巨大数研究 Wiki
登録
Advertisement
巨大数研究 Wiki
Bhydra3
ヒドラゲーム も参照して下さい。

ブーフホルツのヒドラ (Buchholz hydra) は一人で任意の有限の数もしくはωが書かれたラベルの付いた木を使って行うゲームである。このゲームから定義される関数を \(\text{BH}(n)\)とする。 この関数の増加率は 竹内・フェファーマン・ブーフホルツ順序数で表される。

規則

このゲームは、任意のラベル付き木\(T\) 、そしてその根が特別にラベルされている物(+と呼ぶ)を選ぶところから始まり、そのすべての子は0のラベルを持つ。この木はヒドラと呼ばれる。

一回のステップに置き、二つのパラメータを使い木を変形する。:葉の辺\(a\)、非負整数\(n\)。次のルールに従い木を変更する:

  1. もし\(a\)のラベルが0なら、ヒドラゲームと同じようにする。その辺の親を\(b\)、さらにその親を\(c\)とする。まず\(a\)を消去する。もし\(c\)が存在する(つまり\(b\)が根でない)なら、\(n\)個の\(b\)の複製を作り\(c\)にその子として接続させる。
  2. もし\(a\)のラベルが\(u + 1\)なら、ラベル\(v \leq u\)の辺\(b\)が見つかるまで木をさかのぼる(根のすべての子のラベルは0であるので、そのような辺は存在することが保証されている)。\(b\)を根に持つ\(T\)の部分木の中で最大のものを考え、\(S\)とおく。\(S\)の複製を作り、\(S'\)と呼ぶ。\(S'\)中で、\(b\)を\(u\)で、\(a\)を\(0\)でラベルし直す。もともとの木に戻り、\(a\)を\(S'\)で取り換える。
  3. もし\(a\)のラベルが\(\omega\)なら、単純にそれを\(n + 1\)でラベルし直す。

もし\(a\)がヒドラの右端の葉ならば、それを変形された木\(T(n)\)と表記する。

ヒドラを変形するのに、葉と整数\(n\)を選ぶ。葉と整数\(n\)の並びを戦略とよぶ。戦略がヒドラを根の辺以外なくすことが出来れば、勝つ戦略 、そうでなければ負ける戦略と呼ぶ。

ヒドラ理論

ブーフホルツは戦略には勝つ戦略しかないとした。これをヒドラ理論という。ヒドラ理論は\(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\)で証明不可能であるが、この理論は成立する。

ヒドラ理論には無限のヒドラは適用不可能である;次を見よ、section

証明:ヒドラゲームでしたように、木に順序数を対応させ、全ての有効な切り落としが必ず下延焼するものだという事を証明する。 次のようになる:

  • (+) = \(0\)
  • (+H1H2...Hn) = \(H_1 + H_2 + \cdots + H_n\)
  • (k) = \(\Omega_k\)
  • (kH1H2...Hn) = \(\Omega_k^{H_1} + \Omega_k^{H_2} + \cdots + \Omega_k^{H_n}\)

そして辺は減少されていく。

\(\text{BH}(n)\)関数

\(x\)の辺をもち、\(+,0,\omega,\omega,...,\omega\)とラベルされている木を作る。その木を \(R^n\)とする。全ての\(x\)に対し\(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\)では証明できないが、\(R^x(1)(2)(3)...(k)\)が根のみの木となる\(k\)が必ず存在する。(ここでの記法は、\(R^x\)を取り、\(n = 1\)、\(n = 2\)、\(n = 3\)、…、\(n = k\)で変形することを表す。)

\(\text{BH}(x)\)を\(R^x(1)(2)(3)...(k)\)が根のみの木となるような\(k\)とする。ヒドラ理論によりこの関数は定義可能である。\(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\)ではこれは証明できない。この成長率は\(f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(x)\)に匹敵する。 (\(\psi_0(\varepsilon_{\Omega_\omega + 1})\)はここでは竹内・フェファーマン・ブーフホルツ順序数であり、\(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\)の証明論的強さであることは驚くことではない)

BHの最初の二つの値は簡単に示される: \(\text{BH}(1) = 0\)、\(\text{BH}(2) = 1\)である。 \(\text{BH}(3)\)はとても巨大で、いくらかの最初の操作の過程は右上に画像で示されている。

ブーフホルツのヒドラは計算可能な関数の中で最も強い関数の一つである。バードの配列表記を凌駕し、TREE(n)、そしてSCG(n)も超えるだろうと予測されている。. loader.cや、フリードマンの有限ゲームレイバーのテーブルからなる数よりは小さいだろうし、計算可能なため、ビジービーバー関数よりも小さい。

出典や参考

  • W. Buchholz, An independence result for (Π11 - CA) + BI, Ann. Pure Appl. Logic 33 (1987) 131-155.
  • M. Hamano, M. Okada, A relationship among Gentzen's Proof-Reduction, Kirby-Paris' Hydra Game and Buchholz's Hydra Game, Math. Logic Quart. 43 (1997) 103-120.
  • M. Hamano, M. Okada, A direct independence proof of Buchholz's Hydra Game on finite labeled trees, Arch. Math. Logic 37 (1998) 67-89.
  • L. Kirby, J. Paris, Accessible independence results for Peano Arithmetic, Bull. Lon. Math. Soc. 14 (1982) 285-293.
  • J. Ketonen, R. Solovay, Rapidly growing Ramsey functions, Ann. Math. 113 (1981) 267-314.
  • G. Takeuti, Proof Theory, 2nd Edition, North-Holland, Amsterdam, 1987.
  • W. Buchholz, "An independence result for \(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\)"
Advertisement