Normal function
|
|
In axiomatic set theory, a function f : Ord → Ord is called normal (or a normal function) iff it is continuous (with respect to the order topology) and strictly mononotically increasing. This is equivalent to the following two conditions:
- For every infinite limit ordinal γ, f(γ) = sup {f(ν) : ν < γ}.
- For all ordinals α < β, f(α) < f(β).
Examples
A simple normal function is given by f(α) = 1 + α; note however that f(α) = α + 1 is not normal. If β is a fixed ordinal, then the functions f(α) = β + α, f(α) = β × α and f(α) = βα (for β > 1) are all normal.
More important examples of normal functions are given by the aleph numbers f(α) = אα which connect ordinal and cardinal numbers, and by the beth numbers f(α) = <math>\beth_\alpha<math>.
Facts
If f is normal, then for any α ∈ Ord,
- f(α) ≥ α.
(Proof: if this was not the case, we could choose a minimal γ with f(α) < α; then, since f is strictly monotonically increasing, f(f(α)) < f(α), which is a contradiction to α being minimal.)
Furthermore, for any non-empty set S of ordinals, we have
- f(sup S) = sup f(S).
(Proof: "≥" follows from the monotonicity of f and the definition of the supremum. For "≤", we set δ = sup S and distinguish three cases:
- if δ = 0, then S={0} and sup f(S) = f(0);
- if δ = ν + 1, then there exists s in S with ν < s, implying δ ≤ s and so f(δ) ≤ f(s), which implies f(δ) ≤ sup f(S);
- if δ is an infinite limit ordinal, we pick any ν < δ, then find s in S with ν < s (since δ = sup S) and hence f(ν) < f(s), implying f(ν) < sup f(S) and therefore f(δ) = sup { f(ν) : ν < δ } ≤ sup f(S) as desired.)
Every normal function f has arbitrarily large fixed points; see the fixed-point lemma for normal functions for a proof. One can thus create a new function g : Ord → Ord, colloquially described as "g(α) is the α-th fixed point of f". The function g is again normal.