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

  • $\begingroup$ 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. $\endgroup$ Dec 22, 2018 at 2:43

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – Akira
    Dec 22, 2018 at 1:52
  • $\begingroup$ @LeAnhDung sorry, you are correct ( I need to stop answering questions at 3 am). So yes, you are correct $\endgroup$
    – ℋolo
    Dec 22, 2018 at 12:22
  • $\begingroup$ You are very welcome :) $\endgroup$
    – Akira
    Dec 22, 2018 at 12:25
  • $\begingroup$ @LeAnhDung I edit the answer (sorry it took me some time) and added my reasoning for why my method is more intuitive $\endgroup$
    – ℋolo
    Dec 27, 2018 at 13:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .