2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Martin Sleziak Nov 22 '16 at 15:37
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Asaf Karagila Nov 22 '16 at 10:36
  • $\begingroup$ @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. $\endgroup$ – lorenzo Nov 22 '16 at 10:59
  • 1
    $\begingroup$ 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). $\endgroup$ – Eric Wofsey Nov 22 '16 at 11:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Wofsey Nov 22 '16 at 19:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Wofsey Nov 24 '16 at 10:40
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.