数え上げ関数

数え上げ関数 (enumeration) は順序数、あるいは順序数全体からなるクラスから整列なクラスへの全単射であり、巨大数論においてクラスを対角化する基本的な手法である。

整列クラス

整列集合、あるいは集合的な整列クラス\(X\)について、\(X\)の数え上げ関数とは以下のように定義される関数である。(ただし、\(X\)が真クラスの場合は\(\textrm{ot}(X) := \mathrm{On}\)とする。) \begin{eqnarray*} \textrm{enum}[X] \colon \textrm{ot}(X) & \to & X \\ \alpha & \mapsto & \textrm{enum}[X](\alpha) \end{eqnarray*}

\begin{eqnarray*} \textrm{enum}[X](\alpha) & \mapsto & \min \{x \in X \mid \forall \beta < \alpha, \textrm{enum}[X](\beta) < x\} \end{eqnarray*} 関数の値の定義には、\(\alpha\)に関する\(\textrm{ot}(X)\)(\(X\)の順序型)上の超限再帰が用いられる。

例えば、順序数全体のクラス\(\textrm{On}\)の数え上げ関数は\(\textrm{On}\)における恒等関数\(\alpha \mapsto \alpha\)であり、極限順序数全体のクラス\(\textrm{Lim}\)の数え上げ関数は\(\alpha \mapsto \omega \times (1+\alpha)\)であり、\(AP\)順序数全体のクラス\(\textrm{AP}\)の数え上げ関数は\(\alpha \mapsto \omega^{\alpha}\)である。

\(X\)が\(\textrm{On}\)の部分クラスであり、かつ\(\textrm{On}\)上でclub(極限に閉じ、有界でない)ならば、\(X\)の数え上げ関数\(\textrm{On} \to X \subset \textrm{On}\)は正規関数であり、クラス間の全単射(つまり順序同型)となる。逆に、任意の狭義単調増加関数\(\textrm{On} \to \textrm{On}\)はその像の数え上げ関数に等しく、更にそれが正規関数ならば、像は\(\textrm{On}\)上でclubとなる。

チューリングマシンの数え上げ

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.

関連項目

• 微分