What is the simplest proof of Zorn's lemma

[quantum123]

What is the simplest proof of Zorn's lemma from Axiom of Choice?

 

[micromass]

See page 39 of staff.science.uva.nl/~vervoort/AST/ast.ps

It does require a transfinite recursion, the replacement axiom and the Burali-Forti paradox. However, you can't do without these...

 

[micromass]

I just realized that I gave you a .ps file, which you may not be able to open. So, let me post the proof here:

Let $$(A,\preccurlyeq)$$ be a non-empty partially ordened set in which every non-empty chain has an upper bound. Assume that A has no maximal elements. Let $$f:\mathcal{P}(A)\rightarrow A$$ be a choice function for $$\mathcal{P}(A)$$. Define by transfinite recursion the operator $$H:OR\rightarrow \mathbb{V}$$ such that
$$H(\alpha)=f(\{a\in A~\vert~\xi<\alpha~\Rightarrow~H(\xi)\prec a\}),$$
whenever $$\{a\in A~\vert~\xi<\alpha~\Rightarrow~H(\xi)\prec a\}\neq \emptyset$$ and let $$H(\alpha)=A$$ otherwise. We claim the following

$$\forall \alpha:~H(\alpha)\in A~\text{and}~\forall \xi\forall \alpha:~\xi<\alpha~\Rightarrow~H(\xi)\prec H(\alpha)$$

Define the statement $$P(\alpha)$$ as

$$P(\alpha):~\forall \xi\leq \alpha (H(\xi)\in A)~\text{and}~\forall \xi<\alpha:~H(\xi)\prec H(\alpha).$$

We will prove by transfinite recursion that $$P(\alpha)$$ is true for every ordinal. Assume as induction hypothesis that $$P(\beta)$$ is true for every $$\beta<\alpha$$. Then the set $$B=\{H(\beta)~\vert~\beta<\alpha\}$$
is linearly ordered by $$\preccurlyeq$$. Hence we can find an upper bound a of B. Since, by assumption, A has no maximal elements, we can assume that $$a\notin B$$ (Indeed, assume that $$a\in B$$. Since a is not a maximal element, there exists an a' such $$a\prec a^\prime$$. Then a' is an upper bound of B and a' is not in B). This implies that

$$\{a\in A~\vert~\beta<\alpha~\Rightarrow~H(\beta)\prec a\}\neq \emptyset.$$

Thus $$H(\alpha)\in A$$ and $$\xi<\alpha~\Rightarrow~H(\xi)\preccurlyeq H(\alpha)$$.

This implies that H is an injection from OR into A. Then the replacement axiom implies that OR is a set, but this is a contradiction with the Burali-Forti Paradox.

 

[Landau]

I outlined a proof here, which shifts the hard work to some lemma (which does not require AOC itself).

 

[quantum123]

Most complex proof:
http://us.metamath.org/mpegif/zorn2.html