# Proof Explanation (Zorn's Lemma)

1.13 Theorem The following statements are equivalent:

(a) (The Axiom of Choice) Them exists a choice function for every. of sets.

(b) (The Well-Ordering Principle) Every set can be well-ordered.

(c) (Zorn's Lemma) If every chain in a partially ordered set has an upper bound. then the partially ordered set has a maximal element.

We remind the reader that a chain is a linearly ordered subset of a partially ordered set (see Section 5 of Chapter 2 for this definition, as well as the definitions of "ordered set," "upper bound," "maximal element," and other concepts related to orderings).

Proof. Equivalence of (a) and (b) follows immediately from Theorem 1.1: therefore, it is enough to show that (a) implies (c) and (c) implies (a).

(a) implies (c). Let $(A,\preceq)$ be a (partially) ordered set in which every chain has an upper bound. Our strategy is to search for a maximal element of $(A, \preceq)$ by constructing a $\preceq$-increasing transfinite sequence of elements of $A$.

We fix some $b \not\in A$ and a choice function $g$ for $\mathcal{P}(A)$, and define $\langle a_\alpha \mid \alpha < h(A) \rangle$ by transfinite recursion. Given $\langle a_\zeta \mid \zeta < \alpha \rangle$, we consider two cases. If $b \neq a_\zeta$ for all $\zeta < \alpha$ and $A_\alpha = \{a \in A \mid a_\zeta \prec a \textrm{ holds for all } \zeta < \alpha\} \neq \varnothing$ , we let $a_\alpha = g(A_\alpha)$; otherwise we let $a_\alpha = b$.

We leave to the reader the easy task of justifying this definition by Theorem 4.4 in Chapter 7. We note that $a_\alpha = b$ for some $\alpha < h(A)$; otherwise, $\langle a_\zeta \mid \zeta < h(A)\rangle$ h(A)) would be a one-to-one mapping of $h(A)$ into $A$. Let $\lambda$ be the least $\alpha$ for which $a_\alpha = b$. Then the set $C = \{a_\zeta | \zeta < \lambda\}$ is a chain in $(A, \preceq)$ and so it has an upper bound $c \in A$. If $c \prec a$. for some $a \in A$. we have a $a \in A_\lambda \neq \varnothing$ and $a_\lambda = g(A_\lambda) \neq b$, a contradiction. So $c$ is a maximal element of $A$. (It is easy to see that, in fact, $\lambda = \beta + 1$ and $c = a_\beta$.)

The proof above is taken from the book 'Introduction to Set Theory' by Hrbacek and Jech.

Question: In the proof of $(a)$ implies $(c)$, the set $A_{\alpha}= \{ a \in A: a_{\xi} \prec a \text{ holds for all } \xi < \alpha \}$. What is $a$ here? I don't see the author define such $a$ in previous paragraph.

• It's more readable to use letters like $x,y,x$ in the end of the alphabet as bounded variables and use letters in the beginning as free variables. And it's important to understand that it isn't mysterious with AC, WO and ZL. Such things are trivially true for small sets, but these (equivalent ) conditions are used to define what kind of (big) objects that should be considered as sets. IMO.
– Lehs
Commented Oct 16, 2014 at 10:01
• (1) This has absolutely nothing to do with the particular proof. (2) As you were suggested, by myself and by others, perhaps it would be a good idea to revisit some basic topics before tackling more advanced one. If you build a large structure on shaky foundations, it will collapse. And mathematical knowledge is a very large structure, and your foundations seem very shaky. Commented Oct 16, 2014 at 12:34

$a$ is simply an element of $A$. The author has used this letter to iterate through $A$ and take the only ones that satisfy "$a_{\xi} \prec a \text{ holds for all } \xi < \alpha$". This is called a bound variable.

The author sentence may be rewritten like this : Let $A_\alpha$ the set of all the elements in A that verify "$a_{\xi} \prec a \text{ holds for all } \xi < \alpha$".

• Another question: in the proof, b is not in A. But in the same paragraph, b is not equal to $a_{\xi}$ for all $\xi < \alpha$. Isn't the condition b not in A already guarantee the second condition? Commented Oct 16, 2014 at 9:24
• Is the condition b not in A correct? I think it should be in A. Commented Oct 16, 2014 at 9:28
• I have little time to check but it does seem weird. Commented Oct 16, 2014 at 17:18
• I have figured out the reason. Thanks. Commented Oct 16, 2014 at 18:32

When defining a set we have a separator, a term on the left side and formula on the right side. The term might be bounded in a set, but if you insist on formality then this should be in the right side as well.

Here the term used to define the elements which are collected is $a$. This means that $A_\alpha$ is the set of all those $a\in A$ such that ...

• I have always found it strange to consider it more formally correct to include the set over which the term should range on the right. Doing so suggests it is just part of the restrictive condition, and other conditions without any set bounding the variable would be OK as well. But the axiom schema of specification (which set builder notation implicitly refers to) requires the variable to be bounded on a set. So why not insist that set is mentioned right (in fact: left) where the variable is introduced? Commented Oct 16, 2014 at 12:44
• @Marc: The reason is that we define classes, and if we can prove that these classes are subsets of a pre-existing set, then they are in fact sets. Commented Oct 16, 2014 at 12:50
• Are you implying that in set theory every time one writes down a set, one in fact writes a class, and then provides a separate proof that it is a set? This might be useful occasionally, but I don't see why it should be the norm. Commented Oct 16, 2014 at 12:56
• @Marc, yes this is exactly what I'm saying. The axiom schema of separation tells us that a subclass of a set is a set. So the proof is trivial. But you still define a class. Commented Oct 16, 2014 at 13:02