Posets
A set \(\Sigma\) is called a partially ordered set or a poset with respect to a relation \(\le\) if for all \(\sigma, \tau, \rho\in\Sigma\):
-
\(\sigma\le\sigma\) (reflexivity)
-
\(\sigma\le\tau\le\sigma\implies\sigma=\tau\) (antisymmetry)
-
\(\rho\le\sigma\le\tau\implies\rho\le\tau\) (transitivity)
We write \(x \lt y\) if \(x\le y\) and \(x\ne y\).
Let \(X\) be some subset of a poset \(\Sigma\). Then we say \(X\) is a chain or that \(X\) is totally ordered if for all \(x,y \in X\) we have \(x\le y\) or \(y\le x\). We say \(\sigma\in\Sigma\) is an upper bound for \(X\) if for all \(x\in X\) we have \(x\le\sigma\). We say \(\sigma\in \Sigma\) is maximal if for all \(\tau\in\Sigma\) we have \(\sigma\le\tau \implies\sigma =\tau\).
Suppose \(x\lt y\) and there is no \(z\) for which \(x\lt z\lt y\) then we say \(y\) covers \(x\).
A poset can be visualized using a Hasse Diagram.
@@@@ <object data="hasse.svg" width="100px" height="100px" type="image/svg+xml"> </object> @@@@
This is a graph where each node represents an element and two distinct nodes are joined by an edge if and only if one covers the other. Usually the node being covered lies is drawn below the other one.
Example:
-
\(\mathbb{Z},\mathbb{Q},\mathbb{R}\) are totally ordered with respect to the usual \(\le\) and none of them posess a maximal element.
-
Let \(S\) be a set and set \(\Sigma = \mathcal{P}(S) = \{T|T\subset S\}\), the power set of \(S\). Then \(\Sigma\) is a poset with respect to \(\subset\) and \(S\) is the maximal element.
Set \(\Sigma' = \mathcal{P}(S)\setminus\{S\}\). Then \(\Sigma'\) is a poset with respect to \(\subset\) with many maximal elements in general, namely \(S\setminus\{x\}\) for all \(x\in S\). 3. Let \(R\) be a ring and set \(\Sigma = \{I|I\triangleleft R, I\ne R\}\). Then \(\Sigma\) is a poset with respect to \(\subset\) and its maximal elements are precisely the maximal ideals of \(R\).
For example, for \(R=\mathbb{Z}_2\) the Hasse diagram \(\Sigma\cup\{R\}\) is a two node graph joined by one edge, where one node represents \(R\) and the other represents \(\{0\}\).
If \(R,S\) are rings then define their direct sum to be \(R\oplus S = \{(x,y)|x\in R, y\in S\}\) with coordinatewise operations. Note that its ideals must have the form \(I\oplus J\) for some \(I \triangleleft R, J \triangleleft S\).
Then if \(R = \mathbb{Z}_2 \oplus \mathbb{Z}_2\) then the Hasse diagram representing \(\Sigma\cup\{R\}\) resembles a diamond, where the four nodes represent the ideals \(R, \{(0,0)\}, \langle(1,0)\rangle, \langle(0,1)\rangle\). The maximal ideals are \(\langle(1,0)\rangle, \langle(0,1)\rangle\).
Now let \(R = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2\). The Hasse diagram for \(\Sigma \cup \{R\}\) now resembles a wireframe cube, and the maximal ideals are all isomorphic to \(\mathbb{Z}_2\oplus \mathbb{Z}_2\).
A poset \(\Sigma\) is called well-ordered if \(\Sigma\) is totally ordered and each nonempty subset of \(\Sigma\) has a least element. Note all finite totally ordered sets are well-ordered.
Example: \(\mathbb{Z}^+, \mathbb{N}\) are well-ordered and \(\mathbb{Z}, \mathbb{Q}^+, \mathbb{R}^+, \mathbb{Q}, \mathbb{R}^+\) are not with respect to the usual \(\le\).
Let \(\Sigma\) be a finite nonempty alphabet with some total order \(\le\). Define the lexicographic or dictionary order on \(\Sigma^*\) by \(x_1 ... x_m \lt y_1 ... y_n\) if for some \(0\le k\lt n\) we have for all \(0\lt i \le k\) that \(x_i = y_i\), and if \(k + 1 \le m\) then \(x_{k+1} \lt y_{k+1}\). This makes \(\Sigma^*\) totally ordered. Then \(\Sigma^*\) is well-ordered if and only if \(|\Sigma| = 1\).
Zorn’s Lemma: Let \(\Sigma\) be a nonempty poset such that every chain \(\mathcal{C}\subset \Sigma\) has an upper bound in \(\Sigma\). Then \(\Sigma\) has a maximal element.
This is equivalent to the Axiom of Choice, the Well-Ordering Principle and Transfinite Induction.
The Well-Ordering Principle states that every set can be well-ordered. This is nontrivial. For example, there is no known explicit well-ordering of \(\mathbb{R}\).
Proof (Idea):
-
Start with any \(x_0 \in \Sigma\).
-
Build a chain \(x_0 \lt x_1 \lt x_2 ...\) unless a maximal element is reached.
-
This chain has an upper bound \(y_0\in\Sigma\).
-
Build a chain \(y_0 \lt y_1\lt y_2 ...\) unless a maximal element is reached.
-
Repeat until a maximal element is reached.
-
Suppose "every element of \(\Sigma\) is examined" but the chain \(\mathcal{C}\) continues to be built without bound. Then for all \(z\in\Sigma\), we either have \(z\lt x\) for some \(x\in\mathcal{C}\) or for all \(x\in\mathcal{C}\) \(x,z\) are not comparable.
-
But this is a contradiction since \(\mathcal{C}\) has an upper bound \(z_0\), and we must have \(x\le z_0\) for all \(x\in\mathcal{C}\).
We can make the "examining every element" statement precise by assuming \(\Sigma\) is well-ordered.
A lattice is a poset in which the greatest lower bound (g.l.b.) and least upper bound (l.u.b.) exist for any pair of elements. A lattice is complete if the g.l.b. and l.u.b. exist for any subset.