Well-Ordering Principle implies Zorn's Lemma

953 Views Asked by At

Well-Ordering Principle implies Zorn's Lemma

Does my attempt look fine or contain logical flaws/gaps? Any suggestion is greatly appreciated. Thank you for your help!


My attempt:

Let $(A,\preccurlyeq)$ be a partially ordered set in which every chain has an upper bound.

By Well-Ordering Principle, there is a well-ordering $\preccurlyeq'$ on $A$. Let $V$ be the class of all sets and $\rm Ord$ be the class of all ordinals. First, we define function $f:\mathcal{P}(A)\setminus\{\emptyset\} \to A$ by $f(X)=\min X$ (with regard to $\preccurlyeq'$).

Next, we define function $G:V \to V$ by $G(x)=f(\{a\in A \mid \forall t\in {\rm ran}(x):t \prec a\})$ if $x$ is a function and $\{a\in A \mid \forall t\in {\rm ran}(x):t \prec a\} \neq \emptyset$, and $G(x)=A$ otherwise. By Transfinite Recursion Theorem, there is a function $F: {\rm Ord} \to V$ such that $F(\alpha)=G(F \restriction \alpha)$ for all $\alpha \in {\rm Ord}$.

It is not hard to verify (by Hartogs number) that $F(\alpha)= A$ for some ordinal $\alpha$. Let $\lambda=\min\{\alpha \in {\rm Ord} \mid F(\alpha)= A\}$. Then ${\rm ran}(F\restriction \lambda)$ is clearly a chain in $(A,\preccurlyeq)$ and has an upper bound $u \in A$. If $u \prec \bar a$ for some $\bar a\in A$, we have $\bar a\in\{a\in A \mid \forall t\in {\rm ran}(F\restriction \lambda):t \prec a\} \neq \emptyset$ and thus $F(\lambda) \in A$. This contradicts the fact that $F(\lambda)=A$. So $u$ is the maximal element of $A$.

1

There are 1 best solutions below

4
On BEST ANSWER

The proof itself is correct (oops), but saying "clearly a chain" is not a good thing to do, at least state what you are using here like you did with Hartogs number.


Let me suggest a more intuitive proof:

First, the intuition: assuming that Zorn's lemma is false, every chain is bounded but there is no maximal element. Now we create a sequence $x_\beta$ to be strictly increasing sequence. Now if we build the sequence $\langle x_\beta\mid \beta<\alpha\rangle$ the set $\{x_\beta\mid \beta<\alpha\}$ is a chain, so it has an upper bound, $y$, and because $y$ is not maximal element there is $x_\alpha$ such that $y\prec x_\alpha$, so add $x_\alpha$ to the sequence, you can keep going and exhaust the ordinal like that, which is impossible.

Now, formal proof for the above:

Let $V,(A,\preccurlyeq),f$ be defined as yours, assume that $A$ doesn't have maximal element, let $x_0\in A$, and $H:V\to V$ defined as followed:

If $g$ is not order preserving function from some ordinal to $A$ then $H(g)=x_0$(the Do not care case).

If $g$ is a function from $\beta\in Ord$ to $A$ and order preserving, then $g[\beta]$ is a chain, let $U$ be the set of upper bounds of $g[\beta]$, then take $f(U)$, now let $U'$ be the set of elements in $A$ that are greater than $f(U)$(with respect to $\prec$), by assumption $U'\ne \emptyset$, so $H(g)=f(U')$.

Now, by the theorem there exists unique $F:Ord\to A$ such that $F(\beta)=H(F\restriction\beta)$.

Use induction to prove that $F\restriction \gamma:\gamma\to A$ is order preserving for all $\gamma$, so $F\restriction \gamma:\gamma\to A$ is injective, set $\gamma=\mbox{Hartogs’ number}$ and you got a contradiction.