MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Well-Orders and Ordinals

1 Transfinite Induction and Recursion

Definition. A linearly ordered set ⟨W, <⟩ is well-ordered if every non-empty subset A ⊆ W has a least element.

When t ∈ W, let us write seg t = {x ∈ W | x < t}.

Theorem 1 (Transfinite Induction Principle). Let ⟨W, <⟩ be a well-ordered set. Suppose B ⊆ W is a subset such that for all t ∈ W,

seg t ⊆ B ⇒ t ∈ B.

Then B = W.

Proof. Let A = W − B. Suppose A is non-empty. Then A has a least element t. But this means that for all x ∈ t, x ∉ A, thus seg t ⊆ W −A = B. By hypothesis, this implies t ∈ B, contradicting t ∈ A. Thus, A is empty after all, and B = W.□

The way the induction principle is usually used is to show that all elements of W have a certain property. One forms the set B of all those elements of W that have the property. The induction step is to show that if all x < t have the property, then t has the property as well. Unlike with ordinary induction, there is no separate base case.

Theorem 2 (Transfinite Recursion Theorem Schema). For any formula γ(x, y), the following is a theorem: Assume ⟨W, <⟩ is a well-ordering. Assume that for any set x there is a unique set y such that γ(x, y). Then there exists a unique function F with domain W such that for all t ∈ W

γ(F ↾ seg t, F (t)).

Proof. See Enderton, p.180ff. The proof uses the replacement axiom. □

More informally, the transfinite recursion theorem tells us that to define a function on a well-ordered set ⟨W, <⟩, it suffices to give a definition of each function value F (t) in terms of all the previous function values F (x) where x < t.

2 The Axiom of Regularity

Axiom of Regularity Every non-empty set A has a member m ∈ A such that m ∩ A = ∅.

In other words, the regularity axioms asserts that every non-empty set has a member that is minimal with respect to the membership relation. Notice that m∩A = ∅ if and only if, for all x ∈ A, x ∉ m.

The regularity axiom implies that the universe of sets is well-founded, i.e., there is no infinite descending chain of sets. In other words, there is no sequence (s_{n})_{n∈ω} of sets such that

… ∈ s_{3} ∈ s_{2} ∈ s_{1} ∈ s_{0}.

This is stated more precisely in the following proposition:

Proposition 3. If regularity holds, then there is no function s with domain ω such that for all n ∈ ω, s_{n+1} ∈ s_{n}.

Proof. Assume to the contrary that there was such a function s. Let A = ran s = {s_{n} | n ∈ ω}. Then A is non-empty, so by regularity, there must be some m ∈ A with m ∩ A = ∅. But we must have m = {_{}}n for some n ∈ ω, and thus s_{n+1} ∈ m ∩ A, a contradiction. □

Remark. If we assume the axiom of choice, then the converse is also true: If regularity fails, then there exists an infinite descending chain of sets. Because, if regularity fails, then there is some non-empty set A such that for all m ∈ A, m ∩ A ≠ ∅. Let R ⊆ A × A be the relation defined by mRx iff x ∈ m ∩ A. By assumption, dom R = A. So by the axiom of choice, there exists a function F : A → A with F ⊆ R. The latter inclusion implies that mRF (m) holds for all m ∈ A, and thus, that F (m) ∈ m for all m ∈ A, by definition of R. Since A is non-empty, we can pick an element x_{0} ∈ A. By ordinary recursion, we can define a function s : ω → A such that

\begin{aligned}s_{0} & = & x_{0}, \\ s_{n+1} & = & F (s_{n}). \end{aligned}

It follows that s_{n+1} = F (s_{n}) ∈ s_{n} for all n ∈ ω, i.e., (s_{n})_{n∈ω} is an infinite descending chain.

Corollary 4. In the presence of regularity, there is no set x with x ∈ x. Also, there are no sets a, b with a ∈ b and b ∈ a. More generally, there are no sets a_{1}, a_{2}, …, a_{n} such that a_{1} ∈ a_{2} ∈ … ∈ a_{n} ∈ a_{1}.

