# Proof of Zorn's Lemma

I am looking at the Zorn's Lemma.

The axiom of choice is the following: Let $$I$$ be an arbitrary set of indices and let $$A_i$$ be a family of non-empty sets ($$A_i\neq \emptyset$$), then there exists a map $$\begin{equation*}f: \ I\rightarrow \bigcup_{i\in I}A_i \ \text{ with } \ f(I)\in A_i\end{equation*}$$

The Zorn's Lemma is the following: Each nonempty partially ordered set in which each totally ordered subset has an upper bound contains at least one maximum element.



I am looking at the proof:

A sketch of the proof of Zorn's lemma follows, assuming the axiom of choice. Suppose the lemma is false. Then there exists a partially ordered set $$P$$ such that every totally ordered subset has an upper bound, and every element has a bigger one. For every totally ordered subset $$T$$ we may then define a bigger element b(T), because T has an upper bound, and that upper bound has a bigger element. To actually define the function b, we need to employ the axiom of choice.

Using the function $$b$$, we are going to define elements $$a_0 < a_1 < a_2 < a_3 < \ldots$$ in $$P$$. This sequence is really long: the indices are not just the natural numbers, but all ordinals. In fact, the sequence is too long for the set $$P$$; there are too many ordinals (a proper class), more than there are elements in any set, and the set $$P$$ will be exhausted before long and then we will run into the desired contradiction.

The $$a_i$$ are defined by transfinite recursion: we pick $$a_0$$ in $$P$$ arbitrary (this is possible, since $$P$$ contains an upper bound for the empty set and is thus not empty) and for any other ordinal $$w$$ we set $$a_w = b(\{a_v: v < w\})$$. Because the $$a_v$$ are totally ordered, this is a well-founded definition.

This proof shows that actually a slightly stronger version of Zorn's lemma is true:

If $$P$$ is a poset in which every well-ordered subset has an upper bound, and if $$x$$ is any element of $$P$$, then $$P$$ has a maximal element greater than or equal to $$x$$. That is, there is a maximal element which is comparable to $$x$$.



I have some questions:

Then there exists a partially ordered set $$P$$ such that every totally ordered subset has an upper bound, and every element has a bigger one.

This is the negation of Zorn's lemma, isn't it?



Using the function $$b$$, we are going to define elements $$a_0 < a_1 < a_2 < a_3 < \ldots$$ in $$P$$. This sequence is really long: the indices are not just the natural numbers, but all ordinals. In fact, the sequence is too long for the set $$P$$; there are too many ordinals (a proper class), more than there are elements in any set, and the set P will be exhausted before long and then we will run into the desired contradiction.

Could you explain me this part? What exactly is an ordinal?
And how do we get the contradiction?



The $$a_i$$ are defined by transfinite recursion: we pick $$a_0$$ in $$P$$ arbitrary (this is possible, since $$P$$ contains an upper bound for the empty set and is thus not empty) and for any other ordinal $$w$$ we set $$a_w = b(\{a_v: v < w\})$$. Because the $$a_v$$ are totally ordered, this is a well-founded definition.

Do we define these $$a_i$$ by taking a subset of $$P$$ and then we get a bigger element, then we take a bigger subset and so we get a bigger element, and so on?

• Your statement of Zorn’s Lemma is incorrect: it’s “maximal” (an element $x$ for which $x\leq y$ implies $x=y$), not maximum (an element $x$ such that $z\leq x$ for all $z$). – Arturo Magidin Sep 29 '18 at 16:25
• If you don't know what ordinals are, then you will need to learn a lot about them before you have any hope of understanding this proof. – hmakholm left over Monica Sep 29 '18 at 16:27
• In the formulation of AC yoiu mean "... with $f(i)\in A_i$" – Hagen von Eitzen Sep 29 '18 at 16:29
• The proof of Zorn's lemma using ordinals is very short (if I remember correctly). Suppose every chain is bounded above but that X itself has no maximum element. Then, it's not hard to inject the ordinals into X, which is impossible since Ord is not a set. – Matematleta Sep 29 '18 at 16:32
• @Driver8 Well, that's just a condensed formulation of the proof the OP is trying to understand, isn't it? – Hagen von Eitzen Sep 29 '18 at 16:34

