Ordinals

Math 320: Set Theory (David Pierce)

May 12, 2007

Preface

This is a summary of ordinals, as we are studying them. You should be able to give proofs by transfinite induction of the basic properties of ordinal arithmetic (addition, multiplication, and exponentiation of ordinals). If you omit the limit steps from these proofs, then you have proved the same properties of natural numbers, by ordinary induction.

1 Introduction

1.1. By definition, an ordinal (or ordinal number) is a transitive set that is well-ordered by membership (∈). Ordinals are denoted by α, β, γ, δ, …

1.2. The class of ordinals is denoted by ON. This is a transitive class that is well-ordered by membership. Therefore it is a proper class: it is not a set. On ON, membership is the same as proper inclusion (⊂) and may be denoted by <. So each ordinal is the set of its predecessors in ON: that is, α = {x ∈ ON: x < α}.

1.3. The class ON:

(a) contains ∅, which is also denoted by 0 and called zero;

(b) is closed under the successor-operation, x ↦ x′, where x′ = x∪{x};

(c) contains the union of each of its subsets.

1.4. The union of a subset of ON is also its supremum (least upper bound):

⋃ a = sup(a).

If a = {F (x): φ(x)}, then sup(a) can be written as sup_{φ(x)} F (x).

1.5. There are three kinds of ordinals:

(a) zero; (b) successors, namely, ordinals α′;

(c) limits (non-zero non-successors). The successor of 0 is 1; the successor of 1 is 2; and so on. The first limit is ω, the set of natural numbers, which is the smallest set containing 0 and closed under x ↦ x′. In these notes, λ will always denote a limit, and n will always denote a natural number. So α < λ ⇒ α′ < λ, which implies

sup(λ) = λ.

Also, sup(0) = 0, but sup(α′) = α.

2 Induction and recursion

2.1. Proof by transfinite induction is possible in ON: if C ⊆ ON, and

(a) 0 ∈ C (the base step),

(b) α ∈ C ⇒ α′ ∈ C (the successor step),

(c) λ ⊆ C ⇒ λ ∈ C (the limit step), then C = ON. (There are also alternative formulations of this procedure.) 2.2. Definition by transfinite recursion is possible on ON: if α is an ordinal, and F is a singulary operation on ON, and G: P(ON) → ON, then there is a unique singulary operation H on ON such that

(a) H(0) = α,

(b) H(β′) = F (H(β)),

(c) H(λ) = G(H[ λ]). (There are also alternative versions of this kind of definition.)

3 Operations

3.1. By recursion in the second argument, we can define the binary operations of addition, multiplication, and exponentiation on ON:

α + 0 = α,  α · 0 = 0,  α^{0} = 1,
α + β′ = (α + β)′,  α · β′ = α · β + α,  α^{β′} = α^{β} · α,
α + λ = sup_{x<λ} (α + x);  α · λ = sup_{x<λ} (α · x);  α^{λ} = sup_{0<x<λ} (α^{x}).

(Alternative definitions in terms of order types are also possible.)

3.2. A singulary operation F on ON is normal if:

(a) α < β ⇒ F (α) < F (β) (that is, F is strictly order-preserving);

(b) F (λ) = sup_{x<λ} F (x). If F is normal, and a ⊆ ON, then we can show

(c) F (sup(a)) = sup_{x∈a} F (x). 3.3. By definition, the operations x ↦ α + x and x ↦ α · x satisfy part (b) of the definition of normality; so does x ↦ α^{x}, if α ≠ 0. However, the successor-operation is not normal, even though it satisfies (a); indeed, since α < λ ⇒ α′ < λ, we have {x′: x < λ} ⊆ λ, so

sup_{x<λ}(x′) = sup{x′: x < λ} ⩽ sup(λ) = λ < λ′.

4 Arithmetic

4.1. By induction, we can establish the basic properties of:

(a) addition:

i. β < γ ⇒ α + β < α + γ, so x ↦ α + x is normal; ii. addition is associative: α + (β + γ) = (α + β) + γ; iii. 0 + α = α; iv. α ⩽ β ⇒ α + γ ⩽ β + γ;

(b) multiplication:

i. if 0 < α, then β < γ ⇒ α · β < α · γ, so x ↦ α · x is normal; ii. multiplication is associative: α · (β · γ) = (α · β) · γ; iii. multiplication from the left distributes over addition: α·(β +γ) =

α · β + α · γ; iv. 1 · α = α; v. α ⩽ β ⇒ α · γ ⩽ β · γ;

(c) exponentiation:

i. if 1 < α, then β < γ ⇒ α^{β} < α^{γ}, so x ↦ α^{x} is normal; ii. α^{β+γ} = α^{β} · α^{γ}; iii. (α^{β})^{γ} = α^{β·γ}; iv. 0 < α ⇒ 0^{α} = 0; v. 1^{α} = 1;

vi. α ⩽ β ⇒ α^{γ} ⩽ β^{γ}.

4.2. We now have the following initial segment of ω; every entry is a limit if it is not of the form α + n, where n ∈ ω:

0, 1, 2, …; ω, ω + 1, ω + 2, …; ω + ω = ω · 2, ω · 2 + 1, …; ω · 3, …;

ω · ω = ω^{2}, ω^{2} + 1, …; ω^{2} + ω, …; ω^{2} + ω · 2, …; ω^{2} · 2, …; ω^{3}, …;

ω^{ω} , …; ω^{ω+1} , …; ω^{ω·2} , …; ω^{ω^{2}} , …; ω^{ω^{ω}} , …

4.3 Theorem and Definition. If α ⩽ β, then the equation

α + x = β

has a unique solution, which can be denoted by

β − α.

Proof. If there is some solution, then its uniqueness follows, since x ↦ α + x is strictly order-preserving. We prove existence by induction on β:

(a) If β = 0 and α ⩽ β, then α = 0, so α + 0 = β.

(b) Suppose the claim holds when β = γ. Say α ⩽ γ′. If α = γ′, then α + 0 = γ′. If α < γ′, then α ⩽ γ, so γ − α exists, and then

α + (γ − α)′ = (α + (γ − α))′ = γ′.

Thus the claim holds when β = γ′.

(c) Suppose the claim holds when β < λ. Say α ⩽ λ. If α = λ, then α + 0 = λ. Now suppose α < λ. We shall show

α + sup{x: α + x < λ} = λ.  (∗)

Since x ↦ α + x is normal, we have

α + sup{x: α + x < λ} = sup{α + x: α + x < λ} ⩽ sup(λ) = λ.

For the reverse inequality, suppose α ⩽ γ < λ. Then γ − α exists and is a member of {x: α + x < λ}, so

γ − α ⩽ sup{x: α + x < λ},
γ = α + (γ − α) ⩽ α + sup{x: α + x < λ}.

Therefore λ ⩽ α + sup{x: α + x < λ}, and (∗) holds. This completes the induction and the proof.

4.4. Addition and multiplication on ω have properties that fail on ON. As we can prove by induction, on ω:

(a) addition is commutative: n + m = m + n;

(b) multiplication is commutative: n · m = m · n;

(c) multiplication distributes from the right: (n + m) · k = n · k + m · k. However, on ON,

(a) addition does not commute: 1 + ω < ω + 1, since 1 + ω = sup{1 + x: x ∈ ω} ⩽ sup(ω) = ω < ω + 1;

(b) multiplication does not commute: 2 · ω < ω · 2, since 2 · ω = sup{2 · x: x ∈ ω} ⩽ sup(ω) = ω < ω · 2,

(c) multiplication does not distribute: (1 + 1) · ω < 1 · ω + 1 · ω.

5 Base ω

5.1. The remainder of these notes investigates the possibility of computations with ordinals. 5.2 Lemma. β < α ⇒ ω^{β} + ω^{α} = ω^{α}.

5.3 Lemma. β + α = α ⇒ (α + β) · γ = \begin{cases}α · γ + β, & if γ is a successor; \\ α · γ, & if γ is a limit or 0. \end{cases}

5.4. An algorithm for writing a positive natural number n in decimal or “base-ten” notation is the following:

(a) Find k such that 10^{k} ⩽ n < 10^{k+1};

(b) find n_{0} such that 10^{k} · n_{0} ⩽ n < 10^{k} · (n_{0} + 1);

(c) find n_{1} such that 10^{k} · n_{0} + 10^{k−1} · n_{1} ⩽ n < 10^{k} · n_{0} + 10^{k−1} · (n_{1} + 1);

(d) and so on. Then

n = 10^{k} · n_{0} + 10^{k−1} · n_{1} + ⋯ + n_{k} = ∑_{i=0}^{k} 10^{k−i} · n_{i},

and we may write n simply as n_{0} n_{1} ⋯ n_{k}. A similar procedure allows us to write any ordinal in base ω. We first need to know that sufficiently large powers of ω can be found:

5.5 Lemma. α ⩽ ω^{α}, so α < ω^{α′}.

5.6 Lemma. If 0 < α, then there are (unique) β and n such that

ω^{β} · n ⩽ α < ω^{β} · (n + 1).

Proof. If α ∈ ω, then β = 0 and n = α. Now assume ω ⩽ α. By the previous lemma, the class {x: ω^{x} ⩽ α} is bounded above by α; so the class is a subset of α′; so the class is a set. Let β be its supremum. Then 1 ⩽ β. By normality of x ↦ α^{x}, we have

ω^{β} = sup({ω^{x}: ω^{x} ⩽ α}) ⩽ α.

Now, α < ω^{β′} = ω^{β} · ω. By normality of x ↦ ω^{β} · x, there is a greatest n such that ω^{β} · n ⩽ α. Then α < ω^{β} · (n′) = ω^{β} · n + ω^{β}. So β and n are as desired. (Uniqueness is straightforward.)

5.7 Theorem. For every positive ordinal α, for some positive k in ω, there are ordinals β_{0}, …, β_{k}, and there are positive natural numbers n_{0}, …, n_{k−1} and a natural number n_{k}, such that

α = ω^{β_{0}} · n_{0} + ⋯ + ω^{β_{k}} · n_{k},

where β_{k} < ⋯ < β_{0}.

Proof. Apply the previous lemma repeatedly, to α, and then to α − ω^{β} · n, and so on. The process must end, since there is no infinite strictly descending sequence of ordinals.

5.8. We can add and multiply ordinals in base ω; for example,

(ω^{ω+1} · 3 + ω^{6} · 4 + 1) · (ω^{ω^{2}} · 2 + 3)

= (ω^{ω+1} · 3 + ω^{6} · 4 + 1) · (ω^{ω^{2}} · 2) + (ω^{ω+1} · 3 + ω^{6} · 4 + 1) · 3

= (ω^{ω+1} · 3) · (ω^{ω^{2}} · 2) + (ω^{ω+1} · 3) · 3 + ω^{6} · 4 + 1
= ω^{ω+1} · (3 · ω^{ω^{2}} ) · 2 + ω^{ω+1} · (3 · 3) + ω^{6} · 4 + 1
= (ω^{ω+1} · ω^{ω^{2}} ) · 2 + ω^{ω+1} · 9 + ω^{6} · 4 + 1
= (ω^{ω+1+ω^{2}} ) · 2 + ω^{ω+1} · 9 + ω^{6} · 4 + 1
= (ω^{ω^{2}} ) · 2 + ω^{ω+1} · 9 + ω^{6} · 4 + 1.