# Well-Ordering Principle implies Zorn's Lemma

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

• A different approach: Let $<_W$ be well-order of $A$. For $x\in Ord,$ if $f''x=\{f(y):y\in x\}$ is a $\leq$-chain in $A,$ let $f(x)$ be the $<_W$-least of the $\leq$-upper bounds for $f''x$. Let $x_0$ be the least $x\in Ord$ such that $\exists z\in Ord\,(x\in z\land f(x)=f(z)).$ Show by Transfinite Induction that $f''x$ is a $\leq$-chain for every $x\in Ord.$ Show that $x_0$ is a $\leq$-maximal member of $A.$..... (BTW we will have $f(z)=f(x_0)$ for every ordinal $z$ greater than $x_0.$)..... Some texts use $On$ for the class of ordinals. – DanielWainfleet Dec 22 '18 at 2:43

## 1 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.

• Hi @Holo, we have $F(\emptyset)=G(F \restriction \emptyset)=G(\emptyset)=f(\{a\in A \mid \forall t\in {\rm ran}(\emptyset):t \prec a\})=f(\{a\in A \mid \forall t\in \emptyset:t \prec a\})=f(A)\in A.$ Could you please have a closer check? – LE Anh Dung Dec 22 '18 at 1:52
• @LeAnhDung sorry, you are correct ( I need to stop answering questions at 3 am). So yes, you are correct – ℋolo Dec 22 '18 at 12:22
• You are very welcome :) – LE Anh Dung Dec 22 '18 at 12:25
• @LeAnhDung I edit the answer (sorry it took me some time) and added my reasoning for why my method is more intuitive – ℋolo Dec 27 '18 at 13:41