Ordinal numbers, transfinite induction, and Zorn's Lemma

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:

1. 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.
2. 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.
3. In section 3, I'll lay the groundwork for transfinite recursion and induction, explaining how they work abstractly.
4. 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

1. Well orders
2. Ordinal numbers
3. Transfinite induction and recursion
4. Zorn's lemma and the well ordering theorem

1. Well orders

The natural numbers $\mathbb{N}$ with the standard order $0 < 1 < 2 < \dots$ have the property that any nonempty subset of $\mathbb{N}$ has a unique smallest element. A general ordered set $(X, <)$ is said to be well ordered if it has this same property.

More precisely, an order $<$ on a set $X$ is a binary relation satisfying:

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

An ordered set $(X, <)$ is said to be well ordered if every nonempty subset $S \subseteq X$ has a smallest element, i.e., an element $s \in S$ with $s < s'$ for all non-$s$ elements $s' \in S.$ Note that properties 1 and 2 given above imply that this smallest element is unique; if there were two such elements $s_1$ and $s_2,$ then we would have $s_1 < s_2 < s_1,$ which would imply $s_1 < s_1,$ which is a contradiction.

Any well ordered set has many nice properties. A few important ones are:

1. Since $X$ is a subset of itself, it has a unique smallest element.
2. 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\}.$$
3. 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.

We will say that two well-ordered sets $(X, <), (Y, <)$ are order-isomorphic if there exists a bijection $f : X \rightarrow Y$ with

$$f(x) < f(x') \Leftrightarrow x < x'.$$

Interestingly, one can show that if two well ordered sets are order-isomorphic, then the isomorphism between them is unique! If $f_1$ and $f_2$ are two order-isomorphisms from $X$ to $Y,$ then $g \equiv f_1^{-1} \circ f_2$ is an order-isomorphism from $X$ to itself. We can show that $g$ must be the identity by showing that $g$ and $g^{-1}$ satisfy $g^{-1}(y) \geq y,$ $g(x) \geq x.$ This property is very general: we will show that any order-preserving map $g : X \rightarrow X$ satisfies $g(x) \geq x.$ Suppose, toward contradiction, that the set $A = \{x \in X | g(x) < x\}$ were nonempty; then it would have a smallest element $x_0.$ But $g(x_0) < x_0$ implies $g(g(x_0)) < g(x_0),$ which implies $g(x_0) \in A,$ but this contradicts the fact that $g(x_0)$ is smaller than $x_0,$ while $x_0$ is supposed to be the smallest element of $A.$

It should be apparent that any well order on a finite set $X$ of size $n$ is isomorphic to the standard order on the set $\{1, \dots, n\}.$ We can construct this isomorphism by mapping the smallest element of $X$ to $1$, its successor to $2$, and so on until all elements of the set are exhausted. However, it turns out that an infinite set can admit multiple non-isomorphic well orders. As an example, take the natural numbers defined by

$$\mathbb{N} = \{0, 1, 2,  \dots\}.$$

The standard order is $0 < 1 < 2 < \dots.$ We will define a second order, $\tilde{<},$ by

$$1 \tilde{<} 3 \tilde{<} 5 \tilde{<} \dots,$$

$$0 \tilde{<} 2 \tilde{<} 4 \tilde{<} 6 \tilde{<} \dots,$$

and by declaring $j \tilde{<} k$ whenever $j$ is even and $k$ is odd.

$\tilde{<}$ is clearly a well order, as any subset $S \subseteq \mathbb{N}$ has a smallest element with respect to $\mathbb{N}$: if $S$ contains no even numbers, then this smallest element coincides with the smallest element with respect to $<,$ while if $S$ contains even numbers, then the $\tilde{<}$-smallest element of $S$ is the $<$-smallest element of the subset of even numbers in $S.$

However, the well orders $<$ and $\tilde{<}$ cannot possibly be isomorphic. Given an element $x \in \mathbb{N},$ we can define its predecessor set by

$$\mathbb{N}_{< x} = \{y \in \mathbb{N} | y < x\},$$

and similarly for $\mathbb{N}_{\tilde{<} x}.$ In the standard order $<,$ every predecessor set has finite cardinality. But in the order $\tilde{<},$ the predecessor set of any odd number is infinite. This demonstrates that the two well orders cannot be isomorphic.

2. Ordinal numbers

At the end of the previous section, we observed that the cardinality of a well ordered set does not determine its 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.

The definition of ordinal numbers is a bit abstract, so it will be helpful to start with a bit of motivation. Our true goal in constructing the ordinal numbers is to have objects that we can use to label the elements of any well ordered set in increasing order. This might seem different from the goal stated above, where we said that ordinal numbers are canonical sets within each order type. Secretly, however, these two goals are the same.

To see this, we'll start by showing that for any well ordered set $X,$ and any two distinct elements $x, y \in X,$ the sets $X_{<x}$ and $X_{<y}$ have different order types. Since $x$ and $y$ are inequal, one must be smaller; without loss of generality, say $x < y.$ Then we have $X_{<x} \subsetneq X_{<y}$. If $f: X_{<y} \rightarrow X_{<x}$ were an order isomorphism, then because $x$ is in $X_{<y},$ we would have $f(x) < x$; this is a contradiction, since we explained in the previous section that any order-preserving map satisfies $f(x) \geq x$. So we see that to label the elements of $X$, it suffices to label them by the order types of their predecessor sets, i.e., to label each element by some canonical well ordered set.

However, our goal was not just to label the elements of $X,$ but to label them in 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.$

Since we want each ordinal number to be a set, there are two natural candidates for binary relations: set membership $\in,$ and proper set inclusion $\subsetneq.$ Von Neumann showed that choosing $\in$ for the binary relation leads to a very nice canonical class of well ordered sets, which is the one widely used today to define ordinal numbers. We can see how this works by declaring that the smallest ordinal number is the empty set $\varnothing$ with the trivial order, and defining successive ordinals recursively by making each ordinal the set of all previously defined ordinals.

To see how this works, let's declare the ordinal number $0$ to be the empty set $0 = \varnothing.$ By von Neumann's principle, the next ordinal number $1$ should be the set

$$1 = \{0\} = \{\varnothing\}.$$

The next ordinal number $2$ should be the set

$$2 = \{0, 1\} = \{\varnothing, \{\varnothing\} \}.$$

Continuing onward, we can define the $n$-th ordinal number as

$$n = \{0, \dots, n-1\}.$$

Clearly set membership gives the usual ordering on the natural numbers: $0 \in 1 \in \dots.$ But these aren't all the ordinals we can define: we can also define the first "non-natural" ordinal $\omega$ by the countable set

$$\omega = \{0, 1, \dots\} = \cup_n n.$$

But we don't need to stop there! We can also define an ordinal number $\omega+1$ by

$$\omega + 1 = \omega \cup \{\omega\} = \{0, 1, \dots; \omega\}.$$

This set is well ordered with respect to $\in,$ and has the same cardinality as the set of natural numbers, but it is not order-isomorphic to $\omega$, since in $\omega+1$ there is an element whose predecessor set is infinite, namely the element $\omega.$

If we wanted to, we could continue onward to define a countable family of ordinal numbers $\omega, \omega+1, \omega+2, \dots,$ and then a new, distinct ordinal number given by $2 \omega = \cup_{n} (\omega + n).$ But it will be more useful for us to give an abstract characterization of the ordinal numbers, by observing that each ordinal $\alpha$ we have defined thus far has the following two properties:

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

Any set $\alpha$ with these two properties will be called an ordinal number. We would like to show the following facts:

1. 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.$
2. 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.)
3. No two distinct ordinals are order-isomorphic.
4. Every well ordered set is order-isomorphic to an ordinal.

