571
ページ

## 整列クラス

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 en:transfinite induction on $$\alpha$$, where $$\textrm{ot}(X)$$ denotes the order type of $$X$$.[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}$$.

## チューリングマシンの集合

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 en:Kleene's O, and hence to define the 急増加関数 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]

## 参考文献

1. M. Rathjen, Ordinal notations based on a weakly Mahlo cardinal. Archive for Mathematical Logic 29(4) 249-263 (1990).
2. T. Kihara, omega-1-ck.pdf.