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