Enumeration

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

A well-ordered 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\) (under the given well-order).

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}\).

Examples of uses

These are examples of uses of enumeration maps for well-ordered classes in googology, especially in the constructions by iterated derivative, which is an iteration of enumerations of fixed points of previous functions.

Veblen function

The Veblen function is defined using iterated derivative.

Rathjen's Φ function

The Rathjen's \(\Phi\) function is defined using iterated derivative.

Feferman's θ function

Each function \(\theta_\alpha\) can be seen as an enumerating function of the class of "\(\alpha\)-critical ordinals", as given in the equivalent explanation.

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

• Derivative
• Kleene's O

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)