巨大数研究 Wiki
Advertisement
巨大数研究 Wiki

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

整列クラス

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.
Advertisement