クラスカルの木定理

Well-quasi-ordering of finite trees

数学において、クラスカルの木定理は、ラベルの準順序付き集合上の有限木の集合は、それ自体が同相埋め込みの下で準順序付きであることを述べています

この定理を有限に適用すると、急激に増加するTREE関数の存在が示される。TREE(3)は、グラハム数やグーゴルプレックスなどの他の大きな数をはるかに凌駕する、単純に定義された最大の有限数の一つであると広く認められている。^[1]

歴史

この定理はアンドリュー・ヴァゾーニによって予想され、ジョセフ・クラスカル（1960年）によって証明されました 。簡潔な証明は クリスピン・ナッシュ＝ウィリアムズ （1963年）によって与えられました。それ以来、この定理はATR ₀（算術的超限再帰の形を持つ二階算術理論）では証明できない命題として、逆数学における顕著な例となっています

2004 年に、この結果はロバートソン・シーモア定理としてツリーからグラフへと一般化され、この結果は逆数学においても重要であることが証明され、TREE を凌駕する、さらに急速に増加するSSCG 関数につながっています。

記述

ここで示されているバージョンはナッシュ＝ウィリアムズによって証明されたものです。クラスカルの定式化はやや強力です。ここで検討するすべての木は有限です

ルートを持つツリーと、頂点 、 が与えられた場合、ルート から への一意のパスがを含む場合はの子孫を呼び出し、さらに からへのパスに他の頂点が含まれない場合はの子を呼び出します。 ${\displaystyle T}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle w}$

を半順序集合とします。、 が にラベル付けされた頂点を持つ根付き木である場合、はに無限埋め込み可能であると言い、の頂点から の頂点への入射的な写像が存在し、次の条件を満たす場合、 と書きます。 ${\displaystyle (X,\leq _{X})}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle X}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}\leq T_{2}}$ ${\displaystyle F}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

• のすべての頂点について、 のラベルはのラベルです。 ${\displaystyle v}$ ${\displaystyle T_{1}}$ ${\displaystyle v}$ ${\displaystyle \leq _{X}}$ ${\displaystyle F(v)}$
• が内の の子孫である場合、は の子孫であり、かつ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle T_{1}}$ ${\displaystyle F(w)}$ ${\displaystyle F(v)}$
• 、が の任意の 2 つの異なる子である場合、におけるからへのパスにはが含まれます(同様に、とは異なるサブツリーにあります)。 ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle v}$ ${\displaystyle F(w_{1})}$ ${\displaystyle F(w_{2})}$ ${\displaystyle T_{2}}$ ${\displaystyle F(v)}$ ${\displaystyle F(w_{1})}$ ${\displaystyle F(w_{2})}$

クラスカルの木定理は次のように述べます。

が準順序付けされている場合、 のラベルを持つ根付き木の集合は、上で定義した無限埋め込み可能順序の下で準順序付けされています。（つまり、でラベル付けされた根付き木の無限シーケンスが与えられたとき、となるものが存在し、となります。） ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle T_{1},T_{2},\ldots }$ ${\displaystyle X}$ ${\displaystyle i<j}$ ${\displaystyle T_{i}\leq T_{j}}$

フリードマンの研究

可算ラベル集合に対して、クラスカルの木定理は二階算術を用いて表現および証明できます。しかし、グッドスタインの定理やパリス・ハリントンの定理と同様に、定理のいくつかの特殊なケースや変種は、証明可能な部分系よりもはるかに弱い二階算術の部分系で表現できます。これは1980年代初頭にハーヴェイ・フリードマンによって初めて観察され、当時まだ黎明期にあった逆数学の分野の初期の成功でした。上記の木がラベルなしとされる場合（つまり、サイズが1の場合）、フリードマンは結果がATR ₀^{では証明不可能であることを発見しました。 [2]}これは、述語的結果と証明可能非述語的証明の最初の例を示しています。 ^[3]この定理の場合も、Πによって証明可能です ${\displaystyle X}$ ${\displaystyle X}$¹
₁-CA _{0 で}あるが、上記の木構造上の順序の定義に「ギャップ条件」^{[4]を加えることで、このシステムでは証明できない定理の自然な変化を見出した。 [5] [6]}ずっと後になって、ロバートソン・シーモアの定理は、Π¹
₁-CA ₀

順序数分析はクラスカルの定理の強さを裏付けており、定理の証明論的順序数は小さなヴェブレン順序数（より小さなアッカーマン順序数と混同されることがある）に等しい。^[7]

弱木関数

次の命題があると仮定します。 ${\displaystyle P(n)}$

がラベルなし根付き木の有限列で、頂点が 個あるとき、 が成り立つようなものが存在し、に対して が成り立つ ${\displaystyle m}$ ${\displaystyle T_{1},\ldots ,T_{m}}$ ${\displaystyle T_{i}}$ ${\displaystyle i+n}$ ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j}$