A few lemmas will be helpful.

First, one can observe that every element of an abstract ordinal number is itself an ordinal number. Given an ordinal number $\alpha,$ any $a \in \alpha$ is also a subset of $\alpha,$ which means that it is well ordered with respect to $\in.$ Furthermore, for any $a' \in a,$ we have $a' \in \alpha$ and so $a'$ is a subset of $\alpha$; but it is in fact a subset of $a,$ because $x \in a'$ implies $x \in a$ by the fact that $\in$ is transitive in $\alpha.$

Second, for any two ordinal numbers $\alpha$ and $\beta$ with $\alpha \subseteq \beta,$ we have either $\alpha = \beta$ or $\alpha \in \beta.$ To see this, we note that given $\alpha \subsetneq \beta,$ the set $\beta - \alpha$ is a nontrivial subset of $\beta$ and thus has a smallest element $\gamma.$ We now aim to show $\alpha = \gamma.$ For any element $x \in \alpha,$ we cannot have $x = \gamma$ since $\gamma \in \beta - \alpha,$ so because $\beta$ is well ordered we must have either $x \in \gamma$ or $\gamma \in x.$ But $x \in \alpha, \gamma \in x$ is impossible, since transitivity would imply $\gamma \in \alpha,$ which again would contradict $\gamma \in \beta - \alpha.$ This gives $\alpha \subseteq \gamma.$ Conversely, for any $x \in \gamma,$ we cannot have $x \in \beta - \alpha,$ since $\gamma$ is supposed to be the smallest element of $\beta - \alpha,$ but $x$ is smaller than $\gamma.$ This gives $\gamma \subseteq \alpha,$ hence $\alpha = \gamma,$ hence $\alpha \in \beta.$