The sketch is somewhat formally problematic; it is intuitively appealing, but it would take a fair amount of formal machinery to actually get it work. That’s part of where “ordinals” come in.

To answer your questions: yes, that is the negation of Zorn’s Lemma. You can write Zorn’s Lemma as:

If (for all $$T\subseteq P$$

(If $$T$$ is totally ordered,

then there exists $$y_T\in P$$ such that $$x\leq y_T$$ for all $$x\in T$$))

then

(there exists $$m\in P$$ such that

(for all $$y\in P$$

(if $$m\leq y$$

then $$m=y$$))).

The negation of “if $$P$$ then $$Q$$” is “$$P$$ and not($$Q$$)”. So the negation of Zorn’s Lemma would be

For all $$T\subseteq P$$

(if $$T$$ is totally ordered,

then there exists $$y_T\in P$$ such that $$x\leq y_T$$ for all $$x\in T$$)

and (for all $$m\in P$$

(there exists $$y\in P$$ such that

$$m\leq y$$ and $$m\neq y$$)).

The last, “$$m\leq y$$ and $$m\neq y$$” is the same as $$m. So the latter clause reads: for every element of $$P$$ there is an element of $$P$$ that is strictly greater than it.

The idea of the proof is: since the empty set is a totally ordered set and has an upper bound, $$P$$ is not empty. Say $$a_1$$. But $$a_1$$ is not maximal, so there exists $$a_2>a_1$$. But $$a_2$$ is not maximal, so there exists $$a_3>a_2$$. “Continuing this way” (Choice, since it involves infinitely many choices) we get $$a_1; let $$T=\{a_1,a_2,\ldots\}$$. This is totally ordered, so it has an upper bound $$a_{\omega}$$. This is not maximal, so there is $$a_{\omega+1}>a_{\omega}$$. “Continuing this way” (Choice) you keep going and going and going and going. Using some technical set theoretic machinery, you can then guarantee that you “keep going” past countability and really past any set size. So this would allow you find a collection of elements of $$P$$ that is strictly larger (in the sense of cardinality) than $$P$$ itself. This is of course impossible, leading to the contradiction.

The “ordinals” are types of well-ordered sets, and they are the generalization of natural numbers. They allow you to define “inductions” that go past the natural numbers and through to other infinite well-ordered sets as indices.

If you want a different version of the proof, I recommend George Bergman’s handout, The Axiom of Choice, Zorn’s Lemma, and all that, available from his website

• When you introduce the concept of cardinality, doesn't that implicitly make use of AC a second time? (Not that it matters, technically) On the other hand, showing that the class of ordinals is proper (and so is any class containing a "copy" of the class of ordinals, like $P$) does not require AC. – Hagen von Eitzen Sep 29 '18 at 16:46
• @HagenvonEitzen: Yes, Bernstein’s Theorem (any two sets are comparable in the sense of cardinality) is equivalent to the Axiom of Choice; this is one reason why this argument takes a bunch of formal machinery to reach the contradiction, as you have to be careful with things like that. I like Bergman’s proof better, though it is somewhat technical, for that reason. – Arturo Magidin Sep 29 '18 at 16:50
• Could you explain to me further how we use at the proof the axiom of choice?  We have that $T$ is a subset of $P$ but since $T$ is larger than $P$ in sense of cardinality we get a contradiction. Have I understood that correctly? – Mary Star Sep 29 '18 at 18:02
• @MaryStar: What you do is that you take as your index set the collection of all chains in $P$ (totally ordered sets of $P$), and then for each chain $C$ in $P$, you define the set $X_C = \{p\in P\mid \forall c\in C(c\lt p)\}$. The assumptions on $P$ guarantee that $X_C$ is nonempty for every $c\in C$. Then you use the axiom of choice to guarantee the existence of a function $\phi$ from the set of all chains to the union of the $X_C$ with $\varphi(C)\in X_C$ for all $C$. Then you let $a_1=\varphi(\varnothing)$, $a_2=\varphi(\{a_1\})$, $a_3=\varphi(\{a_1,a_2\})$, (cont) – Arturo Magidin Sep 29 '18 at 21:05
• Then you let $a_{\omega}=\varphi(\{a_1,\ldots,a_n,\ldots\})$, “and so on”. – Arturo Magidin Sep 29 '18 at 21:06