Partially Ordered Subsets
Let \(\left( A,\leq\right) \) be a partially ordered set. Thus, \(\leq\) is a binary relation on \(A\) satisfying reflexivity, antisymmetry, and transitivity: \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] .
\end{align*}
Choose a nonempty subset \(X\subset A\). For arbitrary \(x,y\in X\), since \(X\subset A\), we also have \(x,y\in A\), so it makes sense to ask whether \(x\leq y\) holds under the partial order \(\leq\) on \(A\). Define a binary relation \(\leq_{X}\) on \(X\) by \[
x\leq_{X}y\Leftrightarrow x\leq y
\]for arbitrary \(x,y\in X\).
The relation \(\leq_{X}\) is called the restriction of the partial order \(\leq\) on \(A\) to \(X\). As its name suggests, \(\leq_{X}\) is itself a partial order on \(X\).
x\leq_{X}y\Leftrightarrow x\leq y
\]for arbitrary \(x,y\in X\). Then \(\leq_{X}\) is a partial order on \(X\). That is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in X:x\leq_{X}x\\
& \left( O_{2}\right) \ \forall x,y\in X:\left( x\leq_{X}y\wedge y\leq
_{X}x\Rightarrow x=y\right) \\
& \left( O_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\leq_{X}y\wedge y\leq_{X}z\right) \Rightarrow x\leq_{X}z\right] \end{align*}hold.
Given a nonempty subset \(X\) of a partially ordered set \(\left( A,\leq\right) \), the preceding proposition shows that the restriction \(\leq_{X}\) of \(\leq\) to \(X\) is a partial order. Therefore, \[
\left( X,\leq_{X}\right)
\]is also a partially ordered set. It is called a partially ordered subset or simply an ordered subset of \(\left( A,\leq\right) \).
In many cases, the restriction \(\leq_{X}\) is denoted by the same symbol \(\leq\) as the original partial order. In that case, the ordered subset is written as
\[
\left( X,\leq\right) .
\]When it is clear from context that an ordered subset is being discussed, we may simply write
\[
X.
\]
\left(\mathbb{R} ,\leq\right)
\]is a partially ordered set. Since the set of rational numbers \(\mathbb{Q} \) is a nonempty subset of \(\mathbb{R} \), define a binary relation \(\leq_{\mathbb{Q} }\) on \(\mathbb{Q} \) by requiring, for arbitrary \(x,y\in\mathbb{Q} \), that \[
x\leq_{\mathbb{Q} }y\Leftrightarrow x\leq y.
\]Then \(\leq_{\mathbb{Q} }\) is a partial order on \(\mathbb{Q} \). Therefore, \[
\left(\mathbb{Q} ,\leq_{\mathbb{Q} }\right)
\]is a partially ordered set. For the same reason,
\[
\left(\mathbb{Z} ,\leq_{\mathbb{Z} }\right)
\]is a partially ordered set, and
\[
\left(\mathbb{N} ,\leq_{\mathbb{N} }\right)
\]is also a partially ordered set.
\left( 2^{U},\subset\right)
\]is a partially ordered set. Choose a nonempty family of sets \(\mathfrak{A}\subset2^{U}\). Define a binary relation \(\subset_{\mathfrak{A}}\) on \(\mathfrak{A}\) by \[
A\subset_{\mathfrak{A}}B\Leftrightarrow A\subset B
\]for arbitrary \(A,B\in\mathfrak{A}\). Then \(\subset_{\mathfrak{A}}\) is a partial order on \(\mathfrak{A}\). Therefore, \[
\left( \mathfrak{A},\subset_{\mathfrak{A}}\right)
\]is a partially ordered set.
\left(\mathbb{N} ,|\right)
\]is a partially ordered set. Let \(O\) be the set of odd natural numbers. Since \(O\) is a nonempty subset of \(\mathbb{N} \), define a binary relation \(|_{O}\) on \(O\) by \[
x|_{O}y\Leftrightarrow x|y
\]for arbitrary \(x,y\in O\). Then \(|_{O}\) is a partial order on \(O\). Therefore, \[
\left( O,|_{O}\right)
\]is a partially ordered set. For the same reason, if \(E\) denotes the set of even natural numbers, then \[
\left( E,|_{E}\right)
\]is a partially ordered set.
Totally Ordered Subsets
The same discussion applies to totally ordered sets.
Let \(\left( A,\leq\right) \) be a totally ordered set. Thus, \(\leq\) is a binary relation on \(A\) satisfying reflexivity, antisymmetry, transitivity, and completeness: \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] \\
& \left( O_{4}\right) \ \forall x,y\in A:x\leq y\vee y\leq x.
\end{align*}
Choose a nonempty subset \(X\subset A\) and define a binary relation \(\leq_{X}\) on \(X\) by \[
x\leq_{X}y\Leftrightarrow x\leq y
\]for arbitrary \(x,y\in X\). This relation is called the restriction of the total order \(\leq\) on \(A\) to \(X\). The restriction \(\leq_{X}\) is itself a total order on \(X\).
x\leq_{X}y\Leftrightarrow x\leq y
\]for arbitrary \(x,y\in X\). Then \(\leq_{X}\) is a total order on \(X\). That is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in X:x\leq_{X}x\\
& \left( O_{2}\right) \ \forall x,y\in X:\left( x\leq_{X}y\wedge y\leq
_{X}x\Rightarrow x=y\right) \\
& \left( O_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\leq_{X}y\wedge y\leq_{X}z\right) \Rightarrow x\leq_{X}z\right] \\
& \left( O_{4}\right) \ \forall x,y\in X:x\leq_{X}y\vee y\leq_{X}x
\end{align*}hold.
Given a nonempty subset \(X\) of a totally ordered set \(\left( A,\leq\right) \), the preceding proposition shows that the restriction \(\leq_{X}\) is a total order on \(X\). Therefore, \[
\left( X,\leq_{X}\right)
\]is also a totally ordered set. We call it a totally ordered subset of
\(\left( A,\leq\right) \).
As before, the restriction is often denoted by the same symbol \(\leq\), in which case the totally ordered subset is written as \[
\left( X,\leq\right) ,
\]or simply as
\[
X
\]when the meaning is clear from context.
\left(\mathbb{R} ,\leq\right)
\]is a totally ordered set. Since \(\mathbb{Q} \) is a nonempty subset of \(\mathbb{R} \), the restriction defined by \[
x\leq_{\mathbb{Q} }y\Leftrightarrow x\leq y
\]for arbitrary \(x,y\in\mathbb{Q} \) is a total order on \(\mathbb{Q} \). Therefore, \[
\left(\mathbb{Q} ,\leq_{\mathbb{Q} }\right)
\]is a totally ordered set. For the same reason,
\[
\left(\mathbb{Z} ,\leq_{\mathbb{Z} }\right)
\]is a totally ordered set, and
\[
\left(\mathbb{N} ,\leq_{\mathbb{N} }\right)
\]is also a totally ordered set.
Totally Ordered Subsets of Partially Ordered Sets (Chains)
Let \(X\) be a nonempty subset of a partially ordered set \(\left( A,\leq\right) \). The preceding proposition shows that \(\left( X,\leq _{X}\right) \) is a partially ordered set. However, because the partial order \(\leq\) on \(A\) need not satisfy completeness, its restriction \(\leq_{X}\) need not satisfy completeness either. Thus \(\left( X,\leq_{X}\right) \) need not be totally ordered.
On the other hand, by choosing a suitable nonempty subset \(X\) of a partially ordered set \(\left( A,\leq\right) \), it may be possible to obtain a totally ordered subset \(\left( X,\leq_{X}\right) \). A totally ordered subset of a partially ordered set is also called a chain.
\left(\mathbb{N} ,|\right)
\]is a partially ordered set. However, for \(2,3\in\mathbb{N} \), neither \(2|3\) nor \(3|2\) holds. Thus \(|\) does not satisfy completeness, and \(\left(\mathbb{N} ,|\right) \) is not totally ordered.
Now consider the nonempty subset
\[
X=\left\{ 3,9,27,81\right\} .
\]The restriction \(|_{X}\) is a partial order. Since the elements of \(X\) can be written as \(3,3^{2},3^{3},3^{4}\), any two elements are comparable under divisibility. Thus, for arbitrary \(x,y\in X\), \[
x|_{X}y\vee y|_{X}x
\]holds, so \(|_{X}\) satisfies completeness. Therefore, \[
\left( X,|_{X}\right)
\]is a totally ordered set.
Every nonempty partially ordered set has a totally ordered subset.
Exercises
\leq_{X}=\leq\cap\left( X\times X\right) .
\]
\[
\mathcal{P}\left( \left\{ 1,2,3,4\right\} \right) =\left\{ A\subset
\left\{ 1,2,3,4\right\} \right\}
\]be the power set of \(\left\{ 1,2,3,4\right\} \), equipped with the inclusion relation \(\subset\). Show that \[
\left( \mathcal{P}\left( \left\{ 1,2,3,4\right\} \right) ,\subset\right)
\]is a partially ordered set but not a totally ordered set. Then show that
\[
\mathfrak{A}=\left\{ \phi,\left\{ 1\right\} ,\left\{ 1,2\right\}
,\left\{ 1,2,3\right\} ,\left\{ 1,2,3,4\right\} \right\}
\]forms a chain in this partially ordered set.
\left( A,|\right)
\]is a partially ordered set but not a totally ordered set. Then identify all chains in \(A\) containing five elements.
A=\left\{ 1,2,3,4,6,12,24\right\} .
\]Determine which of the following subsets are chains in \(\left( A,|\right) \): \begin{align*}
C_{1} & =\left\{ 1,2,4,12,24\right\} \\
C_{2} & =\left\{ 1,3,6,12,24\right\} \\
C_{3} & =\left\{ 1,2,6,12,24\right\} \\
C_{4} & =\left\{ 1,2,3,6,12\right\} .
\end{align*}
\[
U=\left\{ 1,2,3,4\right\}
\]and define the inclusion relation \(\subset\) on \(2^{U}\). For the families \begin{align*}
\mathfrak{A} & =\left\{ \phi,\left\{ 1\right\} ,\left\{ 1,2\right\}
,\left\{ 1,2,3\right\} ,U\right\} \\
\mathfrak{B} & =\left\{ \phi,\left\{ 1\right\} ,\left\{ 2\right\}
,U\right\} ,
\end{align*}show that \(\mathfrak{A}\) is a chain but \(\mathfrak{B}\) is not.
\[
A=\left\{ 1,2,3,4,5,6,10,12,15,20,30,60\right\}
\]be the set of positive divisors of \(60\), ordered by divisibility. Determine all chains containing five elements.
