10 Posets, Hasse Diagrams, Lexicographical Ordering, Special Elements, Functions, Countability, Infinities

Lecture from: 21.10.2024 | Video: Videos ETHZ

Partially Ordered Sets (Posets)

Example

The powerset of the set $\{a,b,c\}$, denoted as $\mathcal{P}(\{a,b,c\})$, forms a poset under the subset relation $\subseteq$.

1. Reflexivity:

   • For any subset $S\subseteq \{a,b,c\}$, we need to show that: $S\subseteq S$
   • By the definition of subset, every set is a subset of itself. Therefore, reflexivity holds for all subsets in the powerset.

2. Antisymmetry:

   • Assume $S_1$ and $S_2$ are subsets of $\{a,b,c\}$ such that: $S_1\subseteq S_2\text{and}{S}_2\subseteq S_1$
   • This implies that every element of $S_1$ is in $S_2$, and every element of $S_2$ is in $S_1$.
   • Hence, $S_1$ and $S_2$ must contain exactly the same elements, which gives: $S_1=S_2$
   • Thus, antisymmetry is satisfied.

3. Transitivity:

   • Assume $S_1$, $S_2$, and $S_3$ are subsets of $\{a,b,c\}$ such that:$S_1\subseteq S_2\text{and}{S}_2\subseteq S_3$
   • We need to show that:$S_1\subseteq S_3$
   • By the definition of subset, if every element of $S_1$ is in $S_2$, and every element of $S_2$ is in $S_3$, then every element of $S_1$ must also be in $S_3$. Therefore, we have: $S_1\subseteq S_3$
   • This confirms that transitivity holds.

Since the powerset $\mathcal{P}(\{a,b,c\})$ satisfies reflexivity, antisymmetry, and transitivity, it qualifies as a partially ordered set (poset) under the subset relation $\subseteq$.

Hasse Diagram

A Hasse diagram is a graphical representation of a partially ordered set (poset) that illustrates the relationships between its elements. In a Hasse diagram, the elements are represented as vertices, and the order relations are depicted as edges connecting these vertices. The diagram is drawn in such a way that if $a⪯b$ (meaning $a$ is less than or equal to $b$), then $a$ is placed lower than $b$ in the diagram.

Example: $(\mathcal{P}(\{a,b,c\}),\subseteq )$

For the poset $(\mathcal{P}(\{a,b,c\}),\subseteq )$, the Hasse diagram can be constructed as follows:

Diagram: The Hasse diagram is structured as follows:

In this diagram:

• The empty set $\varnothing$ is at the bottom since it is a subset of all other sets.
• Each set is positioned above the sets it covers, illustrating the subset relationships.

Example: $(\{1,2,3,4,6,8,12,24\},|)$

Let us consider the set of all factors of 24, denoted as $S=\{1,2,3,4,6,8,12,24\}$, with the relation of divisibility denoted by $|$. This relation states that for elements $a$ and $b$ in $S$, we write $a|b$ if $a$ divides $b$ without a remainder.

The Hasse diagram for this poset can be constructed by placing the elements in a vertical arrangement based on the divisibility relation. The diagram is structured as follows:

In this diagram:

• The number 1 is at the bottom since it divides all other numbers.
• Each number is placed above the numbers that it divides, illustrating the divisibility relationships.
• Lines connect the numbers to indicate direct divisibility, meaning that no other element in the set can be placed between them in the order.

Product of Posets

Let us define two posets and take their cross product.

Given two posets:

1. $(A,⪯)$
2. $(B,⊑)$

The product poset is defined as: $(A,⪯)\times (B,⊑)=(A\times B,\le )$

Where the relation $\le$ is defined as follows: $(a_1,b_1)\le (a_2,b_2)\stackrel{\text{def}}{⟺}{a}_1⪯a_2\wedge b_1⊑b_2$

Explanation

• In this definition, the product poset consists of all ordered pairs formed by taking one element from $A$ and one element from $B$.
• The ordering of these pairs is determined by the individual orderings of the elements in each poset.
• Specifically, the pair $(a_1,b_1)$ is less than or equal to the pair $(a_2,b_2)$ if the first component $a_1$ is related to $a_2$ in poset $A$ and the second component $b_1$ is related to $b_2$ in poset $B$.

This construction allows us to combine the structures of the two posets into a new poset, preserving the order relations of both.

Visualization

Visually, we can imagine taking the cross product of two lines, each with two elements. This results in a diamond shape in the Hasse diagram.

For example, consider two posets:

