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$?

  • $\begingroup$ @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... $\endgroup$ – Daniele1234 Jun 27 '18 at 21:33
  • $\begingroup$ @Daniele1234: There is really just one option. $\endgroup$ – Asaf Karagila Jun 27 '18 at 21:46
  • $\begingroup$ @AsafKaragila I know how to think of it in plain English, I just can't figure out how to write it down mathematically... $\endgroup$ – Daniele1234 Jun 28 '18 at 8:48
  • $\begingroup$ @Daniele1234: Well, how do you think about it in plain English? $\endgroup$ – Asaf Karagila Jun 28 '18 at 8:54
  • $\begingroup$ @AsafKaragila You take the order defined on the 'largest' set of your chain, no? $\endgroup$ – 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.


The following answer was posted here by the user bof but for some reason it was removed. I worked through all of the details of his/her answer and as far as I could tell it is correct and I was able to prove this question. Here is that answer:

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.

Again, I am not sure why the answer was removed. It could be the case that there is an error in the argument that I did not find, so if anyone discovers this please add a comment.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.