すべてのステートメントは、クラスカルの定理とケーニヒの補題の結果として真です。各 に対して、ペアノ算術はが真であることを証明できますが、 ステートメント「はすべて に対して真である」は証明できません。^[8]さらに、ペアノ算術におけるの 最短の証明の長さはの関数として驚異的に速く増加し、たとえばあらゆる原始再帰関数やアッカーマン関数よりもはるかに速く増加します。 ^[要出典]が成り立つの最小値は、同様に とともに極めて急速に増加します。 ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle P(n)}$ ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle P(n)}$ ${\displaystyle n}$

フリードマンは、以下のTREE関数の弱バージョンである以下の関数を定義しました。正の整数 に対して、を最大のものとし、以下の式が成り立ちます。 ${\displaystyle n}$ ${\displaystyle {\text{FFF}}(n)}$ ${\displaystyle m}$

それぞれが頂点を持つ根付き木のシーケンスが存在しますが、どの に対しても は成り立ちません。 ${\displaystyle T_{1},\ldots ,T_{m}}$ ${\displaystyle T_{i}}$ ${\displaystyle i+n-1}$ ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j\leq m}$

フリードマンはこの数列の最初の数項を、、、、と計算した。彼はまた、が100未満であると推定するが、突然非常に大きな値に爆発する。ペアノ算術における証明は少なくとも^{[c]個の記号を必要とするが、} ACA ₀においては最大10,000個の記号で存在が証明できる。 ^[9] ${\displaystyle {\text{FFF}}(1)=1}$ ${\displaystyle {\text{FFF}}(2)=2}$ ${\displaystyle {\text{FFF}}(3)=5}$ ${\displaystyle {\text{FFF}}(4)}$ ${\displaystyle {\text{FFF}}(5)}$ ${\displaystyle {\text{FFF}}(5)}$ ${\displaystyle A(10)}$

TREE関数

3つのラベル（青 < 赤 < 緑）の集合からラベル付けされた根付き木のシーケンス。シーケンス内の 番目の木には最大で個の頂点が含まれ、シーケンス内の後続の木に無限埋め込み可能な木はありません。は、そのようなシーケンスの可能な最大の長さとして定義されます ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\text{TREE}}(3)}$

フリードマンはラベルを組み込むことで、はるかに速く増加する関数を定義しました。^[10]正の整数 に対して、^[a]を最大値とすると、次のようになります。 ${\displaystyle n}$ ${\displaystyle {\text{TREE}}(n)}$ ${\displaystyle m}$

ラベルのセットからラベル付けされた根付き木のシーケンスがあり、各 には最大で個の頂点があり、任意の に対して は成り立ちません。 ${\displaystyle T_{1},\ldots ,T_{m}}$ ${\displaystyle n}$ ${\displaystyle T_{i}}$ ${\displaystyle i}$ ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j\leq m}$

クラスカルの定理は、任意のに対して が有限であることを主張する。TREE関数は、最終的に、ACA ₀ + Π系のすべての証明可能な再帰関数を支配する。 ${\displaystyle {\text{TREE}}(n)}$ ${\displaystyle n}$¹
₂-BI. ^[10]

数列は で始まり、その後突然爆発的に大きな値になり、フリードマン数やグラハム数 のような他の多くの「大きな」組合せ定数[ b ]^は比較すると極めて小さくなります。の下限値、したがって の極めて弱い下限値は^[c]です。ここではアッカーマン関数の単一引数バージョンであり、 と定義されます。^{[10] [11]} ${\displaystyle {\text{TREE}}(1)=1}$ ${\displaystyle {\text{TREE}}(2)=3}$ ${\displaystyle {\text{TREE}}(3)}$ ${\displaystyle n(4)}$ ${\displaystyle n(4)}$ ${\displaystyle {\text{TREE}}(3)}$ ${\displaystyle A^{A(187196)}(1)}$ ${\displaystyle A(x)}$ ${\displaystyle A(x)=A(x,x)}$

フリードマンは、 ACA ₀ + Πで停止することが証明できるあらゆるチューリングマシンの停止時間よりも大きいことを示した。 ${\displaystyle {\text{TREE}}(3)}$¹
₂-BIは最大^[d]個の記号を持ち、ここでテトレーションを表す。^[10] ${\displaystyle 2\uparrow \uparrow 1000}$ ${\displaystyle \uparrow \uparrow }$

参照

• パリス・ハリントンの定理
• 金森・マカルーンの定理
• ロバートソン・シーモア定理

注釈

^ a Friedmanはもともとこの関数を と表記しました ${\displaystyle {\text{TR}}[n]}$

^ b は、文字のアルファベットで構成できる最長のシーケンスの長さとして定義され、どの文字ブロックも後続のブロックの部分シーケンスにならないようにします。^[12]たとえば、、、などです。 ${\displaystyle n(k)}$ ${\displaystyle k}$ ${\displaystyle x_{i},\ldots ,x_{2i}}$ ${\displaystyle x_{j},\ldots ,x_{2j}}$ ${\displaystyle n(1)=3}$ ${\displaystyle n(2)=11}$ ${\displaystyle n(3)>2\uparrow ^{7197}158386}$

