Exercise 8.1.12

Proof.

Let $(A,\preccurlyeq )$ be a partially ordered set. Define the set

We know that $\subseteq$ partially orders $P$. Now consider any $\subseteq$-chain $C$ of $P$. If $C=\varnothing$ then, since clearly we have that $\preccurlyeq \in P$, we have that $\varnothing \subseteq \preccurlyeq$ so that $\preccurlyeq$ is an upper bound of $C$. On the other hand if $C\ne \varnothing$ then there is an $R\in C$, noting that $C\subseteq P$ so that $R\in P$ as well. Then, by the definition of $P$, $R$ is a partial order on $A$ such that $\preccurlyeq \subseteq R$. Let $U=\bigcup <!--\; FUNCTION\; APPLICATION\; -->C$. We first show that $U$ is a partial order on $A$.

So consider any $a\in A$. Then $(a,a)\in R$ since $R$ is a partial order of $A$ (and therefore reflexive). Hence clearly then $(a,a)\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->C=U$ since $R\in C$ so that $U$ is reflexive since $a$ was arbitrary.

Now consider any $x$ and $y$ in $A$ where $(x,y)\in U$ and $(y,x)\in U$. Then, since $U=\bigcup <!--\; FUNCTION\; APPLICATION\; -->C$, there are $S\in C$ and $T\in C$ such that $(x,y)\in S$ and $(y,x)\in T$. Since $C$ is a $\subseteq$-chain, we have that either $S\subseteq T$ or $T\subseteq S$. In the former case then we have that both $(x,y)\in T$ (since $(x,y)\in S$ and $S\subseteq T$) and $(y,x)\in T$ so that $x=y$ since $T$ is a partial order of $A$ (since $T\in C$ and $C\subseteq P$) and is therefore antisymmetric. The case in which $T\subseteq S$ is analogous. This shows that $U$ is antisymmetric.

Lastly, consider $x$, $y$, and $z$ in $A$ such that $(x,y)\in U$ and $(y,z)\in U$. Then, again, we have that there are $S\in C$ and $T\in C$ such that $(x,y)\in S$ and $(y,z)\in T$. We also again have that $S\subseteq T$ or $T\subseteq S$ since $C$ is a $\subseteq$-chain. In the former case we have that $(x,y)\in T$ (since $(x,y)\in S$ and $S\subseteq T$) and $(y,z)\in T$ so that $(x,z)\in T$ since $T$ is a partial order on $A$ (again since $T\in C$ and $C\subseteq P$) and therefore transitive. Hence, since $T\in C$, clearly we have $(x,z)\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->C=U$ so that $U$ is transitive. The case in which $T\subseteq S$ is again analogous.

Therefore we have shown that $U$ is reflexive, antisymmetric, and transitive, and is therefore a partial order on $A$ by definition. Now consider any $(x,y)\in \preccurlyeq$. Then $(x,y)\in R$ since $\preccurlyeq \subseteq R$. Hence $(x,y)\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->C=U$ since $R\in C$. It then follows that $\preccurlyeq \subseteq U$ since $(x,y)$ was arbitrary. Thus $U$ is a partial order on $A$ and $\preccurlyeq \subseteq U$ so that by definition $U\in P$.

Now consider any $S\in C$ and any $(x,y)\in S$. Then clearly $(x,y)\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->C=U$ so that $S\subseteq U$ since $(x,y)$ was arbitrary. Since $S$ was arbitrary this shows that $U$ is in fact an upper bound of $C$ with respect to $\subseteq$.

Since the chain $C$ was arbitrary, this shows that all $\subseteq$-chains of $P$ have an upper bound so that the conditions of Zorn’s Lemma are satisfied. We can therefore conclude that $P$ has a $\subseteq$-maximal element $\le$.

We claim that $\le$ is a linear ordering of $A$. So assume to the contrary that $\le$ is not linear so that there are $a$ and $b$ in $A$ such that $(a,b)\notin \le$ and $(b,a)\notin \le$. Then define the relations

and $R=\le \cup R^{\prime }$. First, notice that $(a,a)\in \le$ and $(b,b)\in \le$ since $\le$ is reflexive so that by definition $(a,b)\in R^{\prime }$ and hence $(a,b)\in R$. We claim that $R\in P$ so that we must first show that $R$ is an order on $A$.

