normal function

In axiomatic set theory, a function {{math|f : Ord → Ord}} is called normal (or a normal function) if it is continuous (with respect to the order topology) and strictly monotonically increasing. This is equivalent to the following two conditions:

For every limit ordinal {{mvar|γ}} (i.e. {{mvar|γ}} is neither zero nor a successor), it is the case that {{math|1=f{{hairsp}}(γ) = sup{{mset|f{{hairsp}}(ν) : ν < γ}}}}.
For all ordinals {{math|α < β}}, it is the case that {{math|f{{hairsp}}(α) < f{{hairsp}}(β)}}.

Examples

A simple normal function is given by {{math|1=f{{hairsp}}(α) = 1 + α}} (see ordinal arithmetic). But {{math|1=f{{hairsp}}(α) = α + 1}} is not normal because it is not continuous at any limit ordinal (for example, $f(\omega) = \omega+1 \ne \omega = \sup \{f(n) : n < \omega\}$ ). If {{mvar|β}} is a fixed ordinal, then the functions {{math|1=f{{hairsp}}(α) = β + α}}, {{math|1=f{{hairsp}}(α) = β × α}} (for {{math|β ≥ 1}}), and {{math|1=f{{hairsp}}(α) = β^α}} (for {{math|β ≥ 2}}) are all normal.

More important examples of normal functions are given by the aleph numbers $f(\alpha) = \aleph_\alpha$ , which connect ordinal and cardinal numbers, and by the beth numbers $f(\alpha) = \beth_\alpha$ .

Properties

If {{mvar|f}} is normal, then for any ordinal {{mvar|α}},

:{{math|f{{hairsp}}(α) ≥ α}}.{{harvnb|Johnstone|1987|loc=Exercise 6.9, p. 77}}

Proof: If not, choose {{mvar|γ}} minimal such that {{math|f{{hairsp}}(γ) < γ}}. Since {{mvar|f}} is strictly monotonically increasing, {{math|f{{hairsp}}(f{{hairsp}}(γ)) < f{{hairsp}}(γ)}}, contradicting minimality of {{mvar|γ}}.

Furthermore, for any non-empty set {{mvar|S}} of ordinals, we have

:{{math|1=f{{hairsp}}(sup S) = sup f{{hairsp}}(S)}}.

Proof: "≥" follows from the monotonicity of {{mvar|f}} and the definition of the supremum. For "{{math|≤}}", set {{math|1=δ = sup S}} and consider three cases:

if {{math|1=δ = 0}}, then {{math|1=S = {{mset|0}}}} and {{math|1=sup f{{hairsp}}(S) = f{{hairsp}}(0)}};
if {{math|1=δ = ν + 1}} is a successor, then there exists {{mvar|s}} in {{mvar|S}} with {{math|ν < s}}, so that {{math|δ ≤ s}}. Therefore, {{math|f{{hairsp}}(δ) ≤ f{{hairsp}}(s)}}, which implies {{math|f{{hairsp}}(δ) ≤ sup f{{hairsp}}(S)}};
if {{mvar|δ}} is a nonzero limit, pick any {{math|ν < δ}}, and an {{mvar|s}} in {{mvar|S}} such that {{math|ν < s}} (possible since {{math|1=δ = sup S}}). Therefore, {{math|f{{hairsp}}(ν) < f{{hairsp}}(s)}} so that {{math|f{{hairsp}}(ν) < sup f{{hairsp}}(S)}}, yielding {{math|1=f{{hairsp}}(δ) = sup {{mset|f{{hairsp}}(ν) : ν < δ}} ≤ sup f{{hairsp}}(S)}}, as desired.

Every normal function {{mvar|f}} has arbitrarily large fixed points; see the fixed-point lemma for normal functions for a proof. One can create a normal function {{math|f{{hairsp}}′ : Ord → Ord}}, called the derivative of {{mvar|f}}, such that {{math|f{{hairsp}}′(α)}} is the {{mvar|α}}-th fixed point of {{mvar|f}}.{{harvnb|Johnstone|1987|loc=Exercise 6.9, p. 77}} For a hierarchy of normal functions, see Veblen functions.

Notes

References

{{citation

|first=Peter

|last=Johnstone

|authorlink=Peter Johnstone (mathematician)

|year=1987

|title=Notes on Logic and Set Theory

|publisher=Cambridge University Press

|isbn=978-0-521-33692-5

|url-access=registration

|url=https://archive.org/details/notesonlogicsett0000john

}}

Category:Set theory

Category:Ordinal numbers