ORDINAL NUMBERS

1. Linear and partial ordering

Definition 1. A binary relation < on a set P is called a partial ordering of P if
for all elements p, q and r of P ,
(i) p ≮ p;
(ii) if p < r and r < q, then p < q.
An ordered (P, <) is called a partially ordered set if < is a partial ordering on a
set P .
We usually denote (p < q) ∨ (p = q) by p ≤ q. For convenience, instead of (P, <),
we shall frequently call P the partially ordered set when no confusion may arise.
Definition 2. A partial ordering < of P is called a linear ordering if for all elements
p and q of P , exactly one of the following cases is true:
p < q or p = q or q < p .
We observe that if p and q are members of a linearly ordered set P such that p ≤ q
and q ≤ p, then p = q.
Definition 3. Let (P, <) be a partially ordered set, X be a non-empty subset of
P and a be an element of P . Then we call a
(i) a maximal element of X if a ∈ X and (∀x ∈ X)a ≮ x;
(ii) a minimal element of X if a ∈ X and (∀x ∈ X)x ≮ a;
(iii) the maximum of X (denoted by a = max X) if a ∈ X and (∀x ∈ X)x ≤ a;
(iv) the minimum of X (denoted by a = min X) if a ∈ X and (∀x ∈ X)a ≤ x;
(v) an upper bound of X if (∀x ∈ X)x ≤ a;
(vi) a lower bound of X if (∀x ∈ X)a ≤ x;
(vii) the supremum (denoted by a = sup X) of X if a is the least upper bound
of X;
(viii) the infimum of X (denoted by a = inf X) if a is the greatest lower bound
of X.
Suppose that (P, <) and (Q, ≺) are partially ordered sets. Then f : P → Q is
said to be order-preserving if x < y implies f (x) < f (y). If P and Q are linearly
ordered, then f is said to be increasing.
An bijection f from P onto Q is called an isomorphism of P onto Q if both f
and f −1 are order-preserving; (P, <) is then isomorphic to (Q, ≺). An isomorphism
of P onto itself is called an automorphism of (P, <).

2. Well-ordering
Definition 4. A linear ordering < of a set P is called a well-ordering if every
non-empty subset of P has a minimum.
Lemma 1. Suppose that (W, <) is a well-ordered set and f : W → W is an in-
creasing function, then f (x) ≥ x for all x ∈ W .
1
2 ORDINAL NUMBERS

Proof. If the set X = {x ∈ W : f (x) < x} is non-empty, then X has a minimum y.

Since f is increasing, we have f (f (y)) < f (y), a contradiction. 
Corollary 1. The only automorphism of a well-ordered set is the identity function.
Corollary 2. If two well-ordered sets W1 and W2 are isomorphic, then the iso-
morphism is unique.
Let W be a well-ordered set and u be a member of W . Put
W (u) = {x ∈ W : x < u} .
Then W (u) is called an initial segment of W given by u.
Lemma 2. No well-ordered set is isomorphic to an initial segment of itself.
Proof. Given a well-ordered set W and u ∈ W , let f : W → W be a function onto
W (u). Then f (u) < u. By Lemma 1, f cannot be increasing. 
Theorem 1. If W1 and W2 are non-empty well-ordered sets, then exactly one of
the following statements holds:
(a) W1 is isomorphic to W2 ;
(b) W1 is isomorphic to an initial segment of W2 ;
(c) W2 is isomorphic to an initial segment of W1 .
Proof. In view of Lemma 2, the three statements are mutually exclusive. To show
that one must hold, put
f = {(x, y) ∈ W1 × W2 : W1 (x) is isomorphic to W2 (y)} .
By Lemma 2, f is an injective function. Since W1 and W2 have minimums, f is
non-empty. If h is an isomorphism between W1 (x) and W2 (y) and u < x, then
its restriction h|W1 (u) is an isomorphism onto W2 (h(u)). Hence (u, h(u)) ∈ f
and f (u) < f (x). Similarly, if v < y, then (h−1 (v), v) ∈ f and f −1 (v) < x. We
conclude that f is an isomorphism, its domain is either W1 or an initial segment
of W1 , and its range is either W2 or an initial segment of W2 .
Suppose, for contradiction, that the domain and range of f are proper subsets
of W1 and W2 respectively. Let a and b be the least element of W1 − dom(f )
and W2 − ran(f ) respectively. Then W1 (a) is isomorphic to W2 (b), a contradiction.


