ブーフホルツのヒドラ

ヒドラゲーム も参照して下さい。

ブーフホルツのヒドラ (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}\)で証明不可能であり、より強い集合論での証明も明示的に記述されたものは存在しないかもしれない。Googology Wikiにおいてブーフホルツがヒドラ定理を証明したと記載されていたが、少なくとも引用元では証明されていない。

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

\(\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}\)でこの関数の全域性は証明できないと推測される。実際ブーフホルツは\(\lambda n.H_{D_0D_\nu^n0(1)}\)というヒドラから誘導される関数が\(\mathsf{ID}_\nu\)にて可証全域ではないことを示した．よってこの成長率は\(f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(x)\)に匹敵すると信じられている。ここで\(\psi\)はブーフホルツのψ関数であり、\(\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}\)"