クラスカルの木定理

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

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

2004 年に、この結果はロバートソン・シーモア定理として木からグラフへと一般化されました。この定理は逆数学においても重要であることが証明されており、をはるかに上回る、さらに急速増加するSSCG 関数につながります。この定理を有限に適用すると、急速増加するTREE 関数の存在が示されます。 ${\displaystyle {\text{木}}(3)}$

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

ルートを持つ木Tと頂点v、wが与えられたとき、ルートからwへの唯一のパス内に v が含まれる場合は w を v の後継と呼び、さらにvからwへのパス内に他の頂点が含まれない 場合はw をvの直接の後継と呼びます。

X を半順序集合とする。T ₁、T _{2 が}Xにラベル付けされた頂点を持つ根付き木である場合、 T _{1 は}T ₂に無限埋め込み可能であると言い、 T ₁の頂点からT ₂の頂点への入射写像Fが存在して、次のようになる場合は と記述する。 ${\displaystyle T_{1}\leq T_{2}}$

• T ₁のすべての頂点vについて、 vのラベルはのラベルよりも前になります。${\displaystyle F(v)}$
• wがT ₁内のvの後継者である場合は、 は の後継者であり、${\displaystyle F(w)}$${\displaystyle F(v)}$
• w ₁、w _{2 が}vの任意の 2 つの異なる直後の後続である場合、 T ₂のからへのパスにはが含まれます。${\displaystyle F(w_{1})}$${\displaystyle F(w_{2})}$${\displaystyle F(v)}$

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

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

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

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

次のような文がある とします。${\displaystyle P(n)}$

あるm が存在し、T ₁、...、T _{m が}ラベルなしの根付き木の有限シーケンスであり、T _{i が}頂点を持つ場合、ある に対して次の式が成り立ちます。${\displaystyle i+n}$${\displaystyle T_{i}\leq T_{j}}$${\displaystyle i<j}$

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

弱木関数 を最大のmとして定義すると、次のようになります。 ${\displaystyle {\text{木}}(n)}$

ラベルなしの根付き木のシーケンスT ₁ , ..., T _mがあり、各T _iには最大で 個の頂点があり、任意の に対しては が成立しません。${\displaystyle i+n}$${\displaystyle T_{i}\leq T_{j}}$${\displaystyle i<j\leq m}$

、、（約844兆）（ここでグラハム数）、 （ここで引数はラベルの数を指定する。下記参照）はより大きいことが知られている。${\displaystyle {\text{tree}}(1)=2}$${\displaystyle {\text{tree}}(2)=5}$${\displaystyle {\text{tree}}(3)\geq 844,424,930,131,960}$${\displaystyle {\text{tree}}(4)\gg g_{64}}$${\displaystyle g_{64}}$${\displaystyle {\text{TREE}}(3)}$${\displaystyle \mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7).}$

2 つの関数を区別するために、「TREE」(すべて大文字) は大きな TREE 関数であり、「tree」(すべて小文字) は弱いツリー関数です。

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

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

TREE シーケンスは で始まり、その後突然 が爆発的に大きくなり、他の多くの「大きな」組み合わせ定数、たとえばフリードマンの、、およびグラハム数、^{[b] は}それに比べて極めて小さくなります。の下限はであり、したがっての極めて弱い下限はです。^{[c] [9]}たとえば、グラハム数は下限 よりもはるかに小さく、下限は にほぼ等しく、ここで はグラハム関数です。 ${\displaystyle {\text{TREE}}(1)=1}$${\displaystyle {\text{TREE}}(2)=3}$${\displaystyle {\text{TREE}}(3)}$${\displaystyle n(4)}$${\displaystyle n^{n(5)}(5)}$${\displaystyle n(4)}$${\displaystyle {\text{TREE}}(3)}$${\displaystyle A^{A(187196)}(1)}$${\displaystyle A^{A(187196)}(1)}$${\displaystyle g_{3\uparrow ^{187196}3}}$${\displaystyle g_{x}}$

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

^ a Friedmanはもともとこの関数をTR [ n ]と表記した。

^ b n ( k ) は、 k文字のアルファベットで構成できる最長のシーケンスの長さとして定義され、文字ブロック x _i ,...,x _{2 i}はそれ以降のブロック x _j ,...,x _{2 j}の部分列にならない。^[10 ]${\displaystyle n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386}$

^ c 1 つの引数を取る A ( x ) はA ( x , x )と定義されます。ここで、 2 つの引数を取るA ( k , n ) は、次のように定義されるアッカーマン関数の特定のバージョンです: A (1, n ) = 2 n、A ( k +1, 1) = A ( k , 1)、A ( k +1, n +1) = A ( k、A ( k +1, n ))。

引用

文献

• フリードマン、ハーベイ M. (2002)。「内部有限木埋め込み」。ジーク、ウィルフリード、フェファーマン、ソロモン(編)。数学の基礎に関する考察: ソロモン フェファーマンに敬意を表したエッセイ。論理学の講義ノート。第 15 巻。マサチューセッツ州ネイティック: AK ピーターズ。pp. 60–91。ISBN 978-1-56881-170-3MR  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、ツリー定理、および Vazsonyi の予想」(PDF)。アメリカ数学会誌。95 (2)。アメリカ数学会: 210–225。doi : 10.2307 /1993287。JSTOR 1993287。MR  0111704  。
• マルコーネ、アルベルト (2005)。 シンプソン、スティーブン G. (編)。 「2 次演算のサブシステムにおける WQO と BQO 理論」(PDF)。逆数学。 論理学の講義ノート。21。ケンブリッジ:ケンブリッジ大学出版局: 303–330。doi :10.1017/9781316755846.020。ISBN 978-1-316-75584-6。
• Nash-Williams, C. St. JA (1963 年 10 月)。「準整列有限木について」( PDF)  。ケンブリッジ哲学協会数学会報。59 ( 4  ) : 833–835。Bibcode : 1963PCPS ...59..833N。doi :10.1017/S0305004100003844。ISSN 0305-0041。MR 0153601。S2CID 251095188  。
• Rathjen, Michael; Weiermann, Andreas (1993 年 2 月). 「Kruskal の定理に関する証明理論的研究」(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。