Enumeration

An enumeration is a bijective map from an ordinal to a class, and is a fundamental method to diagonalise a class in googology.

Class

For a well-ordered set or a well-ordered definable proper class \(X\), the enumeration of \(X\) is defined by the map \begin{eqnarray*} \textrm{enum}[X] \colon \textrm{ot}(X) & \to & X \\ \alpha & \mapsto & \textrm{enum}[X](\alpha) \end{eqnarray*} defined as \begin{eqnarray*} \textrm{enum}[X](\alpha) & \mapsto & \min \{x \in X \mid \forall \beta < \alpha, \textrm{enum}[X](\beta) < x\} \end{eqnarray*} by the transfinite induction on \(\alpha\), where \(\textrm{ot}(X)\) denotes the order type of \(X\).

For example, the enumeration of \(\textrm{On}\) is the identity map \(\alpha \mapsto \alpha\), the enumeration of \(\textrm{Lim}\) is the map \(\alpha \mapsto \omega \times (1+\alpha)\), and the enumeration of \(\textrm{AP}\) is the map \(\alpha \mapsto \omega^{\alpha}\).

If \(X\) is a definable club subclass of \(\textrm{On}\), then the enumeration of \(X\) is a definable Scott continuous bijective map \(\textrm{On} \to X \subset \textrm{On}\). Conversely, every definable Scott continuous injective map \(\textrm{On} \to \textrm{On}\) coincides with the enumeration of its image, which is a definable club subclass of \(\textrm{On}\).

The set of Turing machines

Turing machines can be encoded into natural numbers through several standard numbering. As a result, the set of all computable partial functions \(\mathbb{N} \to \mathbb{N}\) can be indexed by the set of natural numbers, while the set of all functions \(\mathbb{N} \to \mathbb{N}\) is uncountable. An enumeration is used to define Kleene's O, and hence to define the fast-growing hierarchy corresponding to \(\omega_1^{\textrm{CK}}\). Since there are several standard enumerations and the resulting fast-growing function heavily depends on the choice of an enumeration, how to enumerate a Turing machine is important to generate a fast-growing uncomputable function. See also the main article for the issue of the slow-growing property of the fast-growing hierarchy corresponding to \(\omega_1^{\textrm{CK}}\) corresponding to a pathologic enumeration of Turing machines constructed by a Japanese mathematician Kihara.

See also

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
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)