Proof. Each such situation would give rise to an infinite descending chain of sets, contradicting Proposition 3. □

The axiom of regularity states that there is always a minimal set in each non-empty set. It follows easily that there is always a minimal set in each non-empty class:

Proposition 5 (Minimality Principle for Sets). Suppose ϕ(x) is a property of sets that holds of at least one set. Then there is a minimal m such that ϕ(m) holds. In other words, there is a set m such that ϕ(m) and such that for all x ∈ m, ¬ϕ(x).

Proof. By assumption, there is some set a with ϕ(a). Let C be a transitive set containing a (such a set exists by Problem 7.7). Let A = {x ∈ C | ϕ(x)}. Then a ∈ A, thus A is a non-empty set and we can apply the regularity axiom to A to obtain some m ∈ A with m ∩ A = ∅. Then by definition of A, we have ϕ(m). Also, m is minimal with this property, because for all x ∈ m, we have x ∈ C but x ∉ A, from which it follows that ¬ϕ(x). □

From our experience with the natural numbers and with well-orders, we have learned that induction principles and minimality principles are closely related. So we would expect that our minimality principle for sets gives rise to some sort of induction principle for sets. This is indeed the case, as the following proposition shows:

Proposition 6 (Set Induction Principle). Suppose ϕ(x) is a property of sets such that for all sets y,

(∀x ∈ y.ϕ(x)) ⇒ ϕ(y).

Then the property ϕ(x) holds of all sets.

Proof. Suppose, to the contrary, that ϕ(x) does not hold for all sets. Then, by the minimality principle, there is a minimal m for which ¬ϕ(m). But this means that for all x ∈ m, ϕ(x), which implies ϕ(m) by assumption. This is a contradiction, and thus ϕ(x) holds for all x. □

From now on, we will assume the axioms of replacement and regularity unless otherwise stated.

3 Ordinals

Definition. An ordinal number, or simply ordinal, is a transitive set of transitive sets.

Proposition 7 (Trichotomy for Ordinals). If α and β are ordinals, then exactly one of the possibilities α ∈ β or α = β or β ∈ α holds.

Proof. First, notice that by Corollary 4, at most one of the three possibilities can hold. Let us write trich(α, β) for the statement

α ∈ β ∨ α = β ∨ β ∈ α.

It suffices that show that for all ordinals α and β, trich(α, β) holds. Suppose this was not the case. Then by the minimality principle, we can find a minimal α such that for some β, trich(α, β) fails. Using the minimality principle again, we can find a minimal β such that for the chosen α, trich(α, β) fails. With this choice of α and β, we have that for all α′ ∈ α, trich(α′, β) (by minimality of α), and for all β′ ∈ β, trich(α, β′) (by minimality of β). We will derive a contradiction by showing that trich(α, β) holds after all. If α = β, then we are done. Otherwise, there are two cases:

Case 1: There exists α′ ∈ α such that α′ ∉ β. By trich(α′, β), we have β ∈ − α′, and thus β ∈ α by transitivity of α. Case 2: There exists β′ ∈ β such that β′ ∉ α. By trich(α, β′), we have α ∈ − β′, and thus α ∈ β by transitivity of β.

In any case, we have shown that trichotomy holds for α and β, which is the desired contradiction. □

Corollary 8. For ordinals α and β, one has α ∈ β if and only if α ⊂ β.

Proof. If α ∈ β, then α ⊆ β because β is transitive. Moreover, the inclusion is strict since α ≠ β by regularity. This shows the left-to-right implication. For the converse, assume that α ⊂ β. Then β ≠ α. Also, β ∈ α is impossible, or else we would have β ∈ β. Thus, by trichotomy, the only remaining possibility is α ∈ β. □

Lemma 9. If α is an ordinal and x ∈ α, then x is an ordinal.