• $A=\{a_1,a_2\}$
• $B=\{b_1,b_2\}$

The product poset $(A\times B,\le )$ consists of the pairs:

The Hasse diagram for this product would look like a diamond:

In this diagram:

• Each pair represents an element of the product poset.
• The lines connect pairs according to the defined relation, illustrating how the elements are ordered based on the individual posets.

The Product is a Poset (Theorem 3.12)

Let us denote the two posets as $(A;⪯)$ and $(B;⊑)$. The product poset is defined as:

where the relation $\le$ is defined as: $(a_1,b_1)\le (a_2,b_2)\text{iff}{a}_1⪯a_2\text{ and }{b}_1⊑b_2.$

We will prove that $(A\times B,\le )$ satisfies the properties of a poset: reflexivity, antisymmetry, and transitivity.

Proof:

1. Reflexivity:

   • For every element $(a,b)\in A\times B$, we have:
   $$(a,b)\le (a,b)\text{iff}a⪯a\text{ and }b⊑b.$$
   • Since both $(A;⪯)$ and $(B;⊑)$ are posets, reflexivity holds for each individual element. Thus, reflexivity is satisfied for the product poset.

2. Antisymmetry:

   • Assume $(a_1,b_1)\le (a_2,b_2)$ and $(a_2,b_2)\le (a_1,b_1)$.
   • By definition of the product order, we have:
     • From $(a_1,b_1)\le (a_2,b_2)$:
     $$a_1⪯a_2\text{and}{b}_1⊑b_2.$$
     • From $(a_2,b_2)\le (a_1,b_1)$:
     $$a_2⪯a_1\text{and}{b}_2⊑b_1.$$
   • Since $a_1⪯a_2$ and $a_2⪯a_1$, by the antisymmetry property of $(A;⪯)$, we conclude that $a_1=a_2$.
   • Similarly, from $b_1⊑b_2$ and $b_2⊑b_1$, we conclude that $b_1=b_2$.
   • Therefore, we have $(a_1,b_1)=(a_2,b_2)$, which proves antisymmetry.

3. Transitivity:

   • Assume $(a_1,b_1)\le (a_2,b_2)$ and $(a_2,b_2)\le (a_3,b_3)$.
   • By definition of the product order, we have:
     • From $(a_1,b_1)\le (a_2,b_2)$:
     $$a_1⪯a_2\text{and}{b}_1⊑b_2.$$
     • From $(a_2,b_2)\le (a_3,b_3)$:
     $$a_2⪯a_3\text{and}{b}_2⊑b_3.$$
   • By the transitivity property of $(A;⪯)$:
   $$a_1⪯a_3.$$
   • By the transitivity property of $(B;⊑)$:
   $$b_1⊑b_3.$$
   • Therefore, we have:
   $$(a_1,b_1)\le (a_3,b_3),$$

   which proves transitivity.

Since we have shown that reflexivity, antisymmetry, and transitivity hold for the relation $\le$ in the product poset $(A\times B,\le )$, we conclude that the product of two posets is itself a poset.

Lexicographical Ordering

Lexicographical ordering is a way of ordering pairs of elements from two posets based on their individual orderings.

Given two posets $(A;\prec )$ and $(B;⊑)$, we define the relation ${\le }_{\mathrm{lex}}$ on the Cartesian product $A\times B$ as follows:

This means that the pair $(a_1,b_1)$ is less than or equal to the pair $(a_2,b_2)$ in lexicographical order if:

1. The first element of the first pair, $a_1$, is less than the first element of the second pair, $a_2$.
2. Alternatively, if the first elements are equal ($a_1=a_2$), then the second element $b_1$ must be less than or equal to $b_2$ in the poset $(B;⊑)$.

Proof that ${\le }_{\mathrm{lex}}$ is a Poset:

To prove that $(A\times B,{\le }_{\mathrm{lex}})$ is a poset, we need to establish the three properties: reflexivity, antisymmetry, and transitivity.

1. Reflexivity:

   • For any $(a,b)\in A\times B$, we have:
   $$(a,b){\le }_{\mathrm{lex}}(a,b)\text{iff}a\le a\text{ and }b\le b.$$
   • This holds true since both $\prec$ and $⊑$ are reflexive relations.

