current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite

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.

share|cite|improve this question
1  
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 4 hours ago
up vote 4 down vote

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

share|cite|improve this answer
1  
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 9 hours ago
    
@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 8 hours ago
    
@Eric Wofsey : So if in this proof I use strict upper bound I'll have to modify the proof of Zorn's lemma which is why I'm asking for an upper bound and not a strict one – lorenzo 8 hours ago
1  
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 8 hours ago
1  
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 38 mins ago
up vote 3 down vote

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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