Proof. Let x ∈ α. Then x is transitive since α is a set of transitive sets. Also, for any y ∈ x, one has y ∈ α since α is transitive; hence y is transitive as well. □

Theorem 10 (Burali-Forti). The class of ordinals is not a set.

Proof. Suppose there was a set O such that α ∈ O iff α is an ordinal. Then O is transitive by Lemma 9. Also, the elements of O are transitive, and thus O is an ordinal itself, which implies O ∈ O, a contradiction. □

Remark. Any non-empty class of ordinals has a least element.

Proof. By the minimality principle, any non-empty class of ordinals has a minimal element. By trichotomy, such a minimal element is least. □

Proposition 11. α is an ordinal if and only if α is a transitive set that is wellordered by ∈.

Proof. In the left-to-right direction, we already know that if α is an ordinal, then it is transitive; it remains to show that it is well-ordered by ∈. Transitivity: If x ∈ y ∈ z ∈ α, then x ∈ z since z is a transitive set. Trichotomy: By Lemma 9 and Proposition 7. Thus, ∈ defines a linear order on α. Well-orderedness: Consider any non-empty subset A ⊆ α. Then by regularity, there exists some x ∈ A with x ∩ A = ∅. This implies that for all y ∈ A, y ∉ x, and thus x ∈ − y by trichotomy. Thus, x is minimal in A.

For the right-to-left direction, assume that α is a transitive set that is well-ordered by ∈. We must show that any x ∈ α is transitive. So consider z ∈ y ∈ x. Since α is transitive, we have x, y, z ∈ α, and thus, by transitivity of the ∈-relation on α (which is part of the definition of a well-order), z ∈ x. □

Remark. Some authors, such as Enderton, define ordinals without assuming the regularity axiom. In this case, one may take Proposition 11 as the definition of the ordinals.

The following lemma provides us with some examples of ordinals:

Lemma 12. (1) ∅ is an ordinal.

(2) If α is an ordinal, then α^{+} = α ∪ {α} is an ordinal.

(3) If D is a set of ordinals, then ⋃ D is an ordinal.

Proof. Each case is trivial to check directly from the definition of an ordinal as a transitive set of transitive sets. □

In particular, it follows that each natural number n is an ordinal. These are the only finite ordinals. The next ordinal after that is ω, the set of natural numbers. Next, one has ω^{+}, ω^{++}, and so on. The union of these ordinals is denoted as ω ·2. Here is a list of the first couple of ordinals, in increasing order:

0, 1, 2, …, ω, ω^{+}, ω^{++}, … ω · 2, (ω · 2)^{+}, … ω · 3, …, ω · 4, …

The union of all the ordinals in this list is denoted ω · ω or ω^{2}. One can continue in a similar fashion to ω^{3}, ω^{4}, and so forth. Taking the union of all these ordinals, one gets ω^{ω}, and one can continue to ω^{ω^{ω}}, and so on. We will define these operations on ordinals more precisely later on, once we know a little more about their properties.

We have shown that each ordinal is well-ordered by the ∈-relation. Our next goal is to prove a converse: each well-ordered set is isomorphic to some ordinal. Recall that an isomorphism between ordered sets ⟨A, <_{A}⟩ and ⟨B, <_{B}⟩ is a one-to-one and onto function f : A → B such that x <_{A} y iff f(x) <_{B} f(y), for all x, y ∈ A.

Definition. The ∈-image (pronounced: epsilon-image) of a well-ordered set ⟨W, <⟩ is defined as follows: Let E be the unique function with domain W such that for all t ∈ W,

E(t) = ran(E↾ seg t) = {E(x) | x < t}.

A unique such function exists by the transfinite recursion theorem. The ∈-image of ⟨W, <⟩ is defined to be ran E = {E(t) | t ∈ W }.

Lemma 13. Let α be the ∈-image of a well-ordered set ⟨W, <⟩. Then the following hold:

