Hello from Cambridge, Massachusetts! I've just arrived this past week from California, as August 31 marks my last day as a PhD student at Stanford and September 1 my first day as a postdoctoral researcher at MIT. I've been on a significantly reduced work schedule during the move, so rather than working directly on research problems, I've been taking time to bone up some fundamental math skills. This has involved, mostly, an exploration into functional analysis. One of the fundamental theorems of functional analysis is the Hahn-Banach theorem, which is proved using a very standard application of Zorn's lemma.

During my reading, though, I realized that I actually had no idea how Zorn's lemma is proved. I've applied it many times in math courses, but the underpinnings of the lemma elude me. Trying to figure out the proof led me down a pretty deep rabbit hole — it turns out Zorn's lemma is basically a simplified packaging of a general technique called "transfinite induction," which has its roots in Zermelo-Fraenkel set theory. I found all of this material quite hard to understand at first, since I don't have a background in mathematical logic, so I've written this post to give a pedagogical explanation of ordinal numbers, transfinite induction, and Zorn's lemma.

The basic question that underlies all of this discussion is: how do we label the elements of a set in "increasing order"? If the set is finite, then we can label its elements with natural numbers; we might think we can also do this when it is countable, but that isn't actually the case — as we will see, whether we can label a countable set in increasing order using the naturals depends on how the elements are ordered. (We will see in **section 1** that it is possible to order a countable set so that there are elements for which the set of all smaller elements is infinite; these "infinitely preceded" elements are never reached by a natural-number labeling of the set.) The *ordinal numbers* provide a means of labeling every element in a well ordered set, no matter how many elements there are. These numbers are very useful, because they let us formulate inductive proofs on sets whose elements are not ordered according to the ordering scheme of the natural numbers.

The outline is:

- In
**section 1**, I'll define the idea of "well orders" on a set, and state some of their basic properties. I will also give an example of two non-isomorphic well orders on the natural numbers. - In
**section 2**, I'll introduce the*ordinal numbers*as a way to label distinct well orders. I will prove some basic theorems about ordinal numbers, show that every well ordered set is isomorphic to a unique ordinal number, and explain how to label the elements of a well ordered set with ordinal numbers. - In
**section 3**, I'll lay the groundwork for transfinite recursion and induction, explaining how they work abstractly. - In
**section 4**, I'll apply transfinite recursion and induction to prove Zorn's lemma, and then apply Zorn's lemma to show that every set admits a well order. (A fun note: the proof of Zorn's lemma relies on the axiom of choice, and one can in fact show that the statement "every set admits a well order" implies the axiom of choice, so all three statements are equivalent given the other axioms of set theory.)

I learned all of the material in this post from Wikipedia, and from chapter 2 of Jech's book "Set Theory."

**Prerequisites:** Mathematical fluency.

__Table of Contents__

- Well orders
- Ordinal numbers
- Transfinite induction and recursion
- Zorn's lemma and the well ordering theorem

__1. Well orders__

**well ordered**if it has this same property.

- The order is irreflexive, i.e., for any $x \in X,$ $x \not< x.$
- The order is transitive, i.e., for any $x, y, z \in X$ with $x < y$ and $y < z,$ we have $x < z.$
- Any two set elements are comparable, i.e., for any $x, y \in X,$ we have either $x < y,$ $y < x,$ or $x = y.$

- Since $X$ is a subset of itself, it has a unique smallest element.
- For any $x \in X,$ there is a unique
**successor**element $x+1 \in X.$ This is defined as the least element of the set $$\{y \in X | y > x\}.$$ - Every subset with an upper bound has a supremum. I.e., if there exists some $y$ with $y \geq s$ for all $s \in S \subseteq X,$ then $\sup(S)$ is defined as the unique least element of the (nonempty!) set of all upper bounds.

*predecessor set*by

__2. Ordinal numbers__

**order type**, i.e., the isomorphism class of its ordering. The

**ordinal numbers**form a canonical family of well ordered sets that we will show, at the end of this section, contain all possible order types. In other words, every well ordered set is order-isomorphic to one of the ordinal numbers.