3. Ordinal numbers
Definition 5. A set T is said to be transitive if every element of T is a subset of
T.
Definition 6. A set is called an ordinal number or an ordinal if it is transitive and
well-ordered by ∈.
The class of ordinals is denoted by O.
Lemma 3. (a) the empty set 0 = ∅ is an ordinal;
(b) If β is an ordinal and α ∈ β, then α is the initial segment of β given by α,
and α is an ordinal;
(c) If α 6= β are different ordinals and α ⊂ β, then α ∈ β;
(d) If α and β are ordinals, then either α ⊂ β or β ⊂ α.
 ORDINAL NUMBERS 3

Proof. (a) By definition.

(b) That α ⊂ β(α) and β(α) ⊂ α are by definition of ordinals. Since α ⊂ β,
we have γ ∈ β for all γ ∈ α. Given θ ∈ γ, similar reasoning leads to θ ∈ β.
Since β is linearly ordered by ∈, we conclude that θ ∈ α. Hence γ ⊂ α,
establishing the transitivity of α. Since α is well-ordered by ∈ as a subset
of β, it is an ordinal.
(c) Let γ be the minimum of β − α. By definition and (b) we have (β − α) ∩ γ =
∅, so γ ⊂ α. Suppose, for contradiction, that α − γ is non-empty and has
an element ξ. Since β is an ordinal, either γ = ξ or γ ∈ ξ ⊂ α for some
ξ ∈ α. But this leads to γ ∈ α, which is impossible because γ ∈ β − α.
Hence α = γ.
(d) Put γ = α ∩ β. Since θ ∈ α ∩ β implies θ ⊂ α ∩ β, the set γ is transitive.
Since both α and β are well-ordered by ∈, so is γ. Hence γ is an ordinal.
If γ is neither α nor β, then γ ∈ α ∩ β by (c), a contradiction.


Lemma 4. (a) Each ordinal is the set of ordinals

T less than it;
(b) If C is a non-empty class of ordinals, then S C is the least ordinal S
in C;
(c) If X is a non-empty set of ordinals, then X is an ordinal, and X =
sup X;
(d) For each ordinal α, the least ordinal greater than α is given by α ∪ {α}.
We thus define the successor of α, denoted by α + 1, to be α ∪ {α}. In
particular, we define 1 as the successor of 0.

Proof. (a) By definition and Lemma 3(b).

(b) Pick α ∈ C. If α is not the least of C, then α ∩ C is a non-empty subset
of α, whose minimum is the least of C. Hence C always has T a minimum
min C. Since min C ⊂ β for every
S β ∈ C, we have min C = C. S
(c) By definition and Lemma 3, XSis a ordinal. It follows from (a) that X
is an upper bound of X. If γ ∈ SX, then γ ∈ β for some β ∈ X, so γ is
not an upper bound of X. Hence X = sup X.
(d) By definition, α ∪ {α} is an ordinal. Moreover, it is an upper bound of α.
If γ ∈ α ∪ {α}, then either γ ∈ α or γ = α. Hence α ∈ / γ.


Theorem 2. Every well-ordered set W is isomorphic to a unique ordinal number,

called the order-type of W .

