タグ: sourceedit |
細 (typo) タグ: ソースの編集 |
||
| (10人の利用者による、間の29版が非表示) | |||
| 2行目: | 2行目: | ||
{{see also|ヒドラゲーム}} |
{{see also|ヒドラゲーム}} |
||
| − | '''ブーフホルツのヒドラ'''は |
+ | '''ブーフホルツのヒドラ''' (Buchholz's hydra) は、ラベル付き木を使って行う一人用 (あるいは二人用) ゲームである。このゲームから定義される関数を \(\text{BH}(n)\)とする。 この関数の増加率は [[竹内・フェファーマン・ブーフホルツ順序数]]で表される。 |
| − | == |
+ | == 準備 == |
| + | ブーフホルツのヒドラで使う用語の定義を行う。 |
||
| − | このゲームは、任意のラベル付き木\(T\) 、そしてその根が特別にラベルされている物(+と呼ぶ)を選ぶところから始まり、そのすべての子は0のラベルを持つ。この木は''ヒドラ''と呼ばれる。 |
||
| + | (単純) '''グラフ'''とは、次の条件を満たす集合\(V,E\)の組\(G=(V,E)\)である： |
||
| − | 一回のステップに置き、二つのパラメータを使い木を変形する。:葉の辺\(a\)、非負整数\(n\)。次のルールに従い木を変更する: |
||
| + | * \(E\)の要素は全て、\(V\)の異なる2つの要素からなる集合である。すなわち、 |
||
| + | *:\(\forall e\in E.\exists v,w\in V.(v\neq w)\land(e=\{v,w\})\) |
||
| + | グラフ\(G=(V,E)\)に対して、\(V\)の要素を\(G\)の'''頂点'''、\(E\)の要素を\(G\)の'''辺'''という。 |
||
| + | 集合\(L\)を、\(L=\mathbb{N}\cup\{\omega,\mathord{+}\}\)で定義する。 |
||
| − | # もし\(a\)のラベルが0なら、[[ヒドラゲーム]]と同じようにする。その辺の親を\(b\)、さらにその親を\(c\)とする。まず\(a\)を消去する。もし\(c\)が存在する(もしくは\(b\)が根でない)なら、\(n\)この\(b\)の複製を作り\(c\)にその子として接属させる。 |
||
| + | ブーフホルツのヒドラゲームには頂点が\(L\)で'''ラベルされた有限根付き木'''という特別なグラフを用いる。すなわち、 |
||
| − | # もし\(a\)のラベルが\(u + 1\)なら、ラベル\(v \leq u\)の辺\(b\)が見つかるまで木をさかのぼる。(その直接上のノードのラベルがすべて0である時に限り、それは存在することが保障されている)\(b\)と\(b\)の根を持つ部分木を考え、その部分木を\(S\)とおく。\(S\)の複製を作り、\(S'\)と呼ぶ。\(S'\)中で、\(b\)を\(u\)で\(a\)を\(0\)でラベルし直す。もともとの木に戻り、\(a\)を\(S'\)で取り換える。 |
||
| + | <dl> |
||
| − | # もし\(a\)のラベルが\(\omega\)なら、単純にそれを\(n + 1\)でラベルし直す。 |
||
| + | <dt>有限</dt><dd>\(V,E\)はいずれも有限集合である。</dd> |
||
| + | <dt>木</dt><dd>任意の2つの頂点が、ただ1つの道で繋がっている。つまり、任意の\(v,w\in V\ (v\neq w)\)に対してある\(v_0,\dots,v_n\)と\(e_1,\dots,e_n\)が存在して\(e_i=\{v_{i-1},v_i\},v_0=v,v_n=w\)が成り立ち、そのような\(v_i,e_i\)がただ1つしか存在しないことが成り立つ。</dd> |
||
| + | <dt>根付き木</dt><dd>木であって、さらに'''根'''と呼ばれる特別な頂点\(r\in V\)が指定されている。</dd> |
||
| + | <dt>頂点が\(L\)でラベルされた</dt><dd>グラフの各頂点に対して\(L\)の要素を対応させる写像\(\ell:V\to L\)が定められている。</dd> |
||
| + | </dl> |
||
| + | が成り立つグラフを用いる。定義から、ラベルされた有限根付き木は頂点の集合、辺の集合、根、ラベルの組\(T=(V,E,r,\ell)\)によって表される。 |
||
| + | ヒドラゲームにおいて有限根付き木を図示する際は、根は他の頂点よりも下側に置かれ、枝分かれしながら上部に辺が伸びるように描かれる。この姿を[[Wikipedia:ja:ヒュドラー|ヒュドラー]]に見立てて、ブーフホルツのヒドラゲームで用いる\(L\)でラベルされた有限根付き木をヒドラと呼ぶ。また、ヒュドラーの伝説になぞらえて、プレーヤーは[[Wikipedia:ja:ヘーラクレース|ヘラクレス]]と呼ばれる。 |
||
| + | '''ヒドラ'''は、頂点が\(L\)でラベルされた有限根付き木であって、さらに以下の条件を満たすものである： |
||
| − | もし\(a\)がヒドラの右端の葉ならば、それを変形された木\(T(n)\)と表記する。 |
||
| + | * 根のラベルは\(\mathord{+}\)である。 |
||
| + | * 根以外の頂点のラベルは、自然数または\(\omega\)である。 |
||
| + | * 根に隣接した頂点のラベルは全て\(0\)である。 |
||
| + | 木において、辺が1つしか接続していない頂点を''葉''と呼ぶ。根でない葉をヒドラの'''頭'''、あるいはトップノード (''top node'')、頭とそこに接続した辺を合わせてヒドラの'''首''' (''head'')と呼ぶことにする。また、首が接続している頂点をその首の'''根本'''と呼ぶことにする。 |
||
| − | ヒドラを変形するのに、葉と整数\(n\)を選ぶ。葉と整数\(n\)の並びを''戦略''とよぶ。戦略がヒドラを根の辺以外なくすことが出来れば、''勝つ戦略'' 、そうでなければ''負ける戦略''と呼ぶ。 |
||
| + | あるヒドラの首が根から直接生えていないならば、首の根本からさらに根の方へ向かう辺がただ1つ存在している。そこでこれを'''親首'''と呼ぶことにする。 |
||
| − | == |
+ | ==規則== |
| + | ターンごとに、ヘラクレスはヒドラの首を1つ選び、それを切り落とす (グラフから除去する)。また、ヒドラは任意の自然数\(n\)を1つ選ぶ (例えば、現在のターン数など)。選んだヒドラの首と自然数に応じて、ヒドラは以下の規則に応じて変形する。 |
||
| − | ブーフホルツは戦略には勝つ戦略しかないとした。これを''ヒドラ理論''という。ヒドラ理論は{{pi11}}で証明不可能であるが、この理論は成立する。 |
||
| − | + | # 切った頭のラベルが0である場合。この時は[[ヒドラゲーム]]と同様にする。すなわち： |
|
| + | #* 切った首の根本が根である場合、首は生えてこない。 |
||
| + | #* 切った首の根本が根でない場合、親首から上側のコピーが、親首の根本から\(n\)本新たに生える。 |
||
| + | # 切った頭のラベルが0でない自然数\(u+1\)である場合。 |
||
| + | ## ラベルが\(u\)以下である、切った頭から根に向かって最初の頂点を\(\rho\)とする。また、頂点\(\rho\)のラベルを\(v\)とする。 |
||
| + | ## ヒドラの\(\rho\)から上の部分を\(S\)とする。\(S\)で\(\rho\)にあたる頂点のラベルを\(u\)にして、切った首が生えていた場所にラベルが0の頭を生やしたものを、元のヒドラの切った首の根本から生やす。 |
||
| + | # 切った頭のラベルが\(\omega\)である場合、切った首の根本からラベルが\(n+1\)である頭が生える。 |
||
| + | 全てのヒドラの首を切り落として根だけにすることができればヘラクレスの勝利となる。ヒドラに対してどの首を落とすかの対応を''戦略''と呼び、その戦略によってヘラクレスが勝つならばそれを''勝つ戦略''、そうでないならば''負ける戦略''と呼ぶ。 |
||
| − | '''証明:'''[[ヒドラゲーム]]でしたように、木に順序数を対応させ、全ての有効な切り落としが必ず下延焼するものだという事を証明する。 次のようになる: |
||
| + | ==ヒドラ定理== |
||
| − | * (+) = \(0\) |
||
| + | ブーフホルツは右端の葉を選び続ける戦略が勝つ戦略であることを示した。その証明において、ブーフホルツは「ヒドラから無限整礎木への標準的な対応が基本列を保つ」という性質を示しているが、ここから直接は「戦略には勝つ戦略しかない」という定理は従わない。この定理を''ヒドラ定理''という。ヒドラ定理は{{pi11}}で証明不可能であり、より強い集合論での証明も明示的に記述されたものは存在しないかもしれない。[https://googology.wikia.org/wiki/Buchholz_hydra Googology Wiki]においてブーフホルツがヒドラ定理を証明したと記載されていたが、少なくとも引用元では証明されていない。 |
||
| − | * (+H<sub>1</sub>H<sub>2</sub>...H<sub>''n''</sub>) = \(H_1 + H_2 + \cdots + H_n\) |
||
| − | * (k) = \(\Omega_k\) |
||
| − | * (kH<sub>1</sub>H<sub>2</sub>...H<sub>''n''</sub>) = \(\Omega_k^{H_1} + \Omega_k^{H_2} + \cdots + \Omega_k^{H_n}\) |
||
| + | ヒドラ定理には無限のヒドラは適用''不可能''である;次を見よ、[[ヒドラゲーム#無限のバリアント|section]] |
||
| − | そして辺は減少されていく。 |
||
==\(\text{BH}(n)\)関数== |
==\(\text{BH}(n)\)関数== |
||
| − | \(x\)の辺をもち、\(+,0,\omega,\omega,...,\omega\)とラベルされている木を作る。その木を |
+ | \(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\)とする。ヒドラ理 |
+ | \(\text{BH}(x)\)を\(R^x(1)(2)(3)...(k)\)が根のみの木となるような\(k\)とする。ヒドラ定理によりこの関数は定義可能である。{{pi11}}でこの関数の全域性は証明できないと推測される。実際ブーフホルツは\(\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})\)は[[竹内・フェファーマン・ブーフホルツ順序数]]である。驚くべきことではないが、この順序数は{{pi11}}の[[証明論的順序数]]である。 |
| − | BHの最初の二つの値は簡単に示される: |
+ | BHの最初の二つの値は簡単に示される:\(\text{BH}(1) = 0\)、\(\text{BH}(2) = 1\)である。\(\text{BH}(3)\)はとても巨大で、いくらかの最初の操作の過程は右上に画像で示されている。 |
| − | ブーフホルツのヒドラは計算可能な関数の中で |
+ | ブーフホルツのヒドラは計算可能な関数の中でも強い関数の一つである。[[TREE数列|TREE(n)]]、そして[[サブキュービックグラフ数|SCG(n)]]を超えるだろうと予測されている。[[ローダー数|loader.c]]や、[[有限約束ゲーム]]、[[レイバーのテーブル]]からなる数よりは小さいだろうし、計算可能なため、[[ビジービーバー関数]]よりも小さい。 |
==出典や参考== |
==出典や参考== |
||
| − | * W. Buchholz, An independence result for |
+ | * W. Buchholz, [http://epub.ub.uni-muenchen.de/3842/1/buchholz_wilfried_3842.pdf "An independence result for {{pi11}}"]. Annals of Pure and Applied Logic, Vol. 33, pp. 131–155 (1987). doi:[https://doi.org/10.1016/0168-0072(87)90078-9 10.1016/0168-0072(87)90078-9] |
* 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 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. |
* M. Hamano, M. Okada, A direct independence proof of Buchholz's Hydra Game on finite labeled trees, Arch. Math. Logic 37 (1998) 67-89. |
||
| 47行目: | 65行目: | ||
* J. Ketonen, R. Solovay, Rapidly growing Ramsey functions, Ann. Math. 113 (1981) 267-314. |
* J. Ketonen, R. Solovay, Rapidly growing Ramsey functions, Ann. Math. 113 (1981) 267-314. |
||
* G. Takeuti, Proof Theory, 2nd Edition, North-Holland, Amsterdam, 1987. |
* G. Takeuti, Proof Theory, 2nd Edition, North-Holland, Amsterdam, 1987. |
||
| + | |||
| − | * W. Buchholz, [http://epub.ub.uni-muenchen.de/3842/1/buchholz_wilfried_3842.pdf "An independence result for {{pi11}}"] |
||
{{DEFAULTSORT:ふうふほるつのひとら}} |
{{DEFAULTSORT:ふうふほるつのひとら}} |
||
| 55行目: | 73行目: | ||
[[カテゴリ:組合せ数学]] |
[[カテゴリ:組合せ数学]] |
||
[[カテゴリ:ゲーム]] |
[[カテゴリ:ゲーム]] |
||
| − | [[カテゴリ: |
+ | [[カテゴリ:ブーフホルツのヒドラ]] |
| + | [[カテゴリ:ブーフホルツのψ関数]] |
||
| + | [[カテゴリ:数理論理学]] |
||
| + | [[カテゴリ:証明論]] |
||
| + | [[カテゴリ:定理]] |
||
2021年7月13日 (火) 09:34時点における版
- ヒドラゲーム も参照して下さい。
ブーフホルツのヒドラ (Buchholz's hydra) は、ラベル付き木を使って行う一人用 (あるいは二人用) ゲームである。このゲームから定義される関数を \(\text{BH}(n)\)とする。 この関数の増加率は 竹内・フェファーマン・ブーフホルツ順序数で表される。
準備
ブーフホルツのヒドラで使う用語の定義を行う。
(単純) グラフとは、次の条件を満たす集合\(V,E\)の組\(G=(V,E)\)である：
- \(E\)の要素は全て、\(V\)の異なる2つの要素からなる集合である。すなわち、
- \(\forall e\in E.\exists v,w\in V.(v\neq w)\land(e=\{v,w\})\)
グラフ\(G=(V,E)\)に対して、\(V\)の要素を\(G\)の頂点、\(E\)の要素を\(G\)の辺という。
集合\(L\)を、\(L=\mathbb{N}\cup\{\omega,\mathord{+}\}\)で定義する。 ブーフホルツのヒドラゲームには頂点が\(L\)でラベルされた有限根付き木という特別なグラフを用いる。すなわち、
- 有限
- \(V,E\)はいずれも有限集合である。
- 木
- 任意の2つの頂点が、ただ1つの道で繋がっている。つまり、任意の\(v,w\in V\ (v\neq w)\)に対してある\(v_0,\dots,v_n\)と\(e_1,\dots,e_n\)が存在して\(e_i=\{v_{i-1},v_i\},v_0=v,v_n=w\)が成り立ち、そのような\(v_i,e_i\)がただ1つしか存在しないことが成り立つ。
- 根付き木
- 木であって、さらに根と呼ばれる特別な頂点\(r\in V\)が指定されている。
- 頂点が\(L\)でラベルされた
- グラフの各頂点に対して\(L\)の要素を対応させる写像\(\ell:V\to L\)が定められている。
が成り立つグラフを用いる。定義から、ラベルされた有限根付き木は頂点の集合、辺の集合、根、ラベルの組\(T=(V,E,r,\ell)\)によって表される。 ヒドラゲームにおいて有限根付き木を図示する際は、根は他の頂点よりも下側に置かれ、枝分かれしながら上部に辺が伸びるように描かれる。この姿をヒュドラーに見立てて、ブーフホルツのヒドラゲームで用いる\(L\)でラベルされた有限根付き木をヒドラと呼ぶ。また、ヒュドラーの伝説になぞらえて、プレーヤーはヘラクレスと呼ばれる。
ヒドラは、頂点が\(L\)でラベルされた有限根付き木であって、さらに以下の条件を満たすものである：
- 根のラベルは\(\mathord{+}\)である。
- 根以外の頂点のラベルは、自然数または\(\omega\)である。
- 根に隣接した頂点のラベルは全て\(0\)である。
木において、辺が1つしか接続していない頂点を葉と呼ぶ。根でない葉をヒドラの頭、あるいはトップノード (top node)、頭とそこに接続した辺を合わせてヒドラの首 (head)と呼ぶことにする。また、首が接続している頂点をその首の根本と呼ぶことにする。 あるヒドラの首が根から直接生えていないならば、首の根本からさらに根の方へ向かう辺がただ1つ存在している。そこでこれを親首と呼ぶことにする。
規則
ターンごとに、ヘラクレスはヒドラの首を1つ選び、それを切り落とす (グラフから除去する)。また、ヒドラは任意の自然数\(n\)を1つ選ぶ (例えば、現在のターン数など)。選んだヒドラの首と自然数に応じて、ヒドラは以下の規則に応じて変形する。
- 切った頭のラベルが0である場合。この時はヒドラゲームと同様にする。すなわち：
- 切った首の根本が根である場合、首は生えてこない。
- 切った首の根本が根でない場合、親首から上側のコピーが、親首の根本から\(n\)本新たに生える。
- 切った頭のラベルが0でない自然数\(u+1\)である場合。
- ラベルが\(u\)以下である、切った頭から根に向かって最初の頂点を\(\rho\)とする。また、頂点\(\rho\)のラベルを\(v\)とする。
- ヒドラの\(\rho\)から上の部分を\(S\)とする。\(S\)で\(\rho\)にあたる頂点のラベルを\(u\)にして、切った首が生えていた場所にラベルが0の頭を生やしたものを、元のヒドラの切った首の根本から生やす。
- 切った頭のラベルが\(\omega\)である場合、切った首の根本からラベルが\(n+1\)である頭が生える。
全てのヒドラの首を切り落として根だけにすることができればヘラクレスの勝利となる。ヒドラに対してどの首を落とすかの対応を戦略と呼び、その戦略によってヘラクレスが勝つならばそれを勝つ戦略、そうでないならば負ける戦略と呼ぶ。
ヒドラ定理
ブーフホルツは右端の葉を選び続ける戦略が勝つ戦略であることを示した。その証明において、ブーフホルツは「ヒドラから無限整礎木への標準的な対応が基本列を保つ」という性質を示しているが、ここから直接は「戦略には勝つ戦略しかない」という定理は従わない。この定理をヒドラ定理という。ヒドラ定理は\(\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 \(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\)". Annals of Pure and Applied Logic, Vol. 33, pp. 131–155 (1987). doi:10.1016/0168-0072(87)90078-9
- 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.