Elementary order theory

Equivalence relations

Definition 1. A relationship $\preceq$ over a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive.

Definition 2. Let $\preceq$ an equivalence relationship over a set $A$ and $x \in A$. Then the equivalence class of $x$ is denoted $[x]$ and defined as

$$\begin{aligned} [x] = \{y : y \in A \text{ and } y \preceq x\} \end{aligned}$$

This too is quite simple. For example, consider the relationship $\preceq$ such that $a \preceq b$ means $a$ has the same parity than $b$. Then $[2]$ denotes the set of all even numbers. Since the relationship is symmetric, any $x$ such that $2 \preceq x$ satisfies $[2] = [x]$, and this is a generalizable result (true for any $\preceq$).

Theorem 1. Let $\preceq$ an equivalence relationship over $A$ and $x, y$ elements of $A$. Then

$$\begin{aligned} &(1) ~ [x] = [y] \Leftrightarrow x \preceq y \newline &(2) ~ x \not \preceq y \implies [x] \cap [y] = \emptyset \end{aligned}$$

Proof. $(1)$ is quite trivial and we skip it. To prove $(2)$, assume $x \not \preceq y$. If $[x] \cap [y] \neq \emptyset$ then there is some $a \in [x] \cap [y]$ such that $a \preceq x$ and $a \preceq y$. Since $\preceq$ is transitive we have $x \preceq y$, a contradiction. $\blacksquare$

Definition 3. The partition of any set $A$ is any family of non-empty subsets of $A$ that are disjoint and whose union is $A$.

Theorem 2. Let $\preceq$ an equivalence relationship over a non-empty $A$. Then the family of equivalence classes of $A$ is a partition of $A$.

Proof. We have shown any equivalence classes $[x], [y]$ such that $[x] \neq [y]$ are disjoint. Since $x \preceq x$ for any $x \in A$ we are guaranteed that $[x]$ is non-empty for all $A$. It follows then

$$\begin{aligned} \cup \ldots \cup [a_n] = A \end{aligned}$$

where $[a_1], \ldots, [a_n]$ are all (distinct) equivalence classes of $A$. $\blacksquare$

Order relations

Definition 4. A partial order $\preceq$ over a set $P$ is a transitive, reflexive, and anti-symmetric relation between the elements of $P$.

Definition 5. Let $\preceq$ a relationship over $P$ and $a, b$ elements of $P$. We say $b$ covers $a$ if $a \preceq b$ and for every $x \in P$ such that $a \preceq x$, then $b \preceq x$.

Example 1. Take the set $\{2, 4, 5, 8, 9, 12\}$. The number $4$ divides $8$ and $12$ and so does $2$. Then $4$ covers $2$ under the relationship $\mid$ (divides).

Definition 6. Let $(P, \preceq)$ a partial order. A Hasse diagram is a graph $G = (V, E)$ such that $V = P$ and $E = \{(a, b) : a, b \in P: a \text{ covers } b\}$.

Simply put, a Hasse diagram is a graph containing the elements of $P$, and whose edges denote the cover relation. In truth, Hasse diagrams are what make clear the purpose of defining a relationship such as "cover".

Definition 7. Every partial order has minimal and maximal elements, and some have maximum and minimum elements. These are defined as follows.

$$\begin{aligned} \text{max } P = x &\iff \langle \forall e : e \in P : e \preceq x \rangle \newline \text{min } P = x &\iff \langle \forall e : e \in P : x \preceq e \rangle \newline \text{minimal } P = x &\iff \langle \forall e : e \in P \land e \preceq x : x = e \rangle \newline \text{maximal } P = x &\iff \langle \forall e : e \in P \land x \preceq e : x = e \rangle \newline \end{aligned}$$

For a visual representation of their differences, consider the following GIF.

Theorem 3. If $x$ is a maximum, then $x$ is the only maximal. If $x$ is minimum, it is the only minimal.

Proof. It trivially follows from the definitions.

Definition 8. Let $cs(x), cl(x)$ denote that $x$ is the upper or lower bound, respectively, of a partial order $(P, \preceq )$. We say $x$ is a supremum if and only if

$$\begin{aligned} cs(x) \land \langle \forall y : cs(y) : y \geq x \rangle .\end{aligned}$$

We say $x \in P$ is an infimum if and only if

