Normal function

In axiomatic set theory, a function $f : Ord \to 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 $γ$ (i.e. $γ$ is neither zero nor a successor), it is the case that $f (γ) = sup {f (ν) : ν < γ}$ .
For all ordinals $α < β$ , it is the case that $f (α) < f (β)$ .

Examples

A simple normal function is given by $f (α) = 1 + α$ (see ordinal arithmetic). But $f (α) = α + 1$ is not normal because it is not continuous at any limit ordinal; that is, the inverse image of the one-point open set ${λ + 1}$ is the set ${λ}$ , which is not open when $λ$ is a limit ordinal. If $β$ is a fixed ordinal, then the functions $f (α) = β + α$ , $f (α) = β \times α$ (for $β \geq 1$ ), and $f (α) = β α$ (for $β \geq 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 $f$ is normal, then for any ordinal $α$ ,

f (α) \geq α

.^[1]

Proof: If not, choose $γ$ minimal such that $f (γ) < γ$ . Since $f$ is strictly monotonically increasing, $f (f (γ)) < f (γ)$ , contradicting minimality of $γ$ .

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 " $\leq$ ", set $δ = sup S$ and consider three cases:

if $δ = 0$ , then $S = {0}$ and $sup f (S) = f (0)$ ;
if $δ = ν + 1$ is a successor, then there exists $s$ in $S$ with $ν < s$ , so that $δ \leq s$ . Therefore, $f (δ) \leq f (s)$ , which implies $f (δ) \leq sup f (S)$ ;
if $δ$ is a nonzero limit, pick any $ν < δ$ , and an $s$ in $S$ such that $ν < s$ (possible since $δ = sup S$ ). Therefore, $f (ν) < f (s)$ so that $f (ν) < sup f (S)$ , yielding $f (δ) = sup {f (ν) : ν < δ} \leq 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 create a normal function $f ' : Ord \to Ord$ , called the derivative of $f$ , such that $f ' (α)$ is the $α$ -th fixed point of $f$ .^[2] For a hierarchy of normal functions, see Veblen functions.

Notes

^ Johnstone 1987, Exercise 6.9, p. 77
^ Johnstone 1987, Exercise 6.9, p. 77

References

Johnstone, Peter (1987), Notes on Logic and Set Theory, Cambridge University Press, ISBN 978-0-521-33692-5

[1] Johnstone 1987, Exercise 6.9, p. 77

[2] Johnstone 1987, Exercise 6.9, p. 77

[1]

[2]