Consider any $x\in A$ so that clearly $(x,x)\in \le$ since $\le$ is an ordering of $A$ and is therefore reflexive. Hence clearly $(x,x)\in \le \cup R^{\prime }=R$ so that $R$ is reflexive.

Now suppose any $x$ and $y$ in $A$ where $(x,y)\in R$ and $(y,x)\in R$. Then clearly $(x,y)\in \le$ or $(x,y)\in R^{\prime }$ and similarly $(y,x)\in \le$ or $(y,x)\in R^{\prime }$

Case: $(x,y)\in \le$. If $(y,x)\in \le$ then clearly $x=y$ since $\le$ is an order on $A$ and therefore is antisymmetric. The sub-case in which $(y,x)\in R^{\prime }$ cannot be since, if it were, then we would have $y\le a$ and $b\le x$. Hence we would have that $b\le x\le y\le a$ so that $b\le a$ by transitivity, which we know is not possible by our definition of $a$ and $b$.

Case: $(x,y)\in R^{\prime }$. Then $x\le a$ and $b\le y$. Here again the sub-case in which $(y,x)\in \le$ is impossible since we would then have $b\le y\le x\le a$ so that $b\le a$ by transitivity. Evidently the sub-case in which $(y,x)\in R^{\prime }$ is also impossible since then we would have $y\le a$ and $b\le x$ so that $b\le x\le a$ as well as $b\le y\le a$ so that $b\le a$ and $a\le b$, which we know is not possible. Hence this entire case is not possible.

Thus, in the only valid case, we have that $x=y$ so that $R$ is antisymmetric.

Now suppose $x$, $y$, and $z$ in $A$ where $(x,y)\in R$ and $(y,z)\in R$. Then we have that $(x,y)\in \le$ or $(x,y)\in R^{\prime }$ and similarly $(y,z)\in \le$ or $(y,z)\in R^{\prime }$.

Case: $(x,y)\in \le$. If $(y,z)\in \le$ also then clearly we have $(x,z)\in \le$ since $\le$ is an order and therefore transitive. If, on the other hand, $(y,z)\in R^{\prime }$ then we have $y\le a$ and $b\le z$. Hence we have that $x\le y\le a$ so that $x\le a$ by transitivity. We thus have $x\le a$ and $b\le z$ so that $(x,z)\in R^{\prime }$ by definition.

Case: $(x,y)\in R^{\prime }$. Then we have $x\le a$ and $b\le y$. If $(y,z)\in \le$ then we have $b\le y\le z$ so that $b\le z$ by transitivity. Hence $x\le a$ and $b\le z$ so that $(x,z)\in R^{\prime }$ by definition. On the other hand, if $(y,z)\in R^{\prime }$, then we have $y\le a$ and $b\le z$. Hence $b\le y\le a$ so that $b\le a$ by transitivity, which we know is not true. Therefore this sub-case is impossible.

Hence in all valid cases we have that $(x,z)\in \le$ or $(x,z)\in R^{\prime }$ so that clearly $(x,z)\in R=\le \cup R^{\prime }$, thereby showing that $R$ is transitive.

Therefore we have shown that $R$ is an ordering of $A$. We also clearly have that $\preccurlyeq \subseteq R$ since $\preccurlyeq \subseteq \le$ (since $\le \in P$) and $\le \subseteq R$ (since $R=\le \cup R^{\prime }$). Thus indeed $R\in P$.

Now, since $R=\le \cup R^{\prime }$ we clearly have that $\le \subseteq R$. We also know that $(a,b)\in R$ but $(a,b)\notin \le$ so that $R\ne \le$, and hence $\le \subset R$. However, this contradicts the fact that $\le$ is a maximal element of $P$ so that it must be that $\le$ is in fact linear!

Lastly, consider any $a$ and $b$ in $A$ where $a\preccurlyeq b$. Then $(a,b)\in \preccurlyeq$ so that $(a,b)\in \le$ because $\preccurlyeq \subseteq \le$ since $\le \in P$. Thus $a\le b$ so that $\le$ is the $\preccurlyeq$-extended linear ordering of $A$ that we seek. □