Zorn's lemma, every set can be well-ordered
My task is to prove the well-ordering theorem:
Every non empty set $X$ can be well-ordered
I want to do so in the following steps, which involve Zorn's lemma:
Step 1):
Let $X$ be non empty and $\mathcal{P}=\{(Y,<_Y)| Y\subseteq X, \emptyset\neq Y~\text{and}~ <_Y ~ \text{is a well-ordering on Y}\}$. Show that $\mathcal{P}\neq\emptyset$
Proof:
Since $X\neq\emptyset$ it exists $x\in X$. Then $\{x\}\in\mathcal{P}$, because $\emptyset\neq\{x\}\subseteq X$ and $\{x\}$ can obviously be well-ordered.
So $\mathcal{P}\neq\emptyset$.
Step 2):
Let $\leq$ be a partial order on $\mathcal{P}$ defined by:
$(Y, <_Y)\leq (Z, <_Z)\Leftrightarrow Y\subseteq Z~\text{and for every $x,y\in Y$ holds:}~ (x<_Y y\Leftrightarrow x <_Z y)~\text{and for every $y\in Y$, $z\in Z-Y$ holds:}~ y <_Z z.$
Show that $\mathcal{P}$ is ordered inductivly.
Proof:
We have to show that every linear ordered subset of $\mathcal{P}$ has an upper bound.
Let $\{(M_i, <_{M_i})_{i\in I}\}$ be a linear ordered subset of $\mathcal{P}$
Now I would set $S:=\bigcup_{i\in I} M_i$ with an order $<_S$ and show
$(M_i, <_{M_i})\leq (S,<_S)$ for every $i\in I$.
My problem is that I do not know how I can show that $(S,<_S)\in\mathcal{P}$ and in particular how to give an order on $S$.
Also I wonder if you can have a set $M$ with different orders in $\mathcal{P}$.
Like $M=\{x,y\}$ with the order $<$ and $<'$ where it is $x<'y$ and the other order $y<x$.$M$ is well-orderd with regards to both orders.
And I feel like I would get a problem if such $M$ would occur in $S$.
Step 3):
Is $(Y,<_Y)\in\mathcal{P}$ a maximal element regarding $\leq$, then is $Y=X$.
Proof:
First of all it is clear that $Y\subseteq X$.
So we just need to show $Y\supseteq X$.
Suppose the contrary and $Y\not\supseteq X$. Then there is $x\in X$ with $x\notin Y$.
Observe $(\underbrace{Y\cup\{x\}}_{:=Y'}, <_{Y'})$ where $u<_Y' v\Leftrightarrow u<_Y v$ if $u,v\in Y$ and $u<_Y x$ for every $u\in Y$.
Since $(Y,<_Y)$ is maximal we have:
$(Y',<_{Y'})\leq (Y,<_Y)$, but $Y'\not\subseteq Y$. Contradiction.
Step 4):
Conclude the well-ordering theorem
With the lemma of Zorn we can now conclude, that $X$ can be well-ordered, since it is the maximal element of $\mathcal{P}$.
Besides the gap in step 2), is this correct? How can I fix step 2) and provide an order on $S$? What about my concern about equal sets with different orders?
Thanks in advance.
$\endgroup$ 10 Reset to default
