Notational convention: As in Notes 2, I will colour a statement red in this post if it assumes the axiom of choice. We will, of course, rely on every other axiom of Zermelo-Frankel set theory here (and in the rest of the course).
In this course we will often need to iterate some sort of operation “infinitely many times” (e.g. to create a infinite basis by choosing one basis element at a time). In order to do this rigorously, we will rely on Zorn’s lemma:
Zorn’s Lemma. Let be a non-empty partially ordered set, with the property that every chain (i.e. a totally ordered set) in X has an upper bound. Then X contains a maximal element (i.e. an element with no larger element).
Indeed, we have used this lemma several times already in previous notes. Given the other standard axioms of set theory, this lemma is logically equivalent to
One implication is easy:
Proof of axiom of choice using Zorn’s lemma. Define a partial choice function to be a pair , where is a subset of and is a choice function for . We can partially order the collection of partial choice functions by writing if and f” extends f’. The collection of partial choice functions is non-empty (since it contains the pair consisting of the empty set and the empty function), and it is easy to see that any chain of partial choice functions has an upper bound (formed by gluing all the partial choices together). Hence, by Zorn’s lemma, there is a maximal partial choice function . But the domain of this function must be all of , since otherwise one could enlarge by a single set A and extend to A by choosing a single element of A. (One does not need the axiom of choice to make a single choice, or finitely many choices; it is only when making infinitely many choices that the axiom becomes necessary.) The claim follows.
In the rest of these notes I would like to supply the reverse implication, using the machinery of well-ordered sets. Instead of giving the shortest or slickest proof of Zorn’s lemma here, I would like to take the opportunity to place the lemma in the context of several related topics, such as ordinals and transfinite induction, noting that much of this material is in fact independent of the axiom of choice. The material here is standard, but for the purposes of this course one may simply take Zorn’s lemma as a “black box” and not worry about the proof, so this material is optional.
– Well-ordered sets –
To prove Zorn’s lemma, we first need to strengthen the notion of a totally ordered set.
Definition 1. A well-ordered set is a totally ordered set such that every non-empty subset A of X has a minimal element . Two well-ordered sets X, Y are isomorphic if there is an order isomorphism between them, i.e. a bijection which is monotone ( whenever ).
Example 1. The natural numbers are well-ordered (this is the well-ordering principle), as is any finite totally ordered set (including the empty set), but the integers, rationals, or reals are not well-ordered.
Example 2. Any subset of a well-ordered set is again well-ordered. In particular, if a, b are two elements of a well-ordered set, then intervals such as , , etc. are also well-ordered.
Example 3. If X is a well-ordered set, then the ordered set , defined by adjoining a new element to and declaring it to be larger than all the elements of X, is also well-ordered. More generally, if X and Y are well-ordered sets, then the ordered set , defined as the disjoint union of X and Y, with any element of Y declared to be larger than any element of X, is also well-ordered. Observe that the operation is associative (up to isomorphism), but not commutative in general: for instance, is not isomorphic to .
Example 4. If X, Y are well-ordered sets, then the ordered set , defined as the Cartesian product with the lexicographical ordering (thus if , or if and ), is again a well-ordered set. Again, this operation is associative (up to isomorphism) but not commutative. Note that we have one-sided distributivity: is isomorphic to , but is not isomorphic to in general.
Remark 1. The axiom of choice is trivially true in the case when X is well-ordered, since one can take to be the choice function. Thus, the axiom of choice follows from the well-ordering theorem (every set has at least one well-ordering). Conversely, we will be able to deduce the well-ordering theorem from Zorn’s lemma (and hence from the axiom of choice): see Exercise 11 below.
Exercise 1. (Strong induction on well-ordered sets) Let X be a well-ordered set, and let be a property of elements of X. Suppose that whenever is such that is true for all , then is true. Then is true for every . This is called the principle of strong induction. Conversely, show that a totally ordered set X enjoys the principle of strong induction if and only if it is well-ordered. (For partially ordered sets, the corresponding notion is that of being well-founded.)
To describe the analogue of the ordinary principle of induction for well-ordered sets, we need some more notation. Given a subset A of a non-empty well-ordered set X, we define the supremum of A to be the least upper bound
of A (thus for instance the supremum of the empty set is ). If , we define the successor by the formula
We have the following Peano-type axioms:
Exercise 2. If x is an element of a non-empty well-ordered set X, show that exactly one of the following statements hold:
- (Limit case) .
- (Successor case) for some .
In particular, is not the successor of any element in X.
Exercise 3. Show that if x, y are elements of a well-ordered set such that , then x=y.
Exercise 4. (Transfinite induction for well-ordered sets) Let X be a non-empty well-ordered set, and let be a property of elements of X. Suppose that
- (Base case) is true.
- (Successor case) If and is true, then is true.
- (Limit case) If and is true for all , then is true. [Note that this subsumes the base case.]
Then is true for all .
Remark 2. The usual Peano axioms for succession are the special case of Exercises 2-4 in which the limit case of Exercise 2 only occurs for (which is denoted 0), and the successor function never attains . With these additional axioms, X is necessarily isomorphic to .
Now we introduce two more key concepts.
Definition 2. An initial segment of a well-ordered set X is a subset Y of X such that for all (i.e. whenever y lies in Y, all elements of X that are less than y also lie in Y).
A morphism from one well-ordered set X to another Y is a map which is strictly monotone (thus whenever ) and such that is an initial segment of Y.
Example 5. The only morphism from to is the inclusion map. There is no morphism from to .
We can identify the initial segments of X with elements of :
Exercise 5. Let X be a non-empty well-ordered set. Show that every initial segment I of X is of the form for exactly one .
Exercise 6. Show that an arbitrary union or arbitrary intersection of initial segments is again an initial segment.
Exercise 7. Let be a morphism. Show that maps initial segments of X to initial segments of Y. If is such that x’ is the successor of x, show that is the successor of .
As Example 5 suggests, there are very few morphisms between well-ordered sets. Indeed, we have
Proposition 1. (Uniqueness of morphisms) Given two well-ordered sets X and Y, there is at most one morphism from X and Y.
Proof. Suppose we have two morphisms , . By using transfinite induction (Exercise 4) and Exercise 7, one can show that agree on for every ; setting gives the claim.
Exercise 8. (Schroder-Bernstein theorem for well-ordered sets) Show that two well-ordered sets X, Y are isomorphic if and only if there is a morphism from X to Y, and a morphism from Y to X.
We can complement the uniqueness in Proposition 1 with existence:
Proposition 2. (Existence of morphisms) Given two well-ordered sets X and Y, there is either a morphism from X to Y or a morphism from Y to X.
Proof. Call an element good if there is a morphism from to Y, thus is good. If is good, then we are done. From uniqueness we see that if every element in a set A is good, then the supremum is also good. Applying transfinite induction (Exercise 4), we thus see that we are done unless there exists a good such that is not good. By Exercise 5, for some . If then we could extend the morphism to by mapping a to b, contradicting the fact that is not good; thus and so is surjective. It is then easy to check that exists and is a morphism from Y to X, and the claim follows.
Remark 4. Formally, Proposition 1, Exercise 8, and Proposition 2 tell us that the collection of all well-ordered sets, modulo isomorphism, is totally ordered by declaring one well-ordered set X to be at least as large as another Y when there is a morphism from Y to X. However, this is not quite the case, because the collection of well-ordered sets is only a class rather than a set. Indeed, as we shall soon see, this is not a technicality, but is in fact a fundamental fact about well-ordered sets that lies at the heart of Zorn’s lemma. (From Russell’s paradox we know that the notions of class and set are necessarily distinct.)
– Ordinals –
As we learn very early on in our mathematics education, a finite set of a certain cardinality (e.g. a set ) can be put in one-to-one correspondence with a “standard” set of the same cardinality (e.g. the set ); two finite sets have the same cardinality if and only if they correspond to the same “standard” set ). (The same fact is true for infinite sets; see Exercise 12 below.) Similarly, we would like to place every well-ordered set in a “standard” form. This motivates
Definition 3. A representation of the well-ordered sets is an assignment of a well-ordered set to every well-ordered set X such that
- is isomorphic to X for every well-ordered set X. (In particular, if and are equal, then X and Y are isomorphic.)
- If there exists a morphism from X to Y, then is a subset of (and the order structure on is induced from that on . (In particular, if X and Y are isomorphic, then and are equal.)
Remark 5. In the language of category theory, a representation is a covariant functor from the category of well-ordered sets to itself which turns all morphisms into inclusions, and which is naturally isomorphic to the identity functor.
Remark 6. Because the collection of all well-ordered sets is a class rather than a set, is not actually a function (it is sometimes referred to as a class function).
It turns out that several representations of the well-ordered sets exist. The most commonly used one is that of the ordinals, defined by von Neumann as follows.
Definition 4. An ordinal is a well-ordered set with the property that for all . (In particular, each element of is also a subset of , and the strict order relation on is identical to the set membership relation .)
Example 5. For each natural number , define the ordinal number recursively by setting and for all , thus for instance
and so forth. (Of course, to be compatible with the English language conventions for ordinals, we should write instead of , etc., but let us ignore this discrepancy.) One can easily check by induction that is an ordinal for every n. Furthermore, if we define , then is also an ordinal. (In the foundations of set theory, this construction, together with the axiom of infinity, is sometimes used to define the natural numbers (so that for all natural numbers n), although this construction can lead to some conceptually strange-looking consequences that blur the distinction between numbers and sets, such as and .)
The fundamental theorem about ordinals is
- Given any two ordinals , one is a subset of the other (and the order structure on is induced from that on ).
- Every well-ordered set X is isomorphic to exactly one ordinal .
In particular, is a representation of the well-ordered sets.
Proof. We first prove 1. From Proposition 2 and symmetry, we may assume that there is a morphism from to . By strong induction (Exercise 1) and Definition 4, we see that for all , and so is the inclusion map from into . The claim follows.
Now we prove 2. If uniqueness failed, then we would have two distinct ordinals that are isomorphic to each other, but as one ordinal is a subset of the other, this would contradict Proposition 1 (the inclusion morphism is not an isomorphism); so it suffices to prove existence.
We use transfinite induction. It suffices to show that for every , that is isomorphic to an ordinal (which we know to be unique). This is of course true in the base case . To handle the successor case , we set , which is easily verified to be an ordinal isomorphic to . To handle the limit case , we take all the ordinals associated to elements in and take their union (here we rely crucially on the axiom schema of replacement and the axiom of union); by use of part 1 one can show that this union is an ordinal isomorphic to a as required.
Remark 7. Operations on well-ordered sets, such as the sum and product defined in Examples 3, 4, induce corresponding operations on ordinals, leading to ordinal arithmetic, which we will not discuss here. (Note that the convention for which order multiplication proceeds in is swapped in some of the literature, thus would be the ordinal of rather than .)
Exercise 9. (Ordinals are themselves well-ordered) Let be a non-empty class of ordinals. Show that there is a least ordinal in this class, which is a subset of all the other ordinals in this class. In particular, this shows that any set of ordinals is well-ordered by set inclusion.
Remark 8. Because of Exercise 9, we can meaningfully talk about “the least ordinal obeying property P”, as soon as we can exhibit at least one ordinal with that property P. For instance, once one can demonstrate the existence of an uncountable ordinal (which follows from Exercise 11 below), one can talk about the least uncountable ordinal.
Exercise 10. (Transfinite induction for ordinals) Let be a property pertaining to ordinals . Suppose that
- (Base case) is true.
- (Successor case) If for some ordinal , and is true, then is true.
- (Limit case) If , and is true for all , then is true.
Show that is true for every ordinal .
Now we show a fundamental fact, that the well-ordered sets are just too “numerous” to all fit inside a single set, even modulo isomorphism.
Theorem 2. There does not exist a set A and a representation of the well-ordered sets such that for all well-ordered sets X.
Proof. By Theorem 1, any two distinct ordinals are non-isomorphic, and so get mapped under to a different element of A. Thus we can identify the class of ordinals with a subset of A, and so the class of ordinals is in fact a set. In particular, by the axiom of union, we may take the union of all the ordinals, which one can verify to be another ordinal . But then is another ordinal, which implies that , which contradicts the axiom of foundation.
Remark 9. It is also possible to prove Theorem 2 without the theory of ordinals, or the axiom of foundation. One first observes (by transfinite induction) that given two well-ordered sets X, X’, one of the sets is a subset of the other. Because of this, one can show that the union S of all the (where X ranges over all well-ordered sets) is well-defined (because the form a subset of A) and well-ordered. Now we look at the well-ordered set ; by Proposition 1, it is not isomorphic to any subset of S, but is necessarily contained in S, a contradiction.
Remark 10. The same argument also shows that there is no representation of the ordinals inside a given set; the ordinals are “too big” to be placed in anything other than a class.
– Zorn’s lemma –
Now we can prove Zorn’s lemma. The key proposition is
Proposition 2. Let X be a partially ordered set, and let be the set of all well-ordered sets in X. Then there does not exist a function such that is a strict upper bound for C (i.e. for all ) for all well-ordered .
Proof. Suppose for contradiction that there existed X and g with the above properties. Then, given any well-ordered set Y, we claim that there exists exactly one isomorphism from Y to a well-ordered set in X such that for all . Indeed, the uniqueness and existence can both be established by a transfinite induction that we leave as an exercise. (Informally, is what one gets by “applying g Y times, starting with the empty set”.) From uniqueness we see that whenever Y and Y’ are isomorphic, and another transfinite induction shows that whenever Y is a subset of Y’. Thus is a representation of the ordinals. But this contradicts Theorem 2.
Remark 11. One can use transfinite induction on ordinals rather than well-ordered sets if one wishes here, using Remark 10 in place of Theorem 2.
Proof of Zorn’s lemma. Suppose for contradiction that one had a non-empty partially ordered set X without maximal elements, such that every chain had an upper bound. As there are no maximal elements, every element in X must be bounded by a strictly larger element in X, and so every chain in fact has a strict upper bound; in particular every well-ordered set has a strict upper bound. Applying the axiom of choice, we may thus find a choice function from the space of well-ordered sets in X to X, that maps every such set to a strict upper bound. But this contradicts Proposition 2.
Remark 12. It is important for Zorn’s lemma that X is a set, rather than a class. Consider for instance the class of all ordinals. Every chain of ordinals has an upper bound (namely, the union of the ordinals in that chain), and the class is certainly non-empty, but there is no maximal ordinal. (Compare also Theorem 1 and Theorem 2.)
Remark 13. It is also important that every chain have an upper bound, and not just countable chains. Indeed, the collection of countable subsets of an uncountable set (such as ) is non-empty, and every countable chain has an upper bound, but there is no maximal element.
Remark 14. The above argument shows that the hypothesis of Zorn’s lemma can be relaxed slightly; one does not need every chain to have an upper bound, merely every well-ordered set needs to have one. But I do not know of any application in which this apparently stronger version of Zorn’s lemma dramatically simplifies an argument. (In practice, either Zorn’s lemma can be applied routinely, or it fails utterly to be applicable at all.)
Exercise 11. Use Zorn’s lemma to establish the well-ordering theorem (every set has at least one well-ordering).
Remark 15. By the above exercise, can be well-ordered. However, if one drops the axiom of choice from the axioms of set theory, one can no longer prove that is well-ordered. Indeed, given a well-ordering of , it is not difficult (using Remark 1) to remove the axiom of choice from the Banach-Tarski constructions in Notes 2, and thus obtain constructions of non-measurable subsets of . But a deep theorem of Solovay gives a model of set theory (without the axiom of choice) in which every set of reals is measurable.
Exercise 12. Define a (von Neumann) cardinal to be an ordinal with the property that all smaller ordinals have strictly lesser cardinality (i.e. cannot be placed in one-to-one correspondence with ). Show that every set can be placed in one-to-one correspondence with exactly one cardinal. (This gives a representation of the category of sets, similar to how gives a representation of well-ordered sets.)
It seems appropriate to close these notes with a quote from Jerry Bona:
“The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn’s Lemma?”
[Update, Jan 29: some more remarks added.]
[Update, Jan 30: more remarks added.]