Proof. Suppose, for contradiction, that there exists a well-ordered set W not iso-
morphic to any ordinals. Then by Theorem 1, each ordinal is isomorphic to an
initial segment of W .
By Lemma 2 and 3, we can define an injective function f as the set of all ordered
pairs (x, α) such that x ∈ W and α is an ordinal isomorphic to W (x). Since ran(f )
contains all ordinals, the class of ordinals O is a set. But that is impossible, because
by definition O would be an ordinal itself, which leads to O ∈ O. 

Let α be an ordinal. If α = β + 1 for some ordinal β, then α is called a successor

ordinal. Otherwise, α is called a limit ordinal. We consider 0 = ∅ as a limit ordinal
and define sup ∅ = 0. If α is a non-zero limit ordinal, then α = sup α.
4 ORDINAL NUMBERS

4. The Axiom of Infinity

A set S is called inductive if ∅ ∈ S and x ∪ {x} ∈ S for all x ∈ S. The Axiom
of Infinity asserts the existence of an inductive set. Hence there exists a non-zero
limit ordinal:
Theorem 3. The set
\
ω= {S : S is inductive}
is the least non-zero limit ordinal.
Proof. Given an arbitrary inductive set, its intersection with O is an inductive set
of ordinals. Hence ω is a set of ordinals well-ordered by ∈. Since ω has a transitive
inductive subset {α ∈ ω : α ⊂ ω}, the set ω is itself transitive. Therefore, ω is an
ordinal.
ω is a limit ordinal, for otherwise ω ∈ ω by inductivity. Since non-zero limit
ordinals are all inductive, ω is the least of them. 
Definition 7 (Finite ordinals). The ordinals less than ω are said to be finite.
A set X is said to be finite if there is a bijection from X onto some finite ordinal
a. X is said to be infinite if it is not finite.

5. Induction and recursion

For clarity, we shall use < instead of ∈ when comparing ordinals.
Theorem 4 (Transfinite induction). Let S be a subset of a non-zero ordinal θ and
assume that
(a) 0 ∈ S (base case);
(b) if β ∈ S for all β < α (inductive hypothesis), then α ∈ S.
Then S = θ.
Proof. Otherwise, consider the minimum of θ − S. 
A sequence is a function defined on an ordinal. More specifically, an α-sequence
(sξ )ξ<α in a set X is defined as a function from an ordinal α to X, and α is called
the length of the α-sequence. A sequence in X is called an enumeration of X if it
is surjective. If s is an α-sequence, then sx denotes the sequence of length α + 1
that extends s and has x as its α-th term:
sx = s ∪ {(α, x)} .
Sometimes we shall call a class function on O a sequence.
An α-sequence is said to be
(i) finite, if α < ω;
(ii) infinite, if α = ω;
(iii) transfinite, if α > ω.
Theorem 5 (Transfinite recursion). Let X be a set and θ be a non-zero ordinal.
For every function G on the set of all sequences in X of length less than θ such
that ran(G) ⊂ X, there exists a unique θ-sequence s such that sα = G((sξ )ξ<α ) for
every α < θ.
Proof. Fix G as required. For each α < θ, put f (α) = x if there is a sequence
(sξ )ξ<α such that
 ORDINAL NUMBERS 5

(i) For each β < α, sβ = G((sξ )ξ<β );

(ii) x = G((sξ )ξ<α ).
Then f (0) = G(∅). If α > 0, assume s and t to be two α-sequences in X with
property (i). Then sξ = tξ for all ξ < α by induction. Thus if f (α) exists, f (α) is
uniquely determined. Hence f is a function.
By induction we prove that f (α) exists for all α < θ and f (α) = G(f |α). The
base case is f (0) = G(∅). For α > 0, the inductive hypothesis states that f (ξ) exists
if ξ < α and that f (ξ) = G(f |ξ). Hence f |α is an α-sequence with properties (i).
By definition, f (α) = G(f |α). 
Definition 8. Let α be a non-zero limit ordinal and (θξ )ξ<α be a non-decreasing
sequence of ordinals. We define the limit of this sequence by
lim θξ = sup{θξ : ξ < α} .
ξ→α