^ c 上付き文字は反復を表します。例えば、は を計算することを意味します。 ${\displaystyle A^{3}(1)}$ ${\displaystyle A(A(A(1)))}$

^ d フリードマンは実際にはこれを2 ^[1000]と書き、これは彼の記法では高さ1000の2の指数関数的積み重ねを表しています。^[13]

参考文献

引用

1. 「TREE(3)という数字の巨大さは理解を超えている」『ポピュラーメカニクス』2017年10月20日。2025年2月4日閲覧
2. シンプソン 1985、定理1.8
3. フリードマン 2002, p. 60
4. シンプソン 1985、定義4.1
5. シンプソン 1985、定理5.14
6. マルコーネ 2005、8～9ページ
7. ラトジェン＆ワイアーマン 1993.
8. スミス 1985, 120ページ
9. Friedman, Harvey. 「289: FFFにおける整数閾値」オハイオ州立大学数学科. 2024年2月28日時点のオリジナルよりアーカイブ。
10. Friedman, Harvey (2006年3月28日). "273:Sigma01/optimal/size".オハイオ州立大学数学科. 2024年9月18日時点のオリジナルよりアーカイブ。 2017年8月8日閲覧。
11. Friedman, Harvey M. (2000年6月1日). 「実生活における膨大な整数」(PDF) .オハイオ州立大学. 2017年8月8日閲覧。
12. Friedman, Harvey M. (1998年10月8日). 「Long Finite Sequences」(PDF) .オハイオ州立大学数学科. pp. 5, 48 (Thm.6.8) . 2017年8月8日閲覧。
13. フリードマン、ハーヴェイ。「[FOM] 271:スミス論文の明確化」オハイオ州立大学数学科。2024年2月26日時点のオリジナルよりアーカイブ。

参考文献

• フリードマン、ハーヴェイ・M. (2002). 「内部有限木埋め込み」. ジーク、ウィルフリード、フェファーマン、ソロモン（編）. 『数学の基礎に関する考察：ソロモン・フェファーマンに敬意を表したエッセイ集』 . 論理学講義ノート. 第15巻. マサチューセッツ州ネイティック：AKピーターズ. pp.  60– 91. ISBN 978-1-56881-170-3. MR  1943303.
• H. Gallier, Jean (1991年9月). 「クラスカルの定理と順序数Γ0の何が特別なのか？証明論におけるいくつかの結果の概観」(PDF) . Annals of Pure and Applied Logic . 53 (3): 199– 260. doi : 10.1016/0168-0072(91)90022-E . MR  1129778
• Kruskal, JB (1960年5月). 「Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture」(PDF) .アメリカ数学会誌. 95 (2).アメリカ数学会誌: 210–225 . doi :10.2307/1993287. JSTOR  1993287. MR  0111704.
• マルコーネ、アルベルト (2005). シンプソン、スティーブン G. (編). 「二階算術サブシステムにおけるWQOとBQO理論」(PDF) .逆数学. 論理学講義ノート. 21.ケンブリッジ:ケンブリッジ大学出版局. 303– 330. doi :10.1017/9781316755846.020. ISBN 978-1-316-75584-6。
• ナッシュ＝ウィリアムズ、C. St. JA (1963年10月). 「準順序有限木について」(PDF) .ケンブリッジ哲学協会数学紀要. 59 (4): 833– 835.書誌コード: 1963PCPS...59..833N. doi : 10.1017/S0305004100003844. ISSN  0305-0041. MR  0153601. S2CID  251095188
• ラスジェン, マイケル; ワイアーマン, アンドレアス (1993年2月). 「クラスカルの定理に関する証明理論的研究」(PDF) . Annals of Pure and Applied Logic . 60 (1): 49– 88. doi :10.1016/0168-0072(93)90192-G. MR  1212407.
• シンプソン, スティーブン・G. (1985). 「有限木の特定の組合せ論的性質の証明不可能性」. フリードマン, ハーヴェイ・フリードマン著、ハリントン, LA著、スセドロフ, A.著、他編. 『数学の基礎に関するハーヴェイ・フリードマンの研究』. 『論理学と数学の基礎に関する研究』. アムステルダム; ニューヨーク:ノースホランド. pp.  87– 117. ISBN 978-0-444-87834-2。
• スミス、リック・L. (1985). 「ヒグマン定理とクラスカル定理のいくつかの有限形式の無矛盾性強度」.フリードマン、ハーヴェイ、ハリントン、LA (編).ハーヴェイ・フリードマンの数学基礎に関する研究. 論理学と数学基礎の研究. 第117巻. アムステルダム; ニューヨーク:ノースホランド. pp.  119– 136. doi :10.1016/s0049-237x(09)70157-0. ISBN 978-0-444-87834-2。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Kruskal%27s_tree_theorem&oldid=1319400971#TREE_function"