Let \(A\) be a non-empty set, and let \(\preccurlyeq\) be a relation on \(A\text{.}\) The relation \(\preccurlyeq\) is antisymmetric if \(x \preccurlyeq y\) and \(y \preccurlyeq x\) imply that \(x = y\text{,}\) for all \(x, y\in A\)
Definition8.2.Poset.
Let \(A\) be a non-empty set, and let \(\preccurlyeq\) be a relation on \(A\text{.}\) The relation \(\preccurlyeq\) is a partial ordering (also called a partial order) if it is reflexive, transitive and antisymmetric. If \(\preccurlyeq\) is a partial ordering, the pair \((A, \preccurlyeq)\) is a partially ordered set, often abbreviated as poset.
Example8.3.
Let \(A\) be a set. Then \((P(A), \subseteq )\) is a poset but not a totally ordered set, as mentioned previously.
Divisibility in \(\N\) is a poset.
Definition8.4.Toset.
Let \(A\) be a non-empty set, and let \(\preccurlyeq\) be a relation on \(A\text{.}\) The relation \(\preccurlyeq\) is a total ordering (also called a total order or linear ordering) if it is a partial ordering, and if for every \(a, b\in A\text{,}\) at least one of a \(\preccurlyeq b\) or \(b \preccurlyeq a\) holds. If \(\preccurlyeq\) is a total ordering, the pair \((A, \preccurlyeq)\) is a totally ordered set.
Remark8.5.
Formally, a poset is a pair \((A, \preccurlyeq)\text{.}\) However, when the relation \(\preccurlyeq\) is understood from the context, or it is not important to designate the symbol for the relation, we will simply say “let \(A\) be a poset.” Similarly for totally ordered sets.
Example8.6.
Each of the sets \(\N, \Z, \Q\) and \(\R\) with the relation \(\leq \) is a totally ordered set.
Definition8.7.Cover.
Let \((A, \preccurlyeq)\) be a poset, and let \(a, b\in A\text{.}\) The element \(b\) covers the element \(a\) if \(a \preccurlyeq b\text{,}\) and \(a \neq b\text{,}\) and there is no \(x\in A\) such that \(a \preccurlyeq x \preccurlyeq b\) and \(a \neq x \neq b\text{.}\)
Definition8.8.Greatest, Least Element.
Let \((A, \preccurlyeq)\) be a poset, and let \(a\in A\text{.}\) The element \(a\) is a greatest element of \(A\) if \(x \preccurlyeq a\) for all \(x\in A\text{.}\) The element \(a\) is a least element of \(A\) if \(a \preccurlyeq x\) for all \(x\in A\text{.}\)
Example8.9.
The poset \((\Z, \leq )\) has no greatest element or least element. Even finite posets need not have greatest elements or least elements. For example, the poset in Example 7.4.4 (1) does not have a greatest element; observe that \(12\) is not a greatest element with respect to the relation \(a|b\text{,}\) because \(10\) does not divide \(12\text{.}\) The poset does have a least element, the number \(2\text{,}\) because \(2\) divides all the other numbers in the set.
Definition8.10.Maximal, Minimal Element.
Let \((A, \preccurlyeq)\) be a poset, and let \(a\in A\text{.}\) The element a is a maximal element of \(A\) if there is no \(x\in A\) such that \(a \preccurlyeq x\) and \(a \neq x\text{.}\) The element \(a\) is a minimal element of \(A\) if there is no \(x\in A\) such that \(x \preccurlyeq a\) and \(a \neq x\text{.}\)
Example8.11.
The poset \((\Z, \leq )\) has no maximal element or minimal element. Let \((A, \preccurlyeq)\) be the poset in Example 7.4.4 (1). The elements \(8\text{,}\)\(10\) and \(12\) are all maximal elements, which shows that maximal elements need not be unique, and also that maximal elements need not be greatest elements. The element \(2\) is a minimal element, which also happens to be a least element.
Theorem8.12.
Let \((A, \preccurlyeq)\) be a poset. Suppose that \(A\) is finite. Then \(A\) has a maximal element and a minimal element.
We will prove the existence of maximal elements; the existence of minimal elements is similar, and we omit the details. Let \(n = |A|\text{.}\) We proceed by induction on \(n\text{.}\) If \(n = 1\text{,}\) then the single element of \(A\) is clearly a maximal element. Now assume that \(n \geq 2\text{.}\) Suppose that the result is true for \(n - 1\text{.}\) Let \(w\in A\text{,}\) and let \(B = A - \{w\}\text{.}\) By Exercise 7.4.8 we know that \((B, \preccurlyeq)\) is a poset. Because |\(B| = n - 1\text{,}\) it follows from the inductive hypothesis that there is a maximal element \(p\) of \(B\text{.}\) We now define \(r\in A\) as follows. If \(p \preccurlyeq w\text{,}\) let \(r = w\text{;}\) if it is not the case that \(p \preccurlyeq w\text{,}\) then let \(r = p\text{.}\) We claim that \(r\) is a maximal element of \(A\text{.}\) There are two cases. First, suppose that \(p \preccurlyeq w\text{.}\) Then \(r = w\text{.}\) Suppose that there is some \(y\in A\) such that \(w \preccurlyeq y\) and \(w \neq y\text{.}\) By transitivity it follows that \(p \preccurlyeq y\text{,}\) and by antisymmetry it follows that \(p \neq y\text{.}\) Because \(y \neq w\text{,}\) then \(y\in B\text{,}\) and we then have a contradiction to the fact that \(p\) is a maximal element of \(B\text{.}\) It follows that \(w\) is a maximal element of \(A\text{.}\) Second, suppose that it is not the case that \(p \preccurlyeq w\text{.}\) Then \(r = p\text{.}\) Because \(p\) is a maximal element of \(B\text{,}\) then there is no \(x\in B\) such that \(p \preccurlyeq x\) and \(p \neq x\text{.}\) It follows that there is no \(x\in A = B \cup\{w\}\) such that \(p \preccurlyeq x\) and \(p \neq x\text{,}\) and hence \(p\) is a maximal element of \(A\text{.}\)
Definition8.13.Poset Bounds.
Let \((A, \preccurlyeq)\) be a poset, let \(X \subseteq A\) be a subset and let \(a\in A\text{.}\) The element \(a\) is an upper bound of \(X\) if \(x \preccurlyeq a\) for all \(x\in X\text{.}\) The element \(a\) is a least upper bound of \(X\) if it is an upper bound of \(X\text{,}\) and \(a \preccurlyeq z\) for any other upper bound \(z of X\text{.}\) The element \(a\) is a lower bound of \(X\) if \(a \preccurlyeq x\) for all \(x\in X\text{.}\) The element \(a\) is a greatest lower bound for \(X\) if it is a lower bound of \(X\text{,}\) and \(w \preccurlyeq a\) for any other lower bound \(w of X\text{.}\)
Lemma8.14.Uniqueness of Poset Bounds.
Let \((A, \preccurlyeq)\) be a poset, and let \(X \subseteq A\) be a subset. If \(X\) has a least upper bound, then it is unique, and if \(X\) has a greatest lower bound, then it is unique.
Let \(p, q\in A\text{,}\) and suppose that both are least upper bounds of \(X\text{.}\) By definition both \(p\) and \(q\) are upper bounds for \(X\text{.}\) Because \(p\) is a least upper bound of \(X\text{,}\) and \(q\) is an upper bound of \(X\text{,}\) then \(p \preccurlyeq q\) by the definition of least upper bounds. Similarly, we see that \(q \preccurlyeq p\text{.}\) By antisymmetry, it follows that \(p = q\text{.}\) A similar argument works for greatest lower bounds; we omit the details.
Theorem8.15.Poset Extension Theorem.
Let \((A, \preccurlyeq)\) be a poset. Suppose that \(A\) is finite. Then there is a total ordering \(\preccurlyeq'\) on A such that if \(x \preccurlyeq y\) then \(x \preccurlyeq' y\text{,}\) for all \(x, y\in A\text{.}\)
Let \(n = |A|\text{.}\) We proceed by induction on \(n\text{.}\) If \(n = 1\) the result is trivial. Now assume that \(n \geq 2\text{.}\) Suppose that the result is true for \(n - 1\text{.}\) By Theorem 7.4.9 the poset \(A\) has a maximal element, say \(r\in A\text{.}\) Let \(B = A \sm \{r\}\text{.}\) By Exercise 7.4.8 we know that \((B, \preccurlyeq)\) is a poset. Because \(|B| = n - 1\text{,}\) it follows from the inductive hypothesis that there is a total ordering \(\preccurlyeq''\) on \(B\) such that if \(x \preccurlyeq y\) then \(x \preccurlyeq'' y\text{,}\) for all \(x, y\in B\text{.}\) Now define a relation \(\preccurlyeq'\) on \(A\) as follows. If \(x, y\in B\text{,}\) let \(x \preccurlyeq' y\) if and only if \(x \preccurlyeq'' y\text{.}\) If \(x\in A\text{,}\) let \(x \preccurlyeq' r\text{.}\) It is left to the reader in Exercise 7.4.9 to show that \(\preccurlyeq'\) is a total order on \(A\text{,}\) and that if \(x \preccurlyeq y\) then \(x \preccurlyeq' y\text{,}\) for all \(x, y\in A\text{.}\)
Definition8.16.Order Homomorphism.
Let \((A, \preccurlyeq)\) and \((B, \preccurlyeq')\) be posets, and let \(f : A \to B\) be a function. The function \(f\) is an order homomorphism (also called an order preserving function) if \(x \preccurlyeq y\) implies \(f (x) \preccurlyeq' f (y)\text{,}\) for all \(x, y\in A\text{.}\) The function \(f\) is an order isomorphism if it is bijective, and if both \(f\) and \(f\inv\) are order homomorphisms.
Theorem8.17.Finite Toset Classification Theorem.
Let \((A, \preccurlyeq)\) be a totally ordered set. Suppose that \(A\) is finite. Let \(n = |A|\text{.}\) Then there is an order isomorphism from \((A, \preccurlyeq)\) to \((\{1, 2,\dots, n\}, \leq )\text{.}\)
We follow [KR83a]. We prove the result by induction on \(n\text{.}\) When \(n = 1\) the result is trivial. Now assume that \(n \geq 2\text{.}\) Suppose that the result holds for \(n - 1\text{.}\) By Theorem 7.4.9 the poset \(A\) has a maximal element, say \(r\in A\text{.}\) Let \(x\in A\text{.}\) Because \(\preccurlyeq\) is a total ordering, we know that \(x \preccurlyeq r\) or \(r \preccurlyeq x\text{.}\) If it were the case that \(r \preccurlyeq x\text{,}\) then by hypothesis on \(r\) we would know that \(r = x\text{.}\) Hence \(x \preccurlyeq r\text{.}\) Let \(B = A \sm \{r\}\text{.}\) By Exercise 7.4.8 we know that \((B, \preccurlyeq)\) is a poset. Because \(|B| = n - 1\text{,}\) it follows from the inductive hypothesis that there is an order isomorphism from \((B, \preccurlyeq)\) to \((\{1, 2,\dots, n - 1\}, \leq )\text{,}\) say \(f : B \to\{1, 2,\dots, n - 1\}\text{.}\) Let \(F : A \to\{1, 2,\dots, n\}\) be defined by \(F(x) = f (x)\) for all \(x\in B\text{,}\) and \(F(r) = n\text{.}\) Because \(f\) is bijective, it is straightforward to see that \(F\) is bijective as well; we omit the details. To see that \(F\) is an order isomorphism, it suffices by Lemma 7.4.16 to show that \(x \preccurlyeq y\) if and only if \(F(x) \leq F(y)\text{,}\) for all \(x, y\in A\text{.}\) First, let \(x, y\in B\text{.}\) Then \(x \preccurlyeq y\) if and only if \(f (x) \leq f (y)\) because \(f\) is an order isomorphism. Because \(F(x) = f (x)\) and \(F(y) = f (y)\text{,}\) then \(x \preccurlyeq y\) if and only if \(F(x) \leq F(y)\text{.}\) Now let \(z\in B\text{.}\) We know that \(z \preccurlyeq r\text{,}\) and we also know that \(F(z) \leq n = F(r)\text{,}\) because \(F(z)\in\{1, 2,\dots, n - 1\}\text{.}\) Hence \(z \preccurlyeq r\) if and only if \(F(z) \leq F(r)\text{,}\) because both these statements are true. It follows that \(F\) is an order isomorphism.