A sequence of ordinals (θα )α∈O is said to be continuous if for every non-zero

limit α,
θα = lim θξ .
ξ→α

(θα )α∈O is said to be normal if it is increasing and continuous.

6. Ordinal arithmetic
We define arithmetic operations of ordinals through transfinite recursion.
Definition 9 (Addition). For all ordinal numbers α,
(i) α + 0 = α;
(ii) α + (β + 1) = (α + β) + 1 for all β;
(iii) α + β = limξ→β (α + ξ) for all non-zero limit β.
Definition 10 (Multiplication). For all ordinal numbers α,
(i) α · 0 = 0;
(ii) α · (β + 1) = α · β + α for all β;
(iii) α · β = limξ→β α · ξ for all non-zero limit β.
Definition 11 (Exponentiation). For all ordinal numbers α,
(i) α0 = 1;
(ii) αβ+1 = αβ · α for all β;
(iii) αβ = limξ→β αξ for all non-zero limit β.
Lemma 5. For a fixed α,
(a) α + β is a normal function in β;
(b) α · β is a normal function in β, provided that α > 0;
(c) αβ is a normal function in β, provided that α > 1.
Observe that 0 · β = 0 and 1β = 1 for all β. Also observe that 0β = 0 if β is a
successor and 0β = 1 otherwise.
Lemma 6. For all ordinals α, β and γ,
(a) α + (β + γ) = (α + β) + γ;
(b) α · (β + γ) = α · β + α · γ;
(c) α · (β · γ) = (α · β) · γ;
6 ORDINAL NUMBERS

(d) αβ · αγ = αβ+γ ;
(e) (αβ )γ = αβ·γ .
Lemma 7. For all finite ordinals a and b,
(a) a + b = b + a;
(b) a · b = b · a;
(c) a + b is increasing in a;
(d) a · b is increasing in a, provided that b > 0;
(e) ab is increasing in a, provided that b > 0.
Lemma 5, 6 and 7 can be proved by induction.
Lemma 8. Some ordinary properties of ordinal sums and products:
(a) If α < β, then there exists a unique δ such that α + δ = β;
(b) If α > 0, then for each γ there exists a unique β and a unique ρ < α such
that γ = α · β + ρ.
Proof. (a) Fix α. Suppose, for contradiction, that β > α is the least ordinal
for which α + δ 6= β for all ordinals δ. β is a limit ordinal, for otherwise
β = α + (δ + 1) for some δ. Put δ = sup{ξ : α + ξ < β}. Then δ is a limit
ordinal. Hence α + δ = sup{α + ξ : α + ξ < β} = β, a contradiction.
Uniqueness is by monotonicity of addition.
(b) Let β be the greatest ordinal such that α · β ≤ γ.

Theorem 6 (Cantor’s normal form theorem). Every ordinal α > 0 can be repre-
sented uniquely in the form (called the normal form of α)
α = ω β1 · k1 + · · · + ω βn · kn ,
where n ≥ 1, α ≥ β1 > · · · > βn , and k1 , . . . , kn are finite ordinals.
Proof. We prove the existence of a normal form by induction on α > 1. The base
case is 1 = ω 0 · 1. Given α > 1, let β the greatest ordinal such that ω β ≤ α. Then
there exists a unique δ and a unique ρ < ω β such that α = ω β · δ + ρ. Moreover,
δ is finite, for otherwise ω β+1 ≤ α. By the inductive hypothesis, ρ has a normal
form. Hence α has a normal form.
Suppose that ω β1 +1 ≤ α for β1 in some normal form of α. Then
ω β1 · k1 + · · · + ω βn · kn <ω β1 · k1 + · · · + ω βn−1 · kn−1 + ω βn +1
<ω β1 · k1 + · · · + ω βn−1 · (kn−1 + 1)
...
<ω β1 +1 ,
a contradiction. Since β1 is uniquely determined in each normal form, each ordinal
has a unique normal form.