*increasing order*. For this to be possible, the ordinal numbers must be ordered among themselves. That is, we must have a binary relation on the class of ordinals so that for any two ordinals $\alpha, \beta,$ we have $\alpha = \beta, \alpha < \beta,$ or $\alpha > \beta.$ Furthermore, we would like this order to match the order on predecessor sets; given $x, y \in X$ with $x < y,$ we would like the corresponding ordinals $\alpha_x, \alpha_y$ to satisfy $\alpha_x < \alpha_y.$

*abstract*characterization of the ordinal numbers, by observing that each ordinal $\alpha$ we have defined thus far has the following two properties:

- Every element of $\alpha$ is also a subset of $\alpha.$
- $\in$ is a well order on $\alpha.$

**ordinal number**. We would like to show the following facts:

- The ordinal numbers are ordered by $\in,$ meaning that for any ordinals $\alpha, \beta$ we have either $\alpha = \beta,$ $\alpha \in \beta,$ or $\beta \in \alpha.$
- The ordinal numbers are "well ordered" with respect to $\in$ in the sense that any class of ordinal numbers has a smallest element. (I put quotes around "well ordered" because the class of all ordinals isn't technically a set in that it doesn't satisfy the axioms of set theory.)
- No two distinct ordinals are order-isomorphic.
- Every well ordered set is order-isomorphic to an ordinal.

**not**isomorphic to an ordinal number. Then there would be a least such element $x_0 \in X$ with this property.

__3. Transfinite induction and recursion__

__3. Transfinite induction and recursion__

*limit ordinal*if it has the property

*successor ordinal*if it has the property

- Let $(X, <)$ be a well ordered set isomorphic to an ordinal number $\alpha.$ Label the elements of $X$ using the ordinal numbers $\beta$ with $\beta \in \alpha.$ Suppose further that $x_0$ has a given property. Suppose that every successor element $x_{\alpha + 1}$ has the property whenever $x_{\alpha}$ has that same property. Suppose that every limit element $x_{\cup \alpha}$ has the desired property whenever $x_{\beta}$ has the desired property for each $\beta \in \alpha.$ Then all elements of the set have the desired property.

This is *transfinite induction*. It differs from standard induction only in that we must check that "properties of prior sets" propagate not just to successor ordinals, but to limit ordinals as well. The theorem can be stated more rigorously as follows (taken from chapter 2 of Jech's book "Set Theory").

- Let $C$ be a class of ordinals and assume that (i) $0 \in C,$ (ii) if $\alpha \in C$ then $\alpha + 1 \in C,$ (iii) if $\alpha$ is a nonzero limit ordinal and $\beta \in C$ for all $\beta \in \alpha,$ then $\alpha \in C.$ Then every ordinal is in $C.$

The proof is easy. If the theorem were not true, then there would exist some ordinal $\gamma$ which is the least ordinal not in $C.$ But $\gamma$ cannot be zero by (i), it cannot be a successor ordinal by (ii), and it cannot be a nonzero limit ordinal by (iii). This completes the proof.

Now that we understand transfinite induction, we can use it to understand transfinite *recursion*, which is a way of constructing ordinal-labeled sets recursively. First, for an ordinal number $\alpha$, a *transfinite sequence of length $\alpha$* in a set $X$ is a map from the elements of $\alpha$ into $X$. This is a (not ordered, often degenerate) labeling of elements of $X$ by ordinal numbers less than $\alpha$. The idea behind transfinite recursion is to construct a map $\alpha \mapsto x_{\alpha}$ from ordinal numbers into $X$ such that the $\alpha$'th value of the map is a function of the $\alpha$-sequence $\{x_{\beta} | \beta < \alpha\}.$

More formally, we specify a set $X$ and a function $G$ that maps transfinite sequences in $X$ to elements of $X$. We then seek a map $\alpha \mapsto x_{\alpha}$ with the property

$$x_{\alpha} = G(\{x_{\beta} | \beta < \alpha\}).$$

Transfinite recursion is the (completely trivial) application of transfinite induction to tell us that once $G$ is specified, the ordinal-to-$X$ function $x_{\alpha}$ exists and is unique.

__4. Zorn's lemma and the well ordering theorem__

We see that this map is strictly order-preserving, i.e., for $\alpha < \beta,$ we have $p(\alpha) < p(\beta).$ This would imply, however, that the map is injective; this cannot be the case, since $P$ is a set, and the class of ordinals is too big to be a set, so there can be no injective map taking ordinal numbers into $P.$

## Comments

## Post a Comment