巨大数研究 Wiki
Advertisement
巨大数研究 Wiki
巨大数研究 Wiki
583
ページ
分類: 関数、順序数崩壊関数、順序数、
および 3ページ
日本語

ブーフホルツのψ関数

編集するにはログイン
他のψ関数については、ψ関数 をご覧ください。

ブーフホルツのψ関数（Buchholz's psi function）は W. Buchholz が開発した順序数崩壊関数である[1]。これは、フェファーマンのθ関数より簡単な代替として開発されたもので、2つのシステムは同等の強さである。


定義[]

\(\Omega_0 = 1\)、\(\Omega_\alpha = \aleph_\alpha\)(\(\alpha > 0\))とする。\(P\) を\(\omega^\alpha\)の形で表される順序数全体のクラスとする。 \(P(0) = \emptyset\) で、\(P(\alpha) = \{\alpha_0, \alpha_1, \ldots, \alpha_n\}\) とする。ここで、\(\alpha_i \in P\)、\(\alpha_0 + \alpha_1 + \cdots + \alpha_n = \alpha\)、\(\alpha_0 \geq \alpha_1 \geq \cdots \geq \alpha_n\)である。 (つまり、\(P(\alpha)\)は \(\alpha\)のカントール標準形の全体の集合である)

次に\(C_v(\alpha)\)、\(\psi_v(\alpha)\)の二つの関数を定義する。ただし\(v \leq \omega\)である。\(\alpha\)に関する超限再帰により、全ての\(\xi < \alpha\)に対し\(C_v(\xi)\)と\(\psi_v(\xi)\)が定義されているとし:

\begin{eqnarray*} C_v^0(\alpha) &=& \Omega_v \\ C_v^{n + 1}(\alpha) &=& C_v^n(\alpha) \cup \{\gamma : P(\gamma) \subseteq C_v^n(\alpha)\} \\ & & \cup \{\psi_u(\xi) : \xi \in \alpha \cap C_v^n(\alpha) \wedge \xi \in C_u(\xi) \wedge u \leq \omega\} \\ C_v(\alpha) &=& C_v^0(\alpha) \cup C_v^1(\alpha) \cup C_v^2(\alpha) \cup \cdots \\ \psi_v(\alpha) &=& \min\{\gamma : \gamma \notin C_v(\alpha)\} \end{eqnarray*}

と定める。より単純に表現すると\(C_v(\alpha)\)は、\(\Omega_v\)未満の順序数全体の集合から始めて加算と（定義域を\(\alpha\)未満の順序数に制限した）\(\psi\)関数を有限回適用して構成することのできる順序数全体の集合である。すなわち、\(C_v(\alpha)\)と\(\psi_v(\alpha)\)の代わりに\(C_v(\alpha)'\)と\(\psi_v(\alpha)'\)を以下のように超限再帰で定めると、\(C_v(\alpha) = C_v(\alpha)'\)かつ\(\psi_v(\alpha) = \psi_v(\alpha)'\)が成り立つ:

