# Extending a partial order to a total/linear order using Zorn's Lemma

Here is the question. Given a partially ordered set $(A, \preccurlyeq)$ show that there is a total/linear order $\leq$ on $A$ such that $a \preccurlyeq b$ implies $a \leq b$ for all $a$ and $b$ in $A$, i.e. the total order extends that partial order.

First, I know there are several other questions about this here, namely here (referred to later as Question A), and here. I am posting a new question because the answers for those do not address specifically where I am getting stuck. Well, Question A does but I believe the posted answer is incorrect or at least incomplete, see my comment on the answer there.

I am trying to use the approach in the previous questions, in particular Question A, though I have changed the notation a little to avoid some ambiguity present there. The approach is to define the set $$L = \{(B, \leq_B) \,|\, \text{B \subseteq A and \leq_B is a linear order on B such} \\ \text{that x \preccurlyeq y implies x \leq_B y for all x and y in B}\} \,.$$ We can then define a relation $\trianglelefteq$ on $L$ as follows: $$\text{(B, \leq_B) \trianglelefteq (C, \leq_C) if and only if B \subseteq C and \leq_B \subseteq \leq_C}$$ for any $(B, \leq_B)$ and $(C, \leq_C)$ in $L$. It is easy to show that $\trianglelefteq$ is a partial order on $L$ and that each chain of $L$ has an upper bound, thereby meeting the conditions of Zorn's Lemma.

Therefore $L$ has a maximal element $(\bar{A}, \leq_{\bar{A}})$. The problem I am having is in actually showing that $\bar{A} = A$ so that $\leq_{\bar{A}}$ is then a linear order on $A$ as discussed in Question A, again whose answer I think is invalid because it seems to have mixed up the greatest element with the maximal element. If $(\bar{A}, \leq_{\bar{A}})$ were the greatest element then showing the result would be no sweat. Since it is merely a maximal element though, it seems that the approach should be a proof by contradiction as is so often the case when we are dealing with maximal elements.

We clearly have that $\bar{A} \subseteq A$ by the definition of $L$ (and the fact that $(\bar{A}, \leq_{\bar{A}}) \in L$) but we have to show that $A \subseteq \bar{A}$. So suppose to the contrary that this is not the case so that there is an $a \in A$ where $a \notin \bar{A}$. What we would like to do is construct an element of $(B, \leq_B)$ of $L$ where $(\bar{A}, \leq_{\bar{A}}) \trianglelefteq (B, \leq_B)$, which would be a contradiction since $(\bar{A}, \leq_{\bar{A}})$ is a maximal element.

Clearly the set $B$ should probably be $\bar{A} \cup \{a\}$ since we need to have that $\bar{A} \subseteq B$, but the difficulty is in constructing the ordering $\leq_B$ of $B$ such that the conditions of $L$ are met so that $(B, \leq_B) \in L$. Unless I am missing a simple way to do this, things get messy really fast when trying to ensure transitivity and the fact that it is an extension of $\preccurlyeq$.

Am I missing something simple or is there a better way to prove that $\bar{A} = A$?

• @Asaf Karaglia How do you prove that the hypothesis of Zorn's Lemna holds? I can show that, for the upper bound of a chain, the set is the union of all the sets but I am not sure how to mathematically right the total order for that union... – Daniele1234 Jun 27 '18 at 21:33
• @Daniele1234: There is really just one option. – Asaf Karagila Jun 27 '18 at 21:46
• @AsafKaragila I know how to think of it in plain English, I just can't figure out how to write it down mathematically... – Daniele1234 Jun 28 '18 at 8:48
• @Daniele1234: Well, how do you think about it in plain English? – Asaf Karagila Jun 28 '18 at 8:54
• @AsafKaragila You take the order defined on the 'largest' set of your chain, no? – Daniele1234 Jun 28 '18 at 9:03

Your proof is incorrect, the partial orders all extend a given order on $A$, they are all partial orders on $A$. There are no $B$ and $C$.
The point is that given two points which are incomparable, you can arbitrarily decide that $a<b$, and take the transitive closure of that relation. Then show it is a partial order extending the alleged maximal, therefore there were no incomparable elements.
For a partially ordered set $(A, \preccurlyeq)$ define the set $$P = \{R \subseteq A \times A \,|\, \text{R is a partial order on A and \preccurlyeq \subseteq R}\} \,.$$ Then $\subseteq$ partially orders $P$ and it is easy to show that every $\subseteq$-chain of $P$ has an upper bound. Thus the conditions of Zorn's Lemma are satisfied so that there is a $\subseteq$-maximal element $\leq$ of $P$. To show that $\leq$ is a linear ordering, we assume that it is not so that there are $a$ and $b$ in $A$ such that $(a,b) \notin \leq$ and $(b,a) \notin \leq$. We then define the relation $$R = \leq \cup \{(x,y) \in A \times A \,|\, x \leq a \text{ and } b \leq y\} \,.$$ It is a little tedious but not difficult to then show that $R \in P$ but that $\leq \subset R$, which contradicts the fact that $\leq$ is a maximal element of $P$. So it must be that $\leq$ is in fact linear.