Third, if $A$ is a class of ordinals, then the intersection $\cap A$ is also an ordinal in that class. Any element $x \in \cap A$ is in every ordinal in $A$, and is therefore a subset of every ordinal in $A$, and therefore is a subset of $\cap A.$ Furthermore, because $\cap A$ is a subset of an ordinal (any of the ordinals in $A$), it is well ordered with respect to $\in.$ Finally, we must have $\cap A \in A,$ since for each element $a \in A$ we have $\cap A \subseteq a,$ which by the previous lemma implies $\cap A \in a$ or $\cap A = a.$ But we cannot have $\cap A \in a$ for all $a \in A,$ because this would imply $\cap A \in \cap A,$ which is nonsense since $\cap A$ is a set. So we have $\cap A \leq a$ for all $a \in A,$ and $\cap A$ is the smallest ordinal in $A.$

We can now give rapid-fire, easy proofs of all the fundamental properties of ordinal numbers listed above. The third lemma above is exactly the statement that for any class $A$ of ordinals, $\cap A$ is in that class and is smaller, via the relation $\in,$ than any other ordinal in that class. For two ordinal numbers $\alpha, \beta$ with $\alpha \neq \beta$, this implies either $\alpha \cap \beta = \alpha$ and $\alpha \cap \beta \in \beta,$ or $\alpha \cap \beta = \beta$ and $\alpha \cap \beta \in \alpha.$ So we know that any two ordinals are comparable via $\in,$ which makes $\in$ an order on the class of ordinals. The third lemma above also tells us that $\in$ is a well order on the class of ordinals, since any class $A$ of ordinals has a smallest element $\cap A.$ 

If $\gamma$ is an ordinal and $\alpha \in \gamma$ is another ordinal, then $\alpha$ is a subset of $\gamma,$ and is in fact tautologically equal to its predecessor set $\gamma_{< \alpha}.$ In the previous section, we showed that predecessor sets of distinct elements cannot be order-isomorphic. So for $\alpha \neq \beta$ two distinct ordinals, we can show they are not order-isomorphic by showing that there exists some ordinal $\gamma$ containing both $\alpha$ and $\beta,$ which shows that $\alpha$ and $\beta$ cannot be order-isomorphic since they are equal to their predecessor sets within $\gamma$, which are not order-isomorphic. But this is easy: because $\alpha$ and $\beta$ are distinct, we have either $\alpha \in \beta$ or $\beta \in \alpha$; without loss of generality, say $\alpha \in \beta.$ But then $\alpha$ and $\beta$ are both contained in the set $\beta + 1 = \beta \cup \{\beta\},$ which is obviously an ordinal.

Finally, we would like to show that every well ordered set is order-isomorphic to a unique ordinal number. To start, consider a well ordered set $(X, <),$ and the predecessor sets $X_{< x}$ for $x \in X.$ Each of these predecessor sets is well ordered; a priori, some of them might be isomorphic to ordinal numbers, and some might not. Suppose, toward contradiction, that at least one of the $X_{<x}$ sets was not isomorphic to an ordinal number. Then there would be a least such element $x_0 \in X$ with this property.

So for any $x \in X_{<x_0}$ there exists an ordinal number $\alpha_x$ with $(X_{<x}, <) \cong \alpha_x.$ The map $x \mapsto \alpha_x$ maps $X_{<x_0}$ to the set $\{\alpha_x\}_{x \in X_{<x_0}}.$ We can show that this map is order-preserving: given $x < y < x_0,$ we have

$$\alpha_x \cong X_{<x} \cong \text{a predecessor set in $X_{<y}$} \cong \text{a predecessor set in $\alpha_y$}.$$

This tells us that $\alpha_x$ is isomorphic to a predecessor set in $\alpha_y$; by our previous lemmas, this implies $\alpha_x \in \alpha_y.$ So $X_{<x_0}$ is clearly order-isomorphic to the well ordered set $(\{\alpha_x\}_{x \in X_{<x_0}}, \in).$ But this is clearly an ordinal, since for any $\alpha_x$ we have

$$\alpha_x \cong X_{<x} \subset X_{<x_0} \cong \{\alpha_x\}_{x \in X_{<x_0}},$$

so every element of $\{\alpha_x\}_{x \in X_{<x_0}}$ is also a subset of the full set. This demonstrates that $X_{<x_0}$ is order-isomorphic to an ordinal number, which contradicts our assumption, and thus implies that within $X$, every set $X_{<x}$ is isomorphic to an ordinal number. But then we can construct an isomorphism from $X$ to $\{\alpha_x\}_{x \in X},$ which is an ordinal number by exactly the same arguments already given in this paragraph.

