11,051 Pages

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).[1]

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.[2]