巨大数研究 Wiki
Advertisement

\(\varepsilon_0\) (読み方は"イプシロンゼロ"、"イプシロンヌル"、または"イプシロンノート")は小さな可算順序数の1つであり、関数 \(\textrm{On} \to \textrm{On}, \ \alpha \mapsto \omega^\alpha\) の最小の不動点と定義される。ただし \(\textrm{On}\) は順序数全体のクラスである。 \(\varepsilon_0\) は他にもいくつかの同値な定義が存在する:

また、ワイナー階層を用いると以下のように表せる:

  • \(f_{\varepsilon_0}(n) \approx X \uparrow\uparrow X \&\ n\) (急増加関数)
  • \(H_{\varepsilon_0}(n) \approx X \uparrow\uparrow X \&\ n\) (ハーディー階層)
  • \(g_{\varepsilon_0}(n) = n \uparrow\uparrow n = n \uparrow\uparrow\uparrow 2\) (緩成長階層)

\(f_{\varepsilon_0}(n)\) はグッドスタイン関数GoucherのT関数と同等の増大度を持つ。

より高層のイプシロン数とヴェブレン階層

指数関数 \(\textrm{On} \to \textrm{On}, \ \alpha \mapsto \omega^\alpha\) の不動点を数え上げる関数は \(\textrm{On} \to \textrm{On}, \ \alpha \mapsto \varepsilon_\alpha\) と書かれる。特に \(\varepsilon_1\) は指数関数の\(\varepsilon_0\)の次の不動点である。すなわち

  • \(\varepsilon_0=\min\{\alpha \mid \alpha=\omega^\alpha\}=\sup\{0,1,\omega, \omega^\omega, \omega^{\omega^\omega},...\}\)
  • \(\varepsilon_{\alpha+1}=\min\{\beta \mid \beta=\omega^\beta\wedge\beta>\varepsilon_\alpha\}=\sup\{\varepsilon_\alpha+1,\omega^{\varepsilon_\alpha+1}, \omega^{\omega^{\varepsilon_\alpha+1}},...\}\)
  • \(\varepsilon_{\alpha}=\sup\{\varepsilon_{\beta} \mid \beta<\alpha\}\) (\(\alpha\) が極限順序数のとき)

この定義によって、後述する \(\zeta_0\) 未満の \(0\) でない極限順序数には次の基本列が定まる:

  • \(\alpha=\beta_1+\cdots+\beta_{k-1}+\beta_k\)(\(k\)は\(2\)以上の自然数で\(\beta_1,\ldots,\beta_{k-1},\beta_k\)は加法で分解できない無限順序数で\(\beta_1 \geq \cdots \geq \beta_{k-1} \geq \beta_k\))のとき \(\alpha[n]=\beta_1+\cdots+\beta_{k-1}+(\beta_k[n])\)
  • \(\alpha=\omega^{\beta+1}\) のとき \(\alpha[n]=\omega^{\beta} \times n\)
  • \(\alpha=\omega^{\beta}\) かつ \(\beta\) が非イプシロン数である \(0\) でない極限順序数のとき \(\alpha[n]=\omega^{\beta[n]}\)
  • \(\alpha=\varepsilon_0\) のとき \(\alpha[0]=0\), \(\alpha[n+1]=\omega^{\alpha[n]}\)
  • \(\alpha=\varepsilon_{\beta+1}\) のとき \(\alpha[0]=\varepsilon_\beta+1\), \(\alpha[n+1]=\omega^{\alpha[n]}\)
  • \(\alpha=\varepsilon_{\beta}\) かつ \(\beta\) が \(0\) でない極限順序数のとき \(\alpha[n]=\varepsilon_{\beta[n]}\)

関数 \(\textrm{On} \to \textrm{On}, \ \alpha \mapsto \varepsilon_\alpha\) の最小の不動点は \(\zeta_0\)(ゼータゼロ)やカントールの順序数と呼ばれ、関数 \(\textrm{On} \to \textrm{On}, \ \alpha \mapsto \varepsilon_\alpha\) の不動点を数え上げる関数は \(\textrm{On} \to \textrm{On}, \ \alpha \mapsto \zeta_\alpha\) と書かれる。

ギリシア文字は無限にないので、ヴェブレン階層という階層を用いてこの構成を一般化する。この階層の関数は、それ以前の関数たちの不動点を数え上げる。すなわち:

  • \(\phi_0(\alpha) = \omega^\alpha\)
  • \(\phi_\beta(\alpha)\) は任意の \(\gamma < \beta\) に対して \(\phi_\gamma\) の不動点をなすような順序数全体の中で \(1+\alpha\) 番目に小さいもの

2変数ヴェブレン階層で表せない最小の順序数がΓ₀である。

出典

  1. W. Pohlers, Proof theory: The first step into impredicativity, Springer, 2009.
Advertisement