(1) For all s, t ∈ W, s < t iff E(s) ∈ E(t).

(2) E maps W one-to-one onto α.

(3) α is an ordinal.

Proof. (1) The left-to-right implication follows by definition of E(t) = {E(s) | s < t}. The right-to-left implication follows by trichotomy: if E(s) ∈ E(t), then t ⩽ s is impossible. (2) It is clear that E is onto, since α was defined to be the range of E. The fact that E is one-to-one follows from (1), because if s ≠ t, then s < t or t < s, and thus E(s) ∈ E(t) or E(t) ∈ E(s). In either case, E(s) ≠ E(t). (3) α is transitive, because if x ∈ y ∈ α, then y = E(t) for some t ∈ W, and thus x ∈ E(t) = {E(s) | s < t}. Hence, x = E(s) for some s ∈ W, thus x ∈ α. Also, (1) and (2) show that ⟨α, ∈⟩ is isomorphic to ⟨W, <⟩, and thus α is well-ordered by ∈. It follows from Proposition 11 that α is an ordinal. □

Corollary 14. Any well-ordered set ⟨W, <⟩ is isomorphic to some ordinal α. Namely, one can take α to be the ∈-image of ⟨W, <⟩. □

Is it true that every well-ordered set is isomorphic to a unique ordinal? This is indeed true, because of the following fact:

Lemma 15. Two ordinals are isomorphic if and only if they are equal. The only isomorphisms between ordinals are identity maps.

Proof. Suppose α and β are ordinals and f : α → β is an isomorphism. We first claim that f(t) = t for all t ∈ α. We prove this by transfinite induction. So take t ∈ α and suppose, as an induction hypothesis, that f(x) = x for all x ∈ t. We claim that f(t) = {f(x) | x ∈ t}. The right-to-left inclusion holds because x ∈ t implies f(x) ∈ f(t), since f is an isomorphism. For the left-to-right inclusion, take y ∈ f(t). Then y ∈ β, since β is transitive. Thus, y = f(x) for some x ∈ α, since f is onto. Thus, f(x) ∈ f(t), and hence x ∈ t since f is an isomorphism. It follows that y ∈ {f(x) | x ∈ t}. Now we have the following:

f(t) = {f(x) | x ∈ t} by what we have just shown
= {x | x ∈ t}  by induction hypothesis
= t.

This finishes the induction step. It follows that f(t) = t for all t ∈ α. But now it follows that α = β since f is onto β. Thus, f is the identity map from α to itself. □

Corollary 16. (1) Every well-ordered set ⟨W, <⟩ is isomorphic to a unique ordinal α.

(2) Two well-ordered sets are isomorphic iff the have the same ∈-image.

(3) Each two well-ordered sets are either isomorphic, or one is isomorphic to an initial segment of the other.

(4) Every ordinal is equal to its own ∈-image.

Proof. (1) We know from Corollary 14 that every well-ordered set ⟨W, <⟩ is isomorphic to some ordinal α. For uniqueness, assume that ⟨W, <⟩ is isomorphic to two ordinals α and β. Then α is also isomorphic to β, and thus α = β by Lemma 15. (2) “⇒”: If two well-ordered sets are isomorphic, then their ∈-images must also be isomorphic, and thus equal by Lemma 15. “⇐”: If two well-ordered sets have equal ∈-images, then they must be isomorphic, since each of them is isomorphic to its ∈-image. (3) If W and V are well-ordered sets, then they are isomorphic to unique respective ordinals α and β. If α = β, then W and V are isomorphic by (2). Otherwise, by trichotomy and Corollary 8, either α ⊂ β or β ⊂ α. In the first case, W is isomorphic to an initial segment of β (namely, α), and thus to an initial segment of V. The second case is symmetric. (4) Every ordinal α is isomorphic to its ∈-image by Corollary 14. But since both α and its ∈-image are both ordinals, they must then be equal by Lemma 15. □