2Well-orderings and ordinals
II Logic and Set Theory
2.5 Ordinal arithmetic
We want to define ordinals arithmetic such as + and
×
, so that we can make
formal sense out of our notations such as ω + ω in our huge list of ordinals.
We first start with addition.
Definition (Ordinal addition (inductive)). Define
α
+
β
by recursion on
β
(
α
is fixed):
– α + 0 = α.
– α + β
+
= (α + β)
+
.
– α + λ = sup{α + γ : γ < λ} for non-zero limit λ.
Note that officially, we cannot do “recursion on the ordinals”, since the
ordinals don’t form a set. So what we officially do is that we define
α
+
γ
on
{γ
:
γ < β}
recursively for each ordinal
β
. Then by uniqueness of recursions, we
can show that this addition is well-defined.
Example. ω + 1 = (ω + 0)
+
= ω
+
.
ω + 2 = (ω + 1)
+
= ω
++
.
1 + ω = sup{1 + n : n ≤ ω} = sup{1, 2, 3, ···} = ω.
It is very important to note that addition is not commutative! This asymmetry
arises from our decision to perform recursion on β instead of α.
On the other hand, addition is associative.
Proposition. Addition is associative, i.e. (α + β) + γ = α + (β + γ).
Proof.
Since we define addition by recursion, it makes sense to prove this by
induction. Since we recursed on the right-hand term in the definition, it only
makes sense to induct on γ (and fix α + β).
(i) If γ = 0, then α + (β + 0) = α + β = (α + β) + 0.
(ii) If γ = δ
+
is a successor, then
α + (β + δ
+
) = α + (β + δ)
+
= [α + (β + δ)]
+
= [(α + β) + δ]
+
= (α + β) + δ
+
= (α + β) + γ.
(iii) If γ is a limit ordinal, we have
(α + β) + λ = sup{(α + β) + γ : γ < λ}
= sup{α + (β + γ) : γ < λ}
If we want to evaluate
α
+ (
β
+
λ
), we have to first know whether
β
+
λ
is
a successor or a limit. We now claim it is a limit:
β
+
λ
=
sup{β
+
γ
:
γ < λ}
. We show that this cannot have a greatest
element: for any
β
+
γ
, since
λ
is a limit ordinal, we can find a
γ
′
such that
γ < γ
′
< λ. So β + γ
′
> β + γ. So β + γ cannot be the greatest element.
So
α + (β + λ) = sup{α + δ : δ < β + λ}.
We need to show that
sup{α + δ : δ < β + λ} = sup{α + (β + γ) : γ < λ}.
Note that the two sets are not equal. For example, if
β
= 3 and
λ
=
ω
,
then the left contains α + 2 but the right does not.
So we show that the left is both ≥ and ≤ the right.
≥: Each element of the right hand set is an element of the left.
≤
: For
δ < β
+
λ
, we have
δ < sup{β
+
γ
:
γ < λ}
. So
δ < β
+
γ
for some
γ < λ. Hence α + δ < α + (β + γ).
Note that it is easy to prove that
β < γ ⇒ α
+
β < α
+
γ
by induction on
γ
(which we implicitly assumed above). But it is not true if we add on the right:
1 < 2 but 1 + ω = 2 + ω.
The definition we had above is called the inductive definition. There is an
alternative definition of + based on actual well-orders. This is known as the
synthetic definition.
Intuitively, we first write out all the elements of
α
, then write out all the
elements of β after it. The α + β is the order type of the combined mess.
Definition (Ordinal addition (synthetic)).
α
+
β
is the order type of
α ⊔ β
(
α
disjoint union β, e.g. α × {0} ∪ β × {1}), with all α before all of β
α + β = α β
Example. ω + 1 = ω
+
.
1 + ω = ω.
With this definition, associativity is trivial:.
α + (β + γ) = α β γ = (α + β) + γ.
Now that we have given two definitions, we must show that they are the same:
Proposition. The inductive and synthetic definition of + coincide.
Proof.
Write + for inductive definition, and +
′
for synthetic. We want to show
that α + β = α +
′
β. We induct on β.
(i) α + 0 = α = α +
′
0.
(ii) α + β
+
= (α + β)
+
= (α +
′
β)
+
= otp α
β · = α +
′
β
+
(iii) α
+
λ
=
sup{α
+
γ
:
γ < λ}
=
sup{α
+
′
γ
:
γ < λ}
=
α
+
′
λ
. This works
because taking the supremum is the same as taking the union.
α γ γ
′
γ
′′
···λ
The synthetic definition is usually easier to work with, if possible. For
example, it was very easy to show associativity using the synthetic definition. It
is also easier to see why addition is not commutative. However, if we want to do
induction, the inductive definition is usually easier.
After addition, we can define multiplication. Again, we first give an inductive
definition, and then a synthetic one.
Definition (Ordinal multiplication (inductive)). We define
α · β
by induction
on β by:
(i) α · 0 = 0.
(ii) α · (β
+
) = α · β + α.
(iii) α · λ = sup{α · γ : γ < λ} for λ a non-zero limit.
Example.
– ω · 1 = ω · 0 + ω = 0 + ω = ω.
– ω · 2 = ω · 1 + ω = ω + ω.
– 2 · ω = sup{2 · n : n < ω} = ω.
– ω · ω = sup{ω · n : n < ω} = sup{ω, ω
2
, ω
3
, ···}.
We also have a synthetic definition.
Definition (Ordinal multiplication (synthetic)).
β
α
.
.
.
α
α
Formally,
α ·β
is the order type of
α ×β
, with (
x, y
)
<
(
x
′
, y
′
) if
y < y
′
or (
y
=
y
′
and x < x
′
).
Example. ω · 2 =
ω
ω
= ω + ω.
Also 2 · ω = ω
··
.
.
.
··
··
= ω
We can check that the definitions coincide, prove associativity etc. similar to
what we did for addition.
We can define ordinal exponentiation, towers etc. similarly:
Definition (Ordinal exponentiation (inductive)). α
β
is defined as
(i) α
0
= 1
(ii) α
β
+
= α
β
· α
(iii) α
λ
= sup{α
γ
: γ < λ}.
Example. ω
1
= ω
0
· ω = 1 · ω = ω.
ω
2
= ω
1
· ω = ω · ω.
2
ω
= sup{2
n
: n < ω} = ω.