Normal function

View full site to see MathJax equation

In set theory, a normal function is a (definable) function \(f \colon \text{On} \to \text{On}\) that is strictly increasing and Scott continuous, where \(\text{On}\) denotes the class of ordinals. Some authors also refer to a function \(f \colon \alpha \to \alpha\) for an ordinal \(\alpha\) as a normal function if it satisfies similar conditions, and some also require \(f(0)>0\). When we emphasise the domain and the codomain, we call a normal function in the former convention a normal function on \(\text{On}\), and a normal function in the latter convention a normal function on \(\alpha\).

Explanation

We say that \(f\) is strictly increasing if \(\alpha < \beta\) implies \(f(\alpha) < f(\beta)\) holds for any ordinals \(\alpha\) and \(\beta\), and that \(f\) is Scott continuous (or continuous for short) if \(f(\alpha) = \sup\{f(\beta) \mid \beta < \alpha\}\) holds for any limit ordinal \(\alpha \neq 0\).

A trivial example of a normal function is the identity function \(f(\alpha)=\alpha\). Less trivial examples include functions such as \(f(\alpha)=1+\alpha\) or \(f(\alpha)=\omega^\alpha\). The most typical example of a non-normal function is the successor function \(f(\alpha)=\alpha+1\).

See also

• Derivative

Ordinals, ordinal analysis, and set theory

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) (Omega one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal · Berkeley cardinal · (Club Berkeley cardinal · limit club Berkeley cardinal)
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)