2. Antisymmetry:

   • Assume $(a_1,b_1){\le }_{\mathrm{lex}}(a_2,b_2)$ and $(a_2,b_2){\le }_{\mathrm{lex}}(a_1,b_1)$.
   • From the definitions of ${\le }_{\mathrm{lex}}$, we have two cases to consider:
     • Case 1: If $a_1\prec a_2$ and $a_2\prec a_1$, then by the antisymmetry property of $\prec$, we must have $a_1=a_2$.
     • Case 2: If $a_1=a_2$ and $b_1⊑b_2$ and $b_2⊑b_1$, then by the antisymmetry property of $⊑$, we conclude that $b_1=b_2$.
   • Thus, we have $(a_1,b_1)=(a_2,b_2)$, proving antisymmetry.

3. Transitivity:

   • Assume $(a_1,b_1){\le }_{\mathrm{lex}}(a_2,b_2)$ and $(a_2,b_2){\le }_{\mathrm{lex}}(a_3,b_3)$.
   • By the definition of ${\le }_{\mathrm{lex}}$, we analyze the possible cases:
     • Case 1: If $a_1\prec a_2$ and $a_2\prec a_3$, then by the transitivity property of $\prec$, we have $a_1\prec a_3$.
     • Case 2: If $a_1\prec a_2$ and $a_2=a_3$, then we must have $b_2⊑b_3$, which implies:
     $$(a_1,b_1){\le }_{\mathrm{lex}}(a_3,b_3).$$
     • Case 3: If $a_1=a_2$ and $b_1⊑b_2$, and $a_2\prec a_3$, then by the transitivity of $\prec$ we conclude:
     $$(a_1,b_1){\le }_{\mathrm{lex}}(a_3,b_3).$$
     • Case 4: If $a_1=a_2$ and $b_1⊑b_2$, and $b_2⊑b_3$, then we get:
     $$b_1⊑b_3\text{and}{a}_1=a_3.$$
   • In all cases, we conclude that:
   $$(a_1,b_1){\le }_{\mathrm{lex}}(a_3,b_3),$$

   proving transitivity.

Since we have established reflexivity, antisymmetry, and transitivity for the relation ${\le }_{\mathrm{lex}}$, we conclude that $(A\times B,{\le }_{\mathrm{lex}})$ is indeed a poset.

Special Elements in Posets

Let $(A;⪯)$ be a poset, and let $S\subseteq A$ be some subset of $A$. The following special elements exist:

Minimal and Maximal Elements

• An element $a\in A$ is a minimal element of $A$ if there exists no element $b\in A$ such that $b\prec a$.
• An element $a\in A$ is a maximal element of $A$ if there exists no element $b\in A$ such that $a\prec b$.

Least and Greatest Elements

• An element $a\in A$ is the least element of $A$ if $a⪯b$ for all $b\in A$.
• An element $a\in A$ is the greatest element of $A$ if $b⪯a$ for all $b\in A$.

Lower and Upper Bounds

• An element $a\in A$ is a lower bound of $S$ if $a⪯b$ for all $b\in S$.
• An element $a\in A$ is an upper bound of $S$ if $b⪯a$ for all $b\in S$.

Greatest Lower Bound and Least Upper Bound

• An element $a\in A$ is the greatest lower bound (also known as the infimum) of $S$ if $a$ is the greatest element of the set of all lower bounds of $S$.
• An element $a\in A$ is the least upper bound (also known as the supremum) of $S$ if $a$ is the least element of the set of all upper bounds of $S$.

Some interesting dualisms or parallels can be observed from these definitions:

1. Greatest Common Divisor (GCD):

   • When we consider a poset on the set of natural numbers using the “divides” relation, the greatest lower bound (or infimum) corresponds to the greatest common divisor (GCD) of two numbers. For example, if we have two numbers $a$ and $b$, the GCD of $a$ and $b$ is the largest number that divides both $a$ and $b$.

2. Powerset and Set Operations:

   • In the case of the powerset, where we consider the subset relationship, the infimum (greatest lower bound) of a collection of sets is represented by the intersection of those sets.
   • Conversely, the least upper bound (or supremum) corresponds to the union of the sets. This means that the supremum of a collection of sets is the smallest set that contains all the sets in the collection.

Meet, Join, and Lattices

In the context of partially ordered sets (posets), we can define two important operations known as meet and join:

1. Meet: The meet of two elements $a$ and $b$ in a poset $(A,⪯)$, denoted as $a\wedge b$, is defined as the greatest lower bound (infimum) of $a$ and $b$. If $a$ and $b$ have an infimum, we call it their meet. This means that $c=a\wedge b$ if:

   • $c\le a$ and $c\le b$, and
   • for any other element $d$ such that $d\le a$ and $d\le b$, it follows that $d\le c$.

