Ordered Sets
Partially Ordered Sets
Definition 1. A relation \(R\) on a set \(A\) is a partial order relation if \(R\) is reflexive, antisymmetric, and transitive. Partial order relations are often denoted by \(\leq\). If \(\leq\) is a partial order relation on a set \(A\), then \((A, \leq)\) is called a partially ordered set, or poset.
Definition 2. A relation \(R\) on a set \(A\) is a strict partial order relation if \(R\) is irreflexive, asymmetric, and transitive. Strict partial order relations are often denoted by \(<\). If \(<\) is a strict partial order on a set \(A\), then \((A, <)\) is called a strictly partially ordered set.
Theorem 1. If \((A, \leq)\) is a partially ordered set, then the relation \(<\) defined by \[\forall a,b\in A \quad a < b \iff (a \leq b) \land (a \neq b)\] is a strict partial order on \(A\). In particular, every partially ordered set admits a strict partial order.
Proof. Let \((A, \leq)\) be a partially ordered set and define the relation \(<\) on \(A\) as above. Let \(a,b,c\in A\). Since \(a=a\) \[\lnot (a < a)\] and \(<\) is irreflexive. Suppose \(a < b\). Then \(a \leq b\) and \(a \neq b\). Since \(\leq\) is antisymmetric \(\lnot (b \leq a)\). Hence \[\lnot (b < a)\] and \(<\) is asymmetric. Suppose \(a < b\) and \(b < c\). Then \(a \leq b\), \(a \neq b\), \(b \leq c\), and \(b \neq c\). Since \(\leq\) is transitive, \(a \leq c\). Since \(\leq\) is antisymmetric, \(a \neq c\) (if \(a=c\), then \(a\leq b\) and \(b \leq a\), but \(a \neq b\).) It follows that \[a < c\] and \(<\) is transitive. Then \(<\) is a strict partial order relation on \(A\). ◻
Definition 3. Let \((A, \leq)\) be a partially ordered set. Let \(m\in A\). If \[\lnot (\exists a\in A \quad a < m)\] then \(m\) is called a minimal element of \(A\). If \[\forall a\in A \quad m \leq a\] then \(m\) is called a smallest element of \(A\). If \[\lnot (\exists a\in A \quad m < a)\] then \(m\) is called a maximal element of \(A\). If \[\forall a\in A \quad a \leq m\] then \(m\) is called a largest element of \(A\).
Theorem 2. Let \((A, \leq)\) be a partially ordered set. If \(A\) has a smallest element, then it is unique. If \(A\) has a largest element, then it is unique.
Proof. Suppose \(m\in A\) and \(M\in A\) are smallest elements of \(A\). Then \(m \leq M\) and \(M \leq m\). Since \(\leq\) is antisymmetric, \(m = M\). Likewise suppose \(m\in A\) and \(M\in A\) are largest elements of \(A\). Then \(M \leq m\) and \(m \leq M\). Since \(\leq\) is antisymmetric, \(m = M\). ◻
Totally Ordered Sets
Definition 4. A partial order relation \(\leq\) on a set \(A\) is a total order relation, or linear order relation, if \(\leq\) is strongly connected. That is \[\forall a,b\in A \quad (a \leq b) \lor (b \leq a).\] If \(\leq\) is a total order relation on a set \(A\), we call \((A, \leq)\) a totally ordered set, or linearly ordered set.
Definition 5. A strict partial order relation \(<\) on a set \(A\) is a strict total order relation, or strict linear order relation, if \(<\) is connected. That is \[\forall a,b\in A \quad a\neq b \implies (a < b) \lor (b < a).\] If \(<\) is a strict total order relation on a set \(A\), we call \((A, <)\) a strictly totally ordered set, or strictly linearly ordered set.
Theorem 3. Let \((A, \leq)\) be a totally ordered set. The following hold.
If \(x,y\in A\), then \(x < y \iff \lnot (y\leq x)\).
If \(m\in A\) is a minimal element of \(A\), then \(m\) is the smallest element of \(A\).
If \(M\in A\) is a maximal element of \(A\), then \(M\) is the largest element of \(A\).
Proof. Let \(x,y\in A\). Suppose \(x < y\). Then \(x\leq y\) and \(x\neq y\). Since \(\leq\) is antisymmetric, \(\lnot (y\leq x)\). On the other hand, suppose \(\lnot (y\leq x)\). Since \(\leq\) is strongly connected, \(x \leq y\). Since \(\leq\) is reflexive, \(x\neq y\). It follows that \(x < y\).
Let \(m\in A\) be a minimal element of \(A\). Suppose \(m\) is not the smallest element of \(A\). Then there is \(a\in A\) such that \(\lnot (m \leq a)\). Then \(a < m\), contradicting the assumption that \(m\) is a minimal element of \(A\).
Let \(M\in A\) be a maximal element of \(A\). Suppose \(M\) is not the largest element of \(A\). Then there is \(a\in A\) such that \(\lnot (a \leq M)\). Then \(M < a\), contradicting the assumption that \(M\) is a maximal element of \(A\). ◻
Definition 6. Let \((A, \leq)\) be a totally ordered set. For any \(a,b\in A\), we define intervals as the following sets. \[\begin{aligned} [a,b] &= \{x\in A : a \leq x \leq b\} \\ (a,b) &= \{x\in A : a < x < b\} \\ [a,b) &= \{x\in A : a \leq x < b\} \\ (a,b] &= \{x\in A : a < x \leq b\} \end{aligned}\]
Well-Ordered Sets
Definition 7. A totally ordered set \((A, \leq)\) is well-ordered if for each \(B \subseteq A\), there is \(m\in B\) such that \(m\) is a minimal element of \(B\).
Corollary 4. If \((A, \leq)\) is well-ordered, then there is \(m\in A\) such that \(m\) is the smallest element of \(A\). We denote \(m\) by \(0_A\).
Proof. Let \((A, \leq)\) be a well-ordered set. Since \(A \subseteq A\), there is \(m\in A\) such that \(m\) is a minimal element of \(A\). Since \(\leq\) is a total order, \(m\) is the smallest element of \(A\). ◻
Definition 8. Let \((A, \leq)\) be a well-ordered set. We call \(S \subseteq A\) an initial segment of \(A\) if \[\forall s \in S \ \forall a \in A \quad a < s \implies a \in S.\]
Definition 9. Let \((A,\leq_A)\) and \((B,\leq_B)\) be partially ordered sets. An order homomorphism is a function \(\varphi : A \to B\) such that \[\forall x,y\in A \quad x \leq_A y \implies \varphi(x) \leq_B \varphi(y).\] An order isomorphism is a bijective function \(\varphi : A\to B\) such that \[\forall x,y\in A \quad x \leq_A y \iff \varphi(x) \leq_B \varphi(y).\] If \(\varphi : A \to B\) is an order isomorphism, we call \((A, \leq_A)\) and \((B, \leq_B)\) order isomorphic and write \(A \cong B\).
Lemma 5. Suppose \((A, \leq)\) and \((B, \leq)\) are well-ordered. If \(\varphi: A \to B\) is an order isomorphism, then the following hold.
\(\varphi(0_A) = 0_B\).
\(\forall a\in A \quad \varphi([0_A, a]) = [0_B, \varphi(a)] \land \varphi([0_A, a)) = [0_B, \varphi(a))\).
Proof. Let \(\varphi : A\to B\) be an order isomorphism. Since \(\varphi\) is bijective, it is surjective.
Since \(\varphi\) is surjective, there is \(z\in A\) such that \(\varphi(z)=0_B\). Since \(0_A\) is the smallest element of \(A\), we have \(0_A \leq z\). If \(0_A < z\), then \(\varphi(0_A) < \varphi(z) = 0_B\), contradicting that \(0_B\) is the smallest element of \(B\). It follows that \(\varphi(0_A) = 0_B\).
Let \(a\in A\).
Let \(x\in [0_A,a]\). Then \(0_A \leq x \leq a\). Since \(\varphi\) is an order isomorphism, we have \(\varphi(0_A) \leq \varphi(x) \leq \varphi(a)\). Since \(\varphi(0_A) = 0_B\), we have \(\varphi(x)\in [0_B,\varphi(a)]\). Then \(\varphi([0_A,a])\subseteq [0_B,\varphi(a)]\).
Let \(y\in [0_B,\varphi(a)]\). Then \(0_B \leq y \leq \varphi(a)\). Since \(\varphi\) is surjective, there is \(x\in A\) such that \(\varphi(x)=y\). Since \(\varphi(0_A) = 0_B\), we have \(\varphi(0_A) \leq \varphi(x) \leq \varphi(a)\). Since \(\varphi\) is an order isomorphism, we have \(0_A \leq x \leq a\). Then \(x\in [0_A,a]\) and \(y=\varphi(x)\in\varphi([0_A,a])\). Then \([0_B,\varphi(a)]\subseteq \varphi([0_A,a])\).
It follows that \(\varphi([0_A,a]) = [0_B,\varphi(a)]\). The proof that \(\varphi([0_A,a)) = [0_B,\varphi(a))\) is nearly identical. ◻
Theorem 6. If \((A, \leq_A)\) and \((B, \leq_B)\) are nonempty well-ordered sets, then there is a unique order isomorphism from one of the sets onto an initial segment of the other.
Proof. (Existence) WIP
(Uniqueness) Without loss of generality, suppose there is an order isomorphism from \(A\) onto an initial segment of \(B\). Let \(S_1,S_2\) be initial segments of \(B\) and suppose \(f:A\to S_1\) and \(g:A\to S_2\) are order isomorphisms. Let \[C = \{x\in A : f(x)\neq g(x)\}.\] Suppose towards a contradiction that \(C\) is nonempty. Since \(C\subseteq A\) is nonempty and \(A\) is well-ordered, there is a minimal element \(c\in C\). Let \(x\in [0_A,c)\). Then \(0_A \leq x < c\). Then \(x\notin C\) since \(c\) is a minimal element in \(C\). Then \(f(x)=g(x)\). It follows that \(f([0_A,c)) = g([0_A,c))\). Since \(f\) and \(g\) are order isomorphisms \[[0_B, f(c)) = f([0_a,c)) = g([0_A,c)) = [0_B,g(c)).\] Let \(b\in B\). Let \(I = B\setminus [0_B,f(c))\). Then \(b\in I \iff \lnot (b<f(c))\). Since \(B\) is a totally ordered set, \(b\in I \iff f(c)\leq b\). Since \([0_B, f(c)) = [0_B,g(c))\), we have \(I = B\setminus [0_B,g(c))\). Then \(b\in I \iff \lnot (b<g(c))\). Since \(B\) is a totally ordered set, \(b\in I \iff g(c)\leq b\). It follows that \(f(c)\in I\), \(g(c)\in I\), and both are smallest elements of \(I\). Since smallest elements are unique, we have \(f(c)=g(c)\). This contradicts \(c\in C\). It follows that \(C\) is empty.
Then \(f(x)=g(x)\) for all \(x\in A\). Since \(f\) and \(g\) are surjective, \(S_1 = f(A) = g(A) = S_2\). It follows that \(f=g\). ◻
Source File: jakemath.com/latex/sets/ordered_sets.tex