$$\begin{aligned} ci(x) \land \langle \forall y : ci(y) : y \leq x \rangle .\end{aligned}$$

A different way to understand this is to say the infimum of a partial order is its highest lower bound, and the supremum, its smaller upper bound.

Definition 9. A lattice is a partial order where every pair of elements has both a supremum and an infimum.

From a graphical perspective, a lattice conforms a Hasse diagram such that no pair of elements are unconnected.

Since any pair of elements $x, y$ in a lattice has a supremum and an infimum, we may define two binary operators $\land, \lor,$ such that $x \land y, x \lor y$ denote the infimum and supremum of these elements, respectively.

In general, we use the notation $(L, \land, \lor)$ to denote a lattice $L$. This readily conveys that we are dealing with a poset $L$ for which $\land, \lor,$ are well-defined binary operations.

Observe that $\land, \lor$, are reflexive, commutative, and absorbent with respect to each other. In other words,

$$\begin{aligned} x \lor x = x\land x = x, ~ ~ ~ x \land y = y \land x ~ ~ ~ x \lor (x \land y) = x ~ ~ ~ x \land (x \lor y) = x\end{aligned}$$

Definition 10. A lattice $(L, \lor, \land)$ is said to be bounded if $0 \lor x = x, 1 1 \lor x = 1$, where $0, 1$ denote the supremum and infimum of $L$.

Definition 11. We say a lattice $(L, \lor, \land)$ is complemented if and only if for every $x \in L$ there is some $x^c \in L$ such that $x \lor x^c = 1, x \land x^c = 0$.

If $(L, \lor, \land)$ is a lattice and $L$ is a poset under an order relation $\preceq$, then the following properties are satisfied.

$$\begin{aligned} &x \preceq x \lor y \newline &x \land y \preceq x \newline &x \preceq y \iff x \lor y = y \iff x \land y = x \newline &x \preceq z \text{ and } y \preceq w \implies (x \lor y) \preceq (z \lor w) \text{ and } (x \land y) \preceq (z \land w) &\{\text{Compatibility}\} \newline &x\lor(y \land z) \preceq (x\lor y) \text{ and } x \land (y \lor z) \preceq (x \land y) \lor (x \land z)\end{aligned}$$