2. Join: The join of two elements $a$ and $b$, denoted as $a\vee b$, is defined as the least upper bound (supremum) of $a$ and $b$. If $a$ and $b$ have a supremum, we call it their join. This means that $c=a\vee b$ if:

   • $a\le c$ and $b\le c$, and
   • for any other element $d$ such that $a\le d$ and $b\le d$, it follows that $c\le d$.

3. Lattice: A poset $(A,⪯)$ in which every pair of elements has both a meet and a join is called a lattice. This means that for any elements $a$ and $b$ in the poset, both $a\wedge b$ (infimum) and $a\vee b$ (supremum) exist within the set.

A lattice is a special type of poset where every pair of elements has both a meet and a join. In other words, for any $a,b\in A$, both $a\wedge b$ and $a\vee b$ exist within the set.

Functions

A function is a special type of relation. A function $f:A\to B$ from domain $A$ to codomain $B$ is defined by specific properties:

1. For every $a\in A$, there exists a $b\in B$ such that $afb$ (i.e., $f$ is totally defined).
2. For all $a\in A$ and for all $b,b^{\prime }\in B$, if $afb$ and $af{b}^{\prime }$, then $b=b^{\prime }$ (i.e., $f$ is well-defined).

In simpler terms:

1. Totally defined: Every point in A maps to a point in B.
2. Well defined: Every point in A maps to one and only one point in B.

A function $f$ can be understood as a mapping from $A$ to $B$, assigning to every $a\in A$ a unique element in $B$. This unique element is usually denoted as $f(a)$.

We write $f:A\to B$ to indicate the domain and codomain of $f$, and we can define the function using the notation:

For example, we can define a function as follows:

Injective, Surjective, Bijective

In the context of functions, we often classify them based on their properties of mapping elements between the domain and codomain. These classifications include:

1. Injective (One-to-One): A function $f:A\to B$ is called injective if for every $a_1,a_2\in A$, whenever $f(a_1)=f(a_2)$, it follows that $a_1=a_2$. In other words, different elements in the domain map to different elements in the codomain.

   $$\text{If }f(a_1)=f(a_2)\Rightarrow a_1=a_2$$

2. Surjective (Onto): A function $f:A\to B$ is called surjective if for every $b\in B$, there exists at least one $a\in A$ such that $f(a)=b$. This means that the function covers the entire codomain.

   $$\text{For every }b\in B,\exists a\in A\text{ such that }f(a)=b$$

3. Bijective (One-to-One and Onto): A function $f:A\to B$ is called bijective if it is both injective and surjective. This means there is a perfect pairing between the elements of the domain and codomain; each element in the domain maps to a unique element in the codomain, and every element in the codomain is the image of some element in the domain.

   $$f\text{ is bijective if it is both injective and surjective.}$$

These classifications are essential in understanding the behavior of functions and their inverses.

Functions vs Relations

If we denote a relationship $f$ as $afb$ and state that this relationship is a function (i.e., it is totally defined and well-defined), then we can express it as:

In this case, $f$ assigns a unique element $b$ in the codomain to each element $a$ in the domain.

Similarly, if we have another function $g$, we can represent the composition of the functions $f$ and $g$ as:

This composition can also be denoted as $f\circ g$ (if we look at it from the relation standpoint), which means that we first apply $f$ to $a$ and then apply $g$ to the result. For more details on the composition of relations, see Composition of Relations.

However: It’s common to write $g\circ f$ for function compositions, even though this notation might seem illogical. In this case, we interpret $g$ as being applied to the output of $f$, which can sometimes lead to confusion. It’s important to clarify the order of application when discussing function compositions.

Cardinality of Sets and Countability

The concept of cardinality helps us measure the “size” of sets, particularly in distinguishing between countable and uncountable sets.

Definitions:

1. Equinumerous Sets: Two sets $A$ and $B$ are called equinumerous, denoted $A\sim B$, if there exists a bijection (a one-to-one and onto function) between $A$ and $B$. This means that both sets have the same cardinality, or the same “number” of elements.

2. Domination of Sets: A set $B$ dominates a set $A$, denoted $A⪯B$, if there exists an injective (one-to-one) function from $A$ to $B$. Equivalently, $A$ is equinumerous with some subset $C$ of $B$. In this case, $B$ has at least as many elements as $A$. In simple terms: each point in A uniquely maps to a point in B, but not all points in B may map to a point in A. i.e B is at least as big as A. $A\prec B⟺A⪯B\text{ and }A\nsim B$.

