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).M. Rathjen, Ordinal notations based on a weakly Mahlo cardinal. Archive for Mathematical Logic 29(4) 249-263 (1990).
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.T. Kihara, omega-1-ck.pdf.
== See also ==
* Derivative
* Kleene's O
== Sources ==
Category:Set theory
ja:数え上げ関数