So every well ordered set $X$ is isomorphic to an ordinal number, and it must be unique because we have already shown that distinct ordinals have distinct order types. This lets us label the elements of any well ordered set in increasing order by labeling $x \in X$ by the unique ordinal number isomorphic to $X_{<x}.$

3. Transfinite induction and recursion

There are two kinds of ordinal numbers. To distinguish them, it will be helpful to first note that for any ordinal number $\alpha,$ the set

$$\cup \alpha \equiv \text{union of all elements of $\alpha$}$$

is always an ordinal. This is easy to show: since $\cup \alpha$ is a set of ordinals it is automatically well ordered with respect to $\in.$ So to show that it is an ordinal, you only need to show that elements of $\cup \alpha$ are subsets of $\cup \alpha,$ but this is obvious since the elements of $\alpha$ are themselves ordinals.

Because each element of $\alpha$ is a subset of $\alpha,$ we have $\cup \alpha \subseteq \alpha,$ which by one of our lemmas in the previous section implies either $\cup \alpha = \alpha$ or $\cup \alpha \in \alpha.$ An ordinal number will be called a limit ordinal if it has the property

$$\alpha = \cup \alpha,$$

and it will be called a successor ordinal if it has the property

$$\cup \alpha \in \alpha.$$

The second type is called a "successor ordinal" because whenever this is the case, we have

$$\alpha = \inf\{\beta | \cup \alpha \in \beta \} \equiv \cup \alpha + 1,$$

so $\alpha$ is the successor of some other ordinal number. To see this, we note that $\alpha$ is certainly in the set $\{\beta | \cup \alpha \in \beta\}$, and if that set had a different infimum $\gamma,$ then we would have $\cup \alpha \in \gamma \in \alpha,$ which would imply $\gamma \subseteq \alpha,$ which would imply $\gamma \subseteq \cup \alpha,$ but this contradicts $\cup\alpha \in \gamma.$ 

The name is justified also by the fact that no limit ordinal $\alpha$ can have the property $\alpha = \beta + 1$, since $\alpha = \beta + 1 = \beta \cup \{\beta\}$ implies $\cup \alpha = \beta \neq \beta + 1 = \alpha,$ so $\alpha$ cannot be a limit ordinal.

In a well ordered set $X$ that is labeled by the natural numbers, $X = \{x_j\},$ we can prove that every element of the set has a given property by showing that $x_{0}$ has the desired property, and that $x_{j}$ has the desired property whenever $x_{j-1}$ has the desired property. This is the standard "proof by induction." We would like to be able to apply the same logic to a well ordered set that cannot be labeled by the natural numbers. Given our discussion about "limit ordinals" versus "successor ordinals," we might expect the following to be true:

• 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

Let $P$ be a partially ordered set; this is a set with an order $<$ satisfying $p \not< p$ and $p < q < r \Rightarrow p < r,$ but where two arbitrary elements need not be comparable. A totally ordered subset of $P$ is one in which all elements are pairwise comparable.

Suppose further that every totally ordered subset of $P$ has an upper bound, i.e., if $S$ is a totally ordered subset then there exists some $\sup{S} \in P$ with $\sup{S} \geq s \in S.$ Zorn's lemma then says that $P$ has a maximal element, i.e., there exists some $p_* \in P$ so that there is no $p \in P$ with $p_* < p.$

This can be proven using the axiom of choice and transfinite induction. We assume, toward contradiction, that $P$ has no maximal elements. Then for every totally ordered subset $S \subseteq P,$ there exists some element $G(S)$ with $G(S) > \sup S.$ The axiom of choice needs to be invoked to define $G(S)$ as a function on all totally ordered subsets.

We now define a map from ordinal numbers to $P$ by transfinite recursion; pick $p_0 \in P$ arbitrarily, and for any other ordinal $\alpha$ define

$$p_{\alpha} = G(\{p_{\beta} | \beta < \alpha\}).$$
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.$

The well ordering theorem, which can be viewed as a consequence of Zorn's lemma, says that any set admits a well order. To prove it, we consider a set $X$, and consider the set of well orderings of subsets of $X$. We can put a partial order on this "set of well orderings of subsets" by saying that two well-ordered subsets $(S_1, <_1), (S_2, <_2)$ satisfy

$$(S_1, <_1) < (S_2, <_2)$$

if and only if $S_1 \subsetneq S_2$ and $<_1$ agrees with $<_2$ on $S_1.$ For any totally ordered family of such well ordered subsets, their union is a well ordered subset of $X$ containing all of them; thus we have constructed a partially ordered set that meets the condition of Zorn's lemma, that every totally ordered subset has an upper bound. We conclude that there is a maximal element in this partially ordered set; in order for it to be maximal, the set must be $X$, and by definition the associated order is a well order.