3. Countable Sets: A set $A$ is called countable if there exists an injective function from $A$ to the set of natural numbers $\mathbb{N}$, meaning $A⪯\mathbb{N}$. If no such function exists, the set is called uncountable.

Countable sets can be either finite or infinite, but the key is that they can be enumerated in some way. In contrast, uncountable sets cannot be fully enumerated, as their size exceeds that of the natural numbers.

Example: Prime Numbers vs Natural Numbers

The set of prime numbers $\mathbb{P}=\{2,3,5,7,11,13,\dots \}$ is countable because we can establish a bijection between the prime numbers and the natural numbers $\mathbb{N}$.

A bijection $f:\mathbb{N}\to \mathbb{P}$ can be defined by simply mapping each natural number $n\in \mathbb{N}$ to the $n$-th prime number. For example:

This function is injective (each $n$ maps to a unique prime) and surjective (every prime number appears as an image of some $n$). Therefore, the set of prime numbers $\mathbb{P}$ is equinumerous with $\mathbb{N}$, proving that the primes are countable.

Example: Integers are Countable

The set of integers $\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$ is also countable. We know this because $\mathbb{Z}\sim \mathbb{N}$, meaning the integers are equinumerous with the natural numbers.

A bijection $f:\mathbb{N}\to \mathbb{Z}$ is given by the function:

• $f(0)=(-1{)}^0\lceil \frac{0}{2}\rceil =0$
• $f(1)=(-1{)}^1\lceil \frac{1}{2}\rceil =-1$
• $f(2)=(-1{)}^2\lceil \frac{2}{2}\rceil =1$
• $f(3)=(-1{)}^3\lceil \frac{3}{2}\rceil =-2$
• $f(4)=(-1{)}^4\lceil \frac{4}{2}\rceil =2$

This function maps the natural numbers to the integers by alternating between positive and negative values, starting from $0$. It ensures that every integer is paired with exactly one natural number, proving that the set of integers is countable.

Example: $(0,1)\sim \mathbb{R}$

The goal is to find a bijection between the open interval $(0,1)$ and the set of real numbers $\mathbb{R}$. One way to understand this is through a geometric interpretation.

Imagine a line segment on the $xy$-plane, starting at $(-1,1)$, passing through $(0,0)$, and ending at $(1,1)$. This line sits at $y=1$, and its $x$-coordinates range from $-1$ to $1$.

Now, if we project lines from the point $(1,0)$ to every point on this segment, we can cover all points on the real number line $\mathbb{R}$. This geometric mapping can be used to create a bijection between $(0,1)$ and $\mathbb{R}$. Each point in $(0,1)$ corresponds uniquely to a point on the real line, ensuring that this projection reaches every real number.

This approach gives us a visual way of understanding the bijection, establishing that $(0,1)$ is equinumerous with $\mathbb{R}$, or $(0,1)\sim \mathbb{R}$.

Example: $\mathbb{N}\times \mathbb{N}\sim \mathbb{N}$

The Cartesian product $\mathbb{N}\times \mathbb{N}$ represents the set of all ordered pairs of natural numbers, i.e., $\{(a,b)\mid a,b\in \mathbb{N}\}$. Even though $\mathbb{N}\times \mathbb{N}$ seems “larger” than $\mathbb{N}$, we can demonstrate that it is actually countable and has the same cardinality as $\mathbb{N}$, i.e., $\mathbb{N}\times \mathbb{N}\sim \mathbb{N}$.

To show this, we need to find a bijection between $\mathbb{N}\times \mathbb{N}$ and $\mathbb{N}$. One way to achieve this is by using a diagonalization argument (also known as Cantor’s pairing function).

Cantor’s Pairing Function

Cantor’s pairing function is a bijection $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ that maps each pair $(a,b)$ of natural numbers to a single natural number. The function is defined as:

This function ensures that every pair of natural numbers $(a,b)$ is associated with a unique natural number. Here’s how the mapping works:

• $f(0,0)=0$
• $f(0,1)=2$
• $f(1,0)=1$
• $f(1,1)=4$
• $f(2,0)=3$, etc.

Imagine arranging the pairs $(a,b)$ in a grid, where $a$ corresponds to the row and $b$ to the column. By following a diagonal traversal of this grid, we can systematically list all pairs in a sequence that corresponds to a natural number, proving that $\mathbb{N}\times \mathbb{N}$ is countable.

Thus, $\mathbb{N}\times \mathbb{N}\sim \mathbb{N}$, showing that the product of two countably infinite sets is itself countably infinite.

Continue here: 11 Functions, Relations, Cardinality, Countability, Cantor’s Diagonalization Argument