# Set of partial orderings and Zorn's lemma

Let $X$ be a set and let $P$ be the set of all partial orderings of $X$. ⪯⪯$(P, \leq_p)$ where $\leq_p$ is the ordering such that $\leq\leq_p \leq '$ if $(x\leq y)\Rightarrow (x\leq ' y) \forall x,y\in X$ is a poset. I want to show, using Zorn's lemma, that given any partial ordering $\leq$ there exists a total ordering $\leq '$ such that $\leq\leq_p\leq '$; to accomplish this I tried to apply Zorn's lemma to the set $C:=\{\leq '':\leq\leq_p\leq ''\}$ I tried to show that every totally ordered subset $D$ of $C$ an upper bound (defined in the ⪯text as an element $x\in D$ such that $y\leq_p x \forall y\in D$) but I haven't been able to do so ( I tried by defining an ordering $\leq_m$ such that $x\leq_m y \Leftrightarrow \exists \leq \in D$ such that $x\leq y$ which should be an upper bound but I haven't been able to show that such an ordering belongs to D i.e. that it is an upper bound and not a strict upper bound).

(Note: I know that another user asked a similar question in an almost three years old post and tried a similar approach in proving this fact but he didn't explain why the ordering $\leq_m$ is an upper bound for $D$, that's why I'm asking this question)

So I'd appreciate any help in finishing this proof.

Best regards,

lorenzo.

• Re: I know that another user asked a similar question. If you found older related question, you could post also link to that post. (It might be useful for other users reading your post.) – Martin Sleziak Nov 22 '16 at 15:37

In Zorn's lemma, an upper bound of a set $D$ does not need to be an element of $D$. That is, an upper bound of $D$ is defined to be just an element $c\in C$ such that $d\leq c$ for all $d\in D$. So you don't need to show that $\leq_m$ is an element of $D$; you've already shown that you can apply Zorn's lemma to find a maximal element of $C$.

• It should be remarked, perhaps that while the upper bound need not be an element of $D$, it still has to be an element of $P$. – Asaf Karagila Nov 22 '16 at 10:36
• @Eric Wofsey: in the text I'm using (Analysis 1 by Tao) the proof of Zorn's lemma is based on the lemma that if $X$ is a poset and $x_0 \in X$ then there exists a well-ordered subset $Y$ of $X$ which has $x_0$ as its minimal element and has no strict upper bound; in the proof of Zorn's lemma by assuming that $X$ does not contain a maximal element we arrive to the conclusion that every totally ordered subset of $X$ has a strict upper bound which by the aforementioned lemma is a contradiction and thus Zorn's lemma is proved. – lorenzo Nov 22 '16 at 10:59
• Read the statement and proof of Zorn's lemma carefully. It does not use as a hypothesis that every totally ordered subset of $X$ has a strict upper bound, it only uses the hypothesis that every totally ordered subset of $X$ has an upper bound. The business with strict upper bounds only comes up in the process of the proof (you prove that if $X$ has no maximal element, then actually every totally ordered subset has a strict upper bound and not just an upper bound, and then you use the lemma to get a counterexample to this and hence a contradiction). – Eric Wofsey Nov 22 '16 at 11:12
• You're trying to prove that a total order exists, so you can't assume one exists (that would be circular). Instead, you have to prove that $\leq_M$ is a total order using its maximality. That is, prove that if it wasn't a total order, you could find a different order that is greater than it, which contradicts maximality. So you have to actually construct a specific order in this step. – Eric Wofsey Nov 22 '16 at 19:19
• For that you need to use the fact that $C$ is a chain. So for instance, if $x\leq' y$ and $y\leq'' z$ for $\leq'$ and $\leq''$ in $C$, then you can assume without loss of generality that $\leq'$ is greater than $\leq''$ so actually $y\leq' z$ as well. – Eric Wofsey Nov 24 '16 at 10:40

As Eric points out, an upper bound need not be an element of the set that it is bounding.

In $\Bbb R$, $1$ is an upper bound of $(0,1)$ but still $1\notin(0,1)$. It is true that $1$ is not an upper bound if we only consider the partial order $(0,1)$.

To recap, an upper bound of $D$ in $P$, is an element $p\in P$, such that for all $d\in D$, $d\leq p$. But there is no requirement that $p\in D$.

In the case of partial orders, the increasing union of partial orders is indeed a partial order. Of course, it has no reason to be an element of the chain, but it is a partial order. So the collection of partial orders (which extend some given $\leq$, if you want), satisfy the conditions for Zorn's lemma, and therefore there is a maximal element there. It is not hard to check that this maximal element is a linear order.