変更：ブーフホルツのヒドラ

2020年5月15日 (金) 10:16時点における版

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

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

規則

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

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

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

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

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

ヒドラ定理

ブーフホルツは右端の葉を選び続ける戦略が勝つ戦略であることを示した。その証明において、ブーフホルツは「ヒドラから順序数への標準的な対応が基本列を保つ」という性質を示しており、ここから更に強く、戦略には勝つ戦略しかないという定理が従う。この定理をヒドラ定理という。ヒドラ定理は\(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\)で証明不可能であるが、よりZFC集合論等の強い集合論では成立する。

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

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

(+) = \(0\)
(+H₁H₂...H_n) = \(H_1 + H_2 + \cdots + H_n\)
(k) = \(\Omega_k\)
(kH₁H₂...H_n) = \(\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\)はブーフホルツのψ関数であり、\(\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}\)"

@@ 17行目: / 17行目: @@
 ヒドラを変形するのに、葉と整数\(n\)を選ぶ。葉と整数\(n\)の並びを''戦略''とよぶ。戦略がヒドラを根の辺以外なくすことが出来れば、''勝つ戦略'' 、そうでなければ''負ける戦略''と呼ぶ。
-==ヒドラ理論==
+==ヒドラ定理==
-ブーフホルツは右端の葉を選び続ける戦略が勝つ戦略であることを示した。その証明において、ブーフホルツは「ヒドラから順序数への標準的な対応が基本列を保つ」という性質を示しており、ここから更に強く、戦略には勝つ戦略しかないという定理が従う。この定理を''ヒドラ理論''という。ヒドラ理論は{{pi11}}で証明不可能であるが、よりZFC集合論等の強い集合論では成立する。
+ブーフホルツは右端の葉を選び続ける戦略が勝つ戦略であることを示した。その証明において、ブーフホルツは「ヒドラから順序数への標準的な対応が基本列を保つ」という性質を示しており、ここから更に強く、戦略には勝つ戦略しかないという定理が従う。この定理を''ヒドラ定理''という。ヒドラ定理は{{pi11}}で証明不可能であるが、よりZFC集合論等の強い集合論では成立する。
-ヒドラ理論には無限のヒドラは適用''不可能''である;次を見よ、[[ヒドラゲーム#無限のバリアント|section]]
+ヒドラ定理には無限のヒドラは適用''不可能''である;次を見よ、[[ヒドラゲーム#無限のバリアント|section]]
 '''証明:'''[[ヒドラゲーム]]でしたように、木に順序数を対応させ、全ての有効な切り落としが必ず下延焼するものだという事を証明する。 次のようになる:
@@ 34行目: / 34行目: @@
 \(x\)の辺をもち、\(+,0,\omega,\omega,...,\omega\)とラベルされている木を作る。その木を\(R^n\)とする。全ての\(x\)に対し{{pi11}}では証明できないが、\(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\)とする。ヒドラ理論によりこの関数は定義可能である。{{pi11}}ではこれは証明できない。この成長率は\(f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(x)\)に匹敵する。(\(\psi_0(\varepsilon_{\Omega_\omega + 1})\)はここでは[[竹内・フェファーマン・ブーフホルツ順序数]]であり、{{pi11}}の証明論的強さであることは驚くことではない)
+\(\text{BH}(x)\)を\(R^x(1)(2)(3)...(k)\)が根のみの木となるような\(k\)とする。ヒドラ定理によりこの関数は定義可能である。{{pi11}}ではこれは証明できない。この成長率は\(f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(x)\)に匹敵すると信じられている。ここで\(\psi\)は[[ψ関数|ブーフホルツのψ関数]]であり、\(\psi_0(\varepsilon_{\Omega_\omega + 1})\)は[[竹内・フェファーマン・ブーフホルツ順序数]]である。驚くべきことではないが、この順序数は{{pi11}}の証明論的強さである。
 BHの最初の二つの値は簡単に示される:\(\text{BH}(1) = 0\)、\(\text{BH}(2) = 1\)である。\(\text{BH}(3)\)はとても巨大で、いくらかの最初の操作の過程は右上に画像で示されている。