Definition 12. Two lattices $(L, \land, \lor), (L', \land', \lor')$ are isomorphic if there is a bijection $f : L \to L'$ such that

$$\begin{aligned} f(x \lor y) = f(x) \lor' f(y) ~ ~ ~ f(x \land y) = f(x) \land' f(y) \end{aligned}$$

If this is the case, we write $(L, \land, \lor) ≊/ (L', \land', \lor')$.

Definition 13. A sublattice $(M, \land, \lor)$ of a lattice $(L, \land, \lor)$ is a lattice such that $a.$ $M \subseteq L$, and $b.$ for any $x, y \in M$ we have $x \land y, x \lor y \in M$.

Definition 14. If a lattice is such that $x, y$ satisfy the distributive property, then it is said to be a distributive lattice.

Theorem 4. If a lattice is distributive and bounded, then it is necessarily complemented.

Proof. TO COMPLETE.

Definition 15. A structure $(B, \lor, \land, ^c, 0, 1)$ with $B$ a non-empty set, $^c$ a unary operator, $0, 1 \in B$, is a Boolean algebra if and only if: $a.$ $(B, \lor, \land)$ is a bounded and distributive lattice, and $b.$ $x \lor x^c = 1, x \land x^c = 0$.

Observe that $x^c$ is not required to exist in $B$. This is why a Boolean algebra is not readily defined as a bounded, distributive, and complemented lattice altogether. Furthermore, in a complemented lattice, $a^c$ is understood to be a complement of $a$ as a function of the binary operators $\land, \lor$. In a Boolean algebra, in truth, $^c$ is a unary operation.

Theorem 5. If $(B, \lor, \land, ^c, 0, 1)$ is a Boolean algebra, then its elements satisfy DeMorgan's laws (where $^c$ is understood to be equivalent to negation).

Definition 16. Two Boolean algebras are isomorphic if there is a bijection $f : B \to B'$ such that $f(0) = 0', f(1) = 1'$, and for every $x, y \in B$ we have

$$\begin{aligned} f(x \lor y) = f(x) \lor\ f(y) ~ ~ ~ f(x \land y) = f(x) \land' f(y) ~ ~ ~ f(x^c) = f(x)^{c'} \end{aligned}$$

Representation theorems

Definition 17. Let $B$ a Boolean algebra. An element $a \in B$ is an atom if $a$ covers $0$.

We shall use $At(B)$ to denote the set of all atoms in $B$.

Lemma 1. Let $B$ a finite Boolean algebra. Then any $x \in B$ is uniquely determined as the supreme of atoms. This is, for any $x \in B$,

$$\begin{aligned} &x = \text{sup}\{a \in At(B) : a \preceq x\} \newline &A \subseteq At(B) \text{ and }x = \text{sup } A \implies A = \{a \in At(B) : a \preceq x\} \end{aligned}$$

Proof. Let $A_x = \{ a \in At(B) : a \preceq x\}$ and $y = \text{sup }\{a \in At(B) : a \preceq x\} = \text{sup }A_x$.

(1) Since $x$ is an upper bound of $A_x$, then $y \preceq x$. If $x \not \preceq y$, there is some $a \in At(B)$ such that $a \preceq x$ and $a \not\preceq y$ (see following lemma). But this is absurd by the definition of $y$. Then $x \preceq y$. Then $x = y$.

$(2)$ COMPLETE.

Lemma 2. Let $B$ a finite boolean algebra, and $x, y \in B$ such that $x \not\preceq y$. Then there is some $a \in At(B)$ such that $a \preceq x$ and $a \not\preceq y$. In other words, for finite Boolean algebras, the non-relation of two elements implies the existence of some non-common atom.

Proof. Assume $x \not \preceq y$. From this follows that $x \land y^c \neq 0$. Indeed, if $x \land y^c = 0$, then $y \lor (x \land y^c) = y \lor 0 = y$. So $(y \lor x) \land (y \lor y^c) = (y \lor x) \land 1 = y \lor x = y$, which implies $x \preceq y$, a contradiction. We then have that $a \preceq x\land y^c$ for some $a \in At(B)$. It is clear that $a \preceq x$. Assume $a \preceq y$. Then $a \preceq x \land y^c \land y = 0$, which is absurd since $a$ is atom. Then $x \not \preceq y$ implies there is an atom such that $a \preceq x$ and $a \not \preceq y$.

Theorem 6. Let $B$ a finite Boolean algebra. The function

$$\begin{aligned} f : B &\to \mathcal{P}\big( At(B) \big) \newline x &\to \{a \in At(B) : a \preceq x\} \end{aligned}$$

is an isomorphism between $(B, \land, \lor, ^c, 0, 1)$ and $(\mathcal{P}\big( At(B) \big), \cup, \cap, ^c, \emptyset, At(B))$.

Proof. (1) $f$ is injective because $A_x = A_y$ implies $\text{sup } A_x = \text{sup }A_y$, and by the previous lemmas we have $x = y$. (2) $f$ is surjcetive. Indeed, let $A \subseteq At(B)$ and $x = \text{sup }A$. We have, by the lemmas, that $A = A_x$, which implies $f(x) = A$. $(3)$ That $f$ is an isomorphism it follows from the following fact: TO COMPLETE.

Representation theorem for distributive lattices

Definition 18. Let $(P, \preceq)$ a poset. We say $D \subseteq P$ is decreasing if for any $x, z \in P$ we have

$$\begin{aligned} x \in D \text{ and } y \preceq z \implies z \in D \end{aligned}$$

We use the notation $\mathcal{D}(P)$ to denote the set of all decreasing subsets of $P$, or $\mathcal{D}(P) = \{ D \subseteq P : D \text{ is decreasing }\}$. It follows that to any poset $(P, \preceq )$ there is an associated bounded lattice $(\mathcal{D}(P), \cup, \cap, \emptyset, P)$.

Definition 19. Let $L$ a bounded lattice. An element $x \in L$ is $\lor$-irreducible if

$$\begin{aligned} &x \neq 0 \newline &x = y\lor z \implies x = y \text{ or } x = z, \text{ for all $y, z \in L$ } \end{aligned}$$

It is quite clear that any $a \in At(L)$ is $\lor$-irreducible. If $L$ is a bounded lattice, we write

$$\begin{aligned} Irr(L) = \{i \in L : i \text{ is irreducible }\}\end{aligned}$$

Lemma 3. Let $B$ a Boolean algebra. Then $x \in B$ is $\lor$-irreducible iff $x$ is an atom.

Our last result will be presented without proof. A proof exists in Tiraboschi's order theory.

Theorem 7. Let $L$ a finite distributive bounded lattice. Then

$$\begin{aligned} f : L &\to \mathcal{D} \big( Irr(L) \big) \newline x &\to \{y \in Irr(L) : y \preceq x\} \end{aligned}$$

is an isomorphism between $(L, \lor, \land, 0, 1)$ and $(\mathcal{D}\big( Irr(L) \big), \cup, \cap, \emptyset, Irr(L))$.

Problems

Problem 1. Let $P$ a poset. Prove that if $P$ has a maximum element $x$, then it $x$ is the only maximal.

Assume $x$ is the maximum of $P$. That $x$ is maximal is easy to observe due to the anti-symmetric nature of $\preceq$. Indeed, since $a \preceq x$ for all $x \in a$, it follows $x \not \preceq a$ for all $a \neq x$. (This is an alternative way of interpreting maximality. Indeed, $x \preceq a \implies x = x$ is equivalent to the aforementioned property.) That it is the only maximal is not hard to observe. Simply assume some other maximal $x'$ exists. By definition, $x' \preceq x$. Then $x'$ is not maximal, a contradiction. $\blacksquare$

Problem 2. If $P$ is finite and has a unique maximal $x$, then $x$ is the maximum.

Assume a unique maximal $m$. Assume there is some $x \in P$ such that $x \not \preceq m$. Let $X = \{y \in P : x \preceq y\}$. Since $P$ is finite so is $X$, and then there is a maximal element in $X$, call it $m'$. Observe that $m'$ is also a maximal of $P$ (by definition). That $m' \neq m$ follows from the assumption $x \preceq m$. Then $m$ is a unique maximal, which contradicts our assumption. Then if $m$ is a unique maximal, every $x$ in $P$ must satisfy $x \preceq m$, or equivalently $m$ is also the maximum. $\blacksquare$

Problem 3. Let $f: P \to Q$ be an isomorphism between posets $P, Q$. Show that if $Q$ has some minimal, then so does $P$.

By definition, $f$ is a bijection and therefore it has an inverse $f^{-1}$. Let $m$ denote the minimal of $Q$. Then $f^{-1}(m) = m'$ must be a minimal element of $P$. Simply observe that, for all $x$ in $Q$,

$$\begin{aligned} m \preceq x \implies f(m) \preceq f(x) ~ ~ ~\blacksquare\end{aligned}$$

Problem 4. Let $P$ a poset such that $\text{sup } \{a, b\}$ exists for all $a, b \in P$. Show that $\text{sup } S$ exists for all $S \subseteq P$ that is finite and non-empty.

First of all, observe that any $S \subseteq P$ with $|S| = 1$ has a supremum as an immediate consequence of the definition---it is the very element of $S$. Now let $f(\{a_1, \ldots, a_k\}) = \text{sup } \{f(\{a_1, \ldots, a_{k - 1}\}), a_k\}$ a recursive function for the supremum of a set. We shall prove this function to be well-defined for any $\{a_1, \ldots, a_k\} \subseteq S$.

(1) Let $S \subseteq P$ such that $|S| = 2$. Then $f(S) = \text{sup }\{s_1, s_2\}$ which exists by assumption.

(2) Let $S \subseteq P$ be such that $|S| = k + 1$, with $k \in \mathbb{N}, k + 1 > 2$. Then $f(S) = \text{sup } \{f(\{s_1, \ldots, s_k\}), a_{k + 1}\} = \text{sup } \{x, a_{k +1}\}$. Here, $x = f(\{s_1, \ldots, s_k\})$ exists by inductive hypothesis and $\text{sup } \{x, a_{k + 1}\}$ exists by assumption.

(3) By induction, every finite, non-empty $S \subseteq P$ has a supremum. $\blacksquare$

Problem 5. Let $P$ be a total order. Is it valid to say $P$ has at least one maximal element?

Since $P$ a total order, for every $a, b \in P$ we have $a \preceq b$ or $b \preceq a$. If $P$ is infinite, it is quite clear the statement holds not. If $P$ is finite, the statement must be true, and it can be proven inductively.

(1) Let $\{a, b\}$ a total order. Then either $a \preceq b$ or $b \preceq a$. In the first case, $b$ is maximal; in the second, $a$ is maximal. Then any total order $(T, \preceq)$ with $|T| = 2$ has a maximal element.

(2) Let $(T, \preceq)$ a total order with $|T| = k + 1, k + 1 > 2$. By inductive hypothesis, $T - \{t_{k + 1}\}$ has at least a maximal element $m$. Since $T$ is a total order, then $m \preceq t_{k + 1}$ or $t { k + 1 } \preceq m$. In the second case, it immediately follows that $m$ is a maximal element of $T$. If $m \preceq t{k+1}$, the assumption $t_{k + 1} \preceq x$ for some $x \in T - \{t_{k + 1}\}$ implies $m \preceq x$, which is a contradiction. Then $t_{k + 1}$ precedes only itself. Then $t_{k + 1}$ is maximal.

(3) Any finite total order has a maximal element. $\blacksquare$

Problem 6. Let $B$ a Boolean algebra under the order $\preceq$. Show that $(x^c)^c = x$.

By definition, for every $x \in B$ there is a unique complement $x^c$ such that $x \lor x^c = 1, x \land x^c = 0$. Remember that the $\lor, \land$ operators are commutative. Then $x \lor x^c = x^c \lor x = 1, x \land x^c = x^c \land x = 0$. Then $x$ is a complement of $x^c$. Then $(x^c)^c = x$. $\blacksquare$

Problem 7. Now show $x \preceq y \iff y^c \preceq x^c$.

Assume $x \preceq y$. Then

$$\begin{aligned} y^c &\preceq y^c \land (y^c \lor x^c) &\{\text{Reflex., absorption}\}\newline y^c &\preceq y^c \land (y \land x)^c & \{\text{De Morgan}\}\newline y^c &\preceq y^c \land x^c & \{\text{Assumption}\} \newline y^c &\preceq y^c \land x^c \preceq x^c &\{ a \land b \preceq a\} \newline y^c &\preceq x^c ~ \blacksquare &\{\text{Transitivity}\} .\end{aligned}$$

Now assume $x^c \preceq y^c$. We shall proceed in a similar manner, now remembering that we have shown $(a^c)^c = a$. In particular, observe that by De Morgan's law we have

$$\begin{aligned} a \lor b = (a^c)^c \lor (b^c)^c = (a^c \land b^c)^c .\end{aligned}$$

Now,

$$\begin{aligned} x &\preceq x \land (x \lor y) &\{\text{Absorption}\} \newline x &\preceq x \land (x^c \land y^c)^c &\{\text{Eq. (1)}\} \newline x &\preceq x \land (y^c)^c &\{\text{Assumption}\} \newline x &\preceq x \land y \preceq y \newline x &\preceq y ~ \blacksquare .\end{aligned}$$

Problem 8. Show $y \land z = 0 \iff y \preceq z^c$.

Assume $y \land z = 0$. This problem can be solved by dividing it in two cases. Either $y \lor z = 1$ or $y \lor z \neq 1$.

(1) $\big( y \lor z = 1 \big)$ : If $y \lor z = 1$ then $y = z^c$ (since $y \land z = 0$ by assumption). Then by reflexivity $y \preceq z^c$.

(2) $\big( y \lor z \neq 1 \big)$ : Observe that since $y \lor z \neq 1$ we have $y \neq 1$. Now it follows

$$\begin{aligned} y \land (z \lor z^c) &= y &\{z \lor z^c = 1\}\newline (y \land z) \lor (y \land z^c) &= y &\{\text{Distr.}\} \newline 0 \lor (y \land z^c) &= y &\{\text{Assumption}\} \newline y \land z^c &= y &\{0 \lor a = a\} \newline y &\preceq z^c &\{a \land b = a \Rightarrow a \preceq b\} .\end{aligned}$$

Problem 9. If $x \preceq y$ and $y \land z = 0$, then $z \preceq x^c$.

Given our previous result, it would suffice to show that from the premises follows $x \land z = 0$. Now, assume $x \land z \neq 0$. Since $x \preceq y$, we have $x \land y = x$ and then $(x \land y) \land z \neq 0 \Rightarrow x \land (y \land z) \neq 0$. But $y \land z = 0$ and then we arrive at $x \land 0 \neq 0$, which is a contradiction. Then $x \land z = 0$, which implies $z \preceq x^c$.