\begin{eqnarray*} C_v^0(\alpha)' &=& \{\xi : \xi < \Omega_v\} \\ C_v^{n + 1}(\alpha)' &=& C_v^n(\alpha)' \cup \{\beta+\gamma : \beta,\gamma \in C_v^n(\alpha)'\} \\ & & \cup \{\psi_u(\xi)' : \xi \in C_v^n(\alpha)' \wedge \xi < \alpha \wedge \xi \in C_u(\xi)' \wedge u \leq \omega\} \\ C_v(\alpha)' &=& C_v^0(\alpha)' \cup C_v^1(\alpha)' \cup C_v^2(\alpha)' \cup \cdots \\ \psi_v(\alpha)' &=& \min\{\gamma : \gamma \notin C_v(\alpha)'\} \end{eqnarray*}


順序数表記[]

何らかの可算集合 \(OT\) に再帰的整列順序 \(<\) を定めたものを順序数表記と呼ぶ。Buchholzは上述のψ関数と整合的な方法で以下のように順序数表記を定義している。

まず \(0\) と記号 \(D_0,D_1,\ldots,D_\omega\) とカッコ \((,)\) とコンマを有限個並べた文字列からなる集合 \(T\) を、以下のように帰納的に定める:

  1. \(0 \in T\) である。
  2. \(a \in T\) と \(v \leq \omega\) に対し、\(D_va \in T\) である。このような文字列を単項と呼ぶ。
  3. \(1 \leq k < \omega\) と単項 \(a_0,\ldots,a_k \in T\) に対し、\((a_0,\ldots,a_k) \in T\) である。

すなわち上記の条件を満たす最小の集合が \(T\) である。この定義から、\(T\) の要素は \(0\) であるか、単項であるか、カッコで囲まれた長さ \(2\) 以上の単項の配列であるか、のいずれかとなる。単項全体の集合を \(PT\) と置く。

単項 \(a \in T\) のことを \((a)\) とも表すこととする。\(T\) の定義の３つ目の条件は長さが \(2\) 以上の配列にしか適用されないため、この表記の追加で曖昧性が生じることはないことに注意する。これにより\(T\)の全ての要素は \(0\) かカッコで囲まれた長さ\(1\) 以上の単項の配列であるかのいずれかで表すことが出来る。


\(T\) 上の狭義全順序 \(a < b\) （\((a,b) \in T^2\)）を以下のように帰納的に定める:

  1. \(b = 0\) ならば、\(a < b\) でない。
  2. \(b \neq 0\) かつ \(a = 0\) ならば、\(a < b\) と \(b \neq 0\) は同値である。
  3. \(b \neq 0\) かつ \(a \neq 0\) とする。
    1. \(a,b\) が共に単項である時、\((u,v,a',b') \in (\omega+1)^2 \times T^2\) を用いて \(a = D_ua'\) と \(b = D_vb'\) と置くと、\(a < b\) は以下のいずれかが成り立つことと同値である。
      1. \(u < v\) である。
      2. \(u = v\) かつ \(a' < b'\) である。
    2. \(a,b\) のいずれかが単項でない時、\(1 \leq m+n \) を満たす \(n,m < \omega\) と \((a_0,\ldots,a_n,b_0,\ldots,b_m) \in PT^{n+m+2}\) を用いて \(a = (a_0,\ldots,a_n)\) と \(b = (b_0,\ldots,b_m)\)と置くと、\(a < b\) である必要十分条件は、以下のいずれかが成り立つことである。
      1. \(n < m\) かつ、いかなる\(i \leq n\)に対しても \(a_i = b_i\) である。
      2. ある \(k \leq \min\{n,m\}\) が存在して、\(a_k < b_k\) かつ、いかなる\(i < k\)に対しても\(a_i = b_i\)である。

狭義全順序 \(<\) に付随する全順序を \(\leq\) と置く。\(\leq\) 自体は整列順序ではないが、後に定義する \(OT \subset T\) に \(\leq\) を制限したものは整列順序となる。


\(OT\) を定義する準備として、各 \(a \in T\) と \(u \leq \omega\) に対して部分集合 \(G_ua \subset T\) を以下のように帰納的に定める:

  1. \(a = 0\) の時、\(G_ua = \emptyset\)である。
  2. \(a\) が単項である時、\(a = D_va'\) と置くと、
    1. \(u \leq v\) の時、\(G_ua = \{a'\} \cup G_ua'\) である。
    2. \(u > v\) の時、\(G_ua = \emptyset\) である。
  3. \(a\) が \(0\) でも単項でもない時、\(1 \leq k < \omega\) を用いて \(a = (a_0,\ldots,a_k) \)と置くと、\(G_ua = G_ua_0 \cup \cdots \cup G_ua_k\) である。

これを用い、\(T\) の 部分集合 \(OT\) を以下のように帰納的に定める:

  1. \(0 \in OT\) である。
  2. \(a \in OT\) と \(v \leq \omega \) に対し、条件「任意の \(a' \in G_va\) に対し \(a' < a\) である」が成り立つならば \( D_va \in OT \) である。
  3. \(1 \leq k < \omega\) と単項 \(a_0,\ldots,a_k \in OT\) に対し、\(a_k \leq \cdots \leq a_0\) ならば \((a_0,\ldots,a_k) \in OT\) である。

すなわち上記の条件を満たす最小の部分集合が \(OT \subset T\)である。\(OT\) の要素を順序数項と呼ぶ。


順序数項 \(a\) は以下の方法で、帰納的に順序数 \(o(a)\) へ対応する:

  1. \(a = 0\) の時、\(o(a) = 0\) である。
  2. \(a\) が 単項である時、\(a = D_va'\) と置くと、\(o(a) = \psi_v(o(a'))\) である。
  3. \(a\) が \(0\) でも単項でもない時、\(1 \leq k < \omega\) を用いて \(a = (a_0,\ldots,a_k) \)と置くと、\(o(a) = o(a_0) \# \cdots \# o(a_k)\) である。ただし \(\#\) は順序数の降順の加法であり、\(OT\) の定義からそれは通常の加法と一致する。

これにより定まる写像\(o \colon OT \to C_0(\epsilon_{\Omega_{\omega}+1})\)は以下の性質を満たす:

  • \(o\) は順序を保つ全単射である。特に\(\leq\)は\(OT\)上の整列順序である。
  • 順序数項 \(a < D_10\) に対し、\(o(a)\) は \(\leq\) の \(\{x \in OT \mid x < a\}\) への制限の整列順序型である。
  • \(\psi_0(\epsilon_{\Omega_{\omega}+1})\) は \(\leq\) の \(\{x \in OT \mid x < D_10\}\) への制限の整列順序型である。特に \(\{x \in OT \mid x < D_10\}\) は \(\psi_0(\epsilon_{\Omega_{\omega}+1})\) 相当の順序数表記を与える。
  • \(0 < v \in \omega\) に対し、\(\leq\) の \(\{x \in OT \mid o(x) < \psi_0(\epsilon_{\Omega_v+1})\}\) への制限に関する原始再帰的無限降下列の停止性は\(\textrm{ID}_v\) において証明可能でない。
  • \(\leq\) の \(\{x \in OT \mid o(x) < \psi_0(\Omega_{\omega})\}\) への制限に関する原始再帰的無限降下列の停止性は\(\Pi_1^1-\textrm{CA}_0\) において証明可能でない。


拡張[]

\(\Omega_{\omega}\) までの基数を扱うブーフホルツのψ関数は、Googology WikiユーザーのDenis Maksudovによって 拡張ブーフホルツのψ関数 として 最小の\(\Omega\)不動点 までの基数まで扱うように拡張され、可算順序数に対する基本列も拡張された[2][3]。拡張ブーフホルツのψ関数に伴う順序数表記は巨大数研究 Wikiユーザーのp進大好きbotによって与えられ、基本列や急増加関数の計算アルゴリズムも構成された[4]。

基本列[]

以下はユーザーブログ:P進大好きbot/拡張Buchholz_OCFに伴う順序数表記で構成されている共終数と基本列のアルゴリズムのうち、ブーフホルツのψ関数の部分のみを抜き出したものである。

\(\alpha = \psi_\nu(\beta)\)の共終数\(\textrm{cf}(\alpha)\)と基本列\(\alpha[\eta]\)を、\(\beta\)の共終数によって次のように場合分けして定める:

  1. \(\textrm{cf}(\beta) = 0\)とする。
    1. \(\textrm{cf}(\nu) = 0\)ならば、\(\textrm{cf}(\alpha) := \alpha\)かつ\(\alpha[\eta] := 0\)である。
    2. \(\textrm{cf}(\nu) = 1\)ならば、\(\textrm{cf}(\alpha) := \alpha\)かつ\(\alpha[\eta] := \eta\)である。
    3. \(\textrm{cf}(\nu) \notin \{0,1\}\)ならば、\(\textrm{cf}(\alpha) := \omega\)かつ\(\alpha[\eta] := \Omega_\eta\)である。
  2. \(\textrm{cf}(\beta) = 1\)ならば、\(\beta = \beta'+1\)を満たす\(\beta'\)が存在する。
    1. \(\textrm{cf}(\alpha) := \omega\)かつ\(\alpha[\eta] := \psi_\nu(\beta')\times\eta\)である。
  3. \(\textrm{cf}(\beta) \notin \{0,1\}\)とする。
    1. \(\textrm{cf}(\beta) < \alpha\)ならば、\(\textrm{cf}(\alpha) := \textrm{cf}(\beta)\)かつ\(\alpha[\eta] := \psi_\nu(\beta[\eta])\)である。
    2. \(\textrm{cf}(\beta) \geq \alpha\)ならば、\(\textrm{cf}(\alpha := \omega\)である。
    3. \(\textrm{cf}(\beta) = \psi_{\mu+1}(0)\)とおく。
    4. \(\alpha[0] := \psi_\nu(\beta[\psi_\mu(0)])\)である。
    5. \(\eta = \eta'+1\)を満たす\(\eta'\)と\(\alpha[\eta'] = \psi_\nu(\Gamma)\)を満たす\(\Gamma\)が存在するならば、\(\alpha[\eta] := \psi_\nu(\beta[\psi_\mu(\Gamma)])\)である。

ここで、\(\eta \in \textrm{cf}(\alpha)\)とする。

基本列の例[]

ここで、基本列は上記で定義されたものを使用する。

ブーフホルツのψ関数 基本列
\(\psi_0(1) = \psi_0(\psi_0(0)) = \omega\) \(0,1,2,3,...\)
\(\psi_0(2) = \omega^2\) \(0,\psi_0(1),\psi_0(1)\times 2,\psi_0(1)\times 3,...\)
\(\psi_0(3) = \omega^3\) \(0,\psi_0(2),\psi_0(2)\times 2,\psi_0(2)\times 3,...\)
\(\psi_0(\psi_0(1)) = \omega^\omega\) \(\psi_0(0),\psi(1),\psi_0(2),\psi_0(3),...\)
\(\psi_0(\psi_0(1)+1) = \omega^{\omega+1}\) \(0,\psi_0(\psi_0(1)),\psi_0(\psi_0(1))\times 2,\psi_0(\psi_0(1))\times 3,...\)
\(\psi_0(\psi_0(1)\times 2) = \omega^{\omega\times 2}\) \(\psi_0(\psi_0(1)),\psi_0(\psi_0(1)+1),\psi_0(\psi_0(1)+2),\psi_0(\psi_0(1)+3),...\)
\(\psi_0(\psi_0(2)) = \omega^{\omega^2}\) \(\psi_0(0),\psi_0(\psi_0(1)),\psi_0(\psi_0(1)\times 2),\psi_0(\psi_0(1)\times 3),...\)
\(\psi_0(\psi_0(\psi_0(1))) = \omega^{\omega^\omega}\) \(\psi_0(\psi_0(0)),\psi_0(\psi_0(1)),\psi_0(\psi_0(2)),\psi_0(\psi_0(3)),...\)
\(\psi_0(\psi_1(0)) = \epsilon_0\) \(\psi_0(0),\psi_0(\psi_0(0)),\psi_0(\psi_0(\psi_0(0))),\psi_0(\psi_0(\psi_0(\psi_0(0)))),...\)
\(\psi_0(\psi_1(0)+\psi_0(\psi_1(0))) = \epsilon_0^2\) \(\psi_0(\psi_1(0)+\psi_0(0)),\psi_0(\psi_1(0)+\psi_0(\psi_0(0))),\psi_0(\psi_1(0)+\psi_0(\psi_0(\psi_0(0)))),\psi_0(\psi_1(0)+\psi_0(\psi_0(\psi_0(\psi_0(0))))),...\)
\(\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+1)) = \epsilon_0^\omega\) \(\psi_0(\psi_1(0)),\psi_0(\psi_1(0)+\psi_0(\psi_1(0))),\psi_0(\psi_1(0)+\psi_0(\psi_1(0))+\psi_0(\psi_1(0))),\psi_0(\psi_1(0)+\psi_0(\psi_1(0))+\psi_0(\psi_1(0))+\psi_0(\psi_1(0))),...\)
\(\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(\psi_1(0)))) = \epsilon_0^{\epsilon_0}\) \(\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(0))),\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(\psi_0(0)))),\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(\psi_0(\psi_0(0))))),\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(\psi_0(\psi_0(\psi_0(0)))))),...\)
\(\psi_0(\psi_1(0)\times 2) = \epsilon_1\) \(\psi_0(\psi_1(0)),\psi_0(\psi_1(0)+\psi_0(\psi_1(0))),\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(\psi_1(0)))),\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(\psi_1(0)+\psi_0(\psi_1(0))))),...\)
\(\psi_0(\psi_1(0)\times 3) = \epsilon_2\) \(\psi_0(\psi_1(0)\times 2),\psi_0(\psi_1(0)\times 2+\psi_0(\psi_1(0)\times 2)),\psi_0(\psi_1(0)\times 2+\psi_0(\psi_1(0)\times 2+\psi_0(\psi_1(0)\times 2))),\psi_0(\psi_1(0)\times 2+\psi_0(\psi_1(0)\times 2+\psi_0(\psi_1(0)\times 2+\psi_0(\psi_1(0)\times 2)))),...\)
\(\psi_0(\psi_1(1)) = \epsilon_\omega\) \(\psi_0(0),\psi_0(\psi_1(0)),\psi_0(\psi_1(0)\times 2),\psi_0(\psi_1(0)\times 3),...\)
\(\psi_0(\psi_1(1)+\psi_1(0)) = \epsilon_{\omega+1}\) \(\psi_0(\psi_1(1)),\psi_0(\psi_1(1)+\psi_0(\psi_1(1))),\psi_0(\psi_1(1)+\psi_0(\psi_1(1)+\psi_0(\psi_1(1)))),\psi_0(\psi_1(1)+\psi_0(\psi_1(1)+\psi_0(\psi_1(1)+\psi_0(\psi_1(1))))),...\)
\(\psi_0(\psi_1(1)+\psi_1(1)) = \epsilon_{\omega\times 2}\) \(\psi_0(\psi_1(1)),\psi_0(\psi_1(1)+\psi_1(0)),\psi_0(\psi_1(1)+\psi_1(0)\times 2),\psi_0(\psi_1(1)+\psi_1(0)\times 3),...\)
\(\psi_0(\psi_1(2)) = \epsilon_{\omega^2}\) \(\psi_0(0),\psi_0(\psi_1(1)),\psi_0(\psi_1(1)\times 2),\psi_0(\psi_1(1)\times 3),...\)
\(\psi_0(\psi_1(\psi_0(1))) = \epsilon_{\omega^\omega}\) \(\psi_0(\psi_1(0)),\psi_0(\psi_1(1)),\psi_0(\psi_1(2)),\psi_0(\psi_1(3)),...\)
\(\psi_0(\psi_1(\psi_0(\psi_1(0)))) = \epsilon_{\epsilon_0}\) \(\psi_0(\psi_1(\psi_0(0))),\psi_0(\psi_1(\psi_0(\psi_0(0)))),\psi_0(\psi_1(\psi_0(\psi_0(\psi_0(0))))),\psi_0(\psi_1(\psi_0(\psi_0(\psi_0(\psi_0(0)))))),...\)
\(\psi_0(\psi_1(\psi_1(0))) = \varphi_2(0)\) \(\psi_0(\psi_1(0)),\psi_0(\psi_1(\psi_0(\psi_1(0)))),\psi_0(\psi_1(\psi_0(\psi_1(\psi_0(\psi_1(0)))))),\psi_0(\psi_1(\psi_0(\psi_1(\psi_0(\psi_1(\psi_0(\psi_1(0)))))))),...\)

関連項目[]

外部リンク[]

参考文献[]

  1. ↑ W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, Vol. 32 (1986), pp. 195--207.
  2. ↑ Googology WikiにおけるDenis Maksudovのユーザーページ
  3. ↑ Denis Maksudov, The extension of Buchholz's function, Traveling To The Infinity.
  4. ↑ p進大好きbot, 拡張Buchholz OCFに伴う順序数表記, 巨大数研究 Wikiユーザーブログ.
English
特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。
Advertisement