2Well-orderings and ordinals
II Logic and Set Theory
2.6 Normal functions*
Note: These content were not lectured during the year.
When we have ordinals, we would like to consider functions
On → On
.
Since the ordinals are totally ordered, it would make sense to consider the
order-preserving functions, i.e. the increasing ones. However, ordinals have an
additional property — we could take suprema of ordinals. If we want our function
to preserve this as well, we are lead to the following definition:
Definition (Normal function). A function f : On → On is normal if
(i) For any ordinal α, we have f(α) < f(α
+
).
(ii) If λ is a non-zero limit ordinal, then f(λ) = sup{f(γ) : γ < λ}.
Some replace the increasing condition by
f
(
α
)
< f
(
α
+
). These are easily
seen to be equivalent by transfinite induction.
Example. By definition, we see that for each
β >
1, the function
α 7→ β
α
is
normal.
We start by a few technical lemmas.
Lemma. Let f be a normal function. Then f is strictly increasing.
Proof. Let α be a fixed ordinal. We induct on all β > α that f(α) < f (β).
If β = α
+
, then the result is obvious.
If
β
=
γ
+
with
γ
=
α
, then
α < γ
. So
f
(
α
)
< f
(
γ
)
< f
(
γ
+
) =
f
(
β
) by
induction.
If β is a limit and is greater than α, then
f(β) = sup{f(γ) : γ < β} ≥ f(α
+
) > f(α),
since α
+
< β. So the result follows.
Lemma. Let f be a normal function, and α an ordinal. Then f(α) ≥ α.
Proof.
We prove by induction. It is trivial for zero. For successors, we have
f(α
+
) > f(α) ≥ α, so f(α
+
) ≥ α
+
. For limits, we have
f(λ) = sup{f(γ) : γ < λ} ≥ sup{γ : γ < λ} = λ.
The following is a convenient refinement of the continuity result:
Lemma. If
f
is a normal function, then for any non-empty set
{α
i
}
i∈I
, we have
f(sup{α
i
: i ∈ I}) = sup{f(α
i
) : i ∈ I}.
Proof.
If
{α
i
}
has a maximal element, then the result is obvious, as
f
is increasing,
and the supremum is a maximum.
Otherwise, let
α = sup{α
i
: i ∈ I}
Since the
α
i
has no maximal element, we know
α
must be a limit ordinal. So we
have
f(α) = sup{f (β) : β < α}.
So it suffices to prove that
sup{f(β) : β < α} = sup{f(α
i
) : i ∈ I}.
Since all α
i
< α, we have sup{f(β) : β < α} ≥ sup{f(α
i
) : i ∈ I}.
For the other direction, it suffices, by definition, to show that
f(β) ≤ sup{f (α
γ
) : i ∈ I}
for all β < α.
Given such a
β
, since
α
is the supremum of the
α
i
, we can find some particular
α
i
such that
β < α
i
. So
f
(
β
)
< f
(
α
i
)
≤ sup{f
(
α
i
) :
i ∈ I}
. So we are done.
Because of these results, some define normal functions to be functions that
are strictly increasing and preserve all suprema.
We now proceed to prove two important properties of normal functions (with
easy proofs!):
Lemma (Fixed-point lemma). Let
f
be a normal function. Then for each
ordinal α, there is some β ≥ α such that f(β) = β.
Since the supremum of fixed points is also a fixed point (by normality), it
follows that we can define a function
g
:
On → On
that enumerates the fixed
points. Now this function itself is again normal, so it has fixed points as well. . .
Proof. We thus define
β = sup{f (α), f(f(α)), f(f(f(α))), ···}.
If the sequence eventually stops, then we have found a fixed point. Otherwise,
β
is a limit ordinal, and thus normality gives
f(β) = sup{f (f(α)), f(f (f(α))), f(f (f(f(α)))), ···} = β.
So β is a fixed point, and β ≥ f (α) ≥ α.
Lemma (Division algorithm for normal functions). Let
f
be a normal function.
Then for all α, there is some maximal γ such that α ≥ f(γ).
Proof. Let γ = sup{β : f(β) ≤ α}. Then we have
f(γ) = sup{f(β) : f(b) ≤ α} ≤ α.
This is clearly maximal.