グッドスタインの定理

数理論理学において、グッドスタインの定理は、 1944 年にルーベン・グッドスタインによって証明された自然数に関する命題であり、グッドスタイン数列(以下で定義) はすべて最終的に 0 で終わると述べている。ローレンス・カービーとジェフ・パリス^{[ 1 ]}は 1982 年に、グッドスタインの定理はペアノ算術では証明不可能であることを示した(ただし、2 階算術やツェルメロ・フレンケル集合論などのより強力な体系では証明可能)。これは、ゲーデルの不完全性定理とゲルハルト・ゲンツェンによる 1943 年のペアノ算術におけるε ₀帰納法の証明不可能性の直接証明に続く、ペアノ算術では証明不可能な自然数に関する真の命題の 3 番目の例であった。パリス・ハリントンの定理は別の例を示した。

カービーとパリスは、グッドスタイン数列と同様の挙動を示すグラフ理論的なヒドラゲームも導入した。「ヒドラ」（レルナの神話上の多頭のヒドラにちなんで名付けられた）は根付き木であり、「ヘラクレス」の動きは、その「頭」（木の枝）の1つを切り落とすことであり、ヒドラは特定の規則に従って有限個の新しい頭を生やすことで反応する。カービーとパリスは、ヘラクレスがヒドラの頭を切り落とすためにどのような戦略を用いるかにかかわらず、ヒドラは最終的に殺されることを証明したが、これには非常に長い時間がかかる可能性がある。グッドスタイン数列の場合と同様に、カービーとパリスは、ペアノ算術だけでは証明できないことを示した。^{[ 1 ]}

グッドスタイン数列は、「遺伝的基数n表記法」と呼ばれる概念に基づいて定義されます。この表記法は、自然数の通常の基数n位取り記数法と非常によく似ていますが、通常の表記法ではグッドスタインの定理の目的には不十分です。

通常の基数n表記法（nは 1 より大きい自然数）を実現するには、任意の自然数m をnのべき乗の倍数の和として表します。

${\displaystyle m=a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0},}$

ここで、各係数a _{i は}0 ≤ a _i < n を満たし、a _k ≠ 0 である。

例えば、100の3進数表記は次のようになります。

${\displaystyle 100=81+18+1=3^{4}+2\cdot 3^{2}+3^{0}.}$

ここでは、上記のケース 3 ^{4に見られるように、} nの指数自体はn を基数とする表記では書かれていません。

n進数表記を遺伝的n進数表記に変換するには、まずすべての指数をnのべき乗の和として書き直します(係数の制限は0 ≤ a _i < nです)。次に、指数内の任意の指数を再びn進数表記で書き直し (係数の制限は同じです)、式に現れるすべての数 (基数自体を除く) がn進数表記で書かれるまで、この手順を繰り返します。

例えば、遺伝的3進数表記の100は

${\displaystyle 100=3^{3^{1}+1}+2\cdot 3^{2}+1.}$

グッドスタインシーケンス${\displaystyle G_{m}}$数mの列は自然数の数列です。数列の最初の要素は次のように書きます。${\displaystyle G_{m}(1)}$は、m自体です。2 番目の要素は、${\displaystyle G_{m}(2)}$は、 m を遺伝的基数 2 表記で書き、すべての 2 を 3 に変更し、結果から 1 を引くことによって得られます。一般に、この項は${\displaystyle G_{m}(n+1)}$mのグッドスタイン数列は次のように計算されます。

• 遺伝的基底( n +1 )表現をとる${\displaystyle G_{m}(n)}$、
• 基数 ( n + 1 )の各出現箇所をn + 2に置き換え、
• 1を引く。

${\displaystyle G_{m}(n+1)}$両方に依存する${\displaystyle G_{m}(n)}$そしてインデックスnについて。${\displaystyle G_{m}(n)}$次のように書かれています${\displaystyle G_{n-1}(m)}$[ ^{2 ]​}

グッドスタイン数列は、その要素が 0 に達したときに終了します。初期のグッドスタイン数列はすぐに終了します。たとえば、${\displaystyle G_{3}}$6番目のステップで終了します（「遺伝的表記」とラベル付けされた列は、値の計算方法を示しています）。

後期のグッドスタイン数列は非常に多くのステップにわたって増加します。例えば、${\displaystyle G_{4}}$以下のように始まります（OEIS：A056193 ）：

要素${\displaystyle G_{4}}$しばらくは増加し続けるが、ベースラインでは${\displaystyle 3\cdot 2^{402\,653\,209}}$最大に達する${\displaystyle 3\cdot 2^{402\,653\,210}-1}$次の期間そこに滞在する${\displaystyle 3\cdot 2^{402\,653\,209}}$階段を上り、その後 1 ずつ下り始め、ベースが 0 に達すると 0 になります。${\displaystyle 3\cdot 2^{402\,653\,211}-1.}$ここでの指数は${\displaystyle 3\cdot 2^{27}+27,}$^{[ 3 ]}したがって、基数は${\displaystyle n\cdot 2^{n}-1,}$ウッドール数​${\displaystyle n=3\cdot 2^{27}.}$

別の例として、${\displaystyle G_{19}}$増加速度ははるかに速く、以下のように始まります。

このような急速な増加にもかかわらず、グッドスタインの定理によれば、開始値が何であれ、すべてのグッドスタイン数列は最終的に0で終了する。

グッドスタインの定理は、（ペアノ算術以外の手法を用いて、以下参照）次のように証明できます。グッドスタイン数列が与えられた場合${\displaystyle G_{m}}$並列シーケンスを構築する${\displaystyle P_{m}}$カントール標準形における順序数の、厳密に減少し、有限である。この証明のよくある誤解は、${\displaystyle G_{m}}$行く${\displaystyle 0}$なぜならそれは${\displaystyle P_{m}}$実際、${\displaystyle P_{m}}$支配する${\displaystyle G_{m}}$全く役割を果たさない。重要な点は次のとおりです。${\displaystyle G_{m}(k)}$存在するのは、${\displaystyle P_{m}(k)}$（並列性）が存在し、2 つのメンバー間の比較${\displaystyle G_{m}}$対応するエントリを比較する際に保持されます。${\displaystyle P_{m}}$[ ^{4 ]}ならば^​${\displaystyle P_{m}}$終了するので、${\displaystyle G_{m}}$無限後退により、${\displaystyle G_{m}}$到達しなければならない${\displaystyle 0}$これは、契約解除を保証するものです。

関数を定義します${\displaystyle f=f(u,k)}$遺伝的塩基を計算する${\displaystyle k}$の表現${\displaystyle u}$そして、ベースとなる各出現箇所を置き換える${\displaystyle k}$最初の無限序数で${\displaystyle \omega }$。 例えば、${\displaystyle f(100,3)=f(3^{3^{1}+1}+2\cdot 3^{2}+1,3)=\omega ^{\omega ^{1}+1}+\omega ^{2}\cdot 2+1=\omega ^{\omega +1}+\omega ^{2}\cdot 2+1}$。

各学期${\displaystyle P_{m}(n)}$シーケンスの${\displaystyle P_{m}}$は次のように定義される。${\displaystyle f(G_{m}(n),n+1)}$。 例えば、${\displaystyle G_{3}(1)=3=2^{1}+2^{0}}$そして${\displaystyle P_{3}(1)=f(2^{1}+2^{0},2)=\omega ^{1}+\omega ^{0}=\omega +1}$序数の加算、乗算、べき乗は明確に定義されている。

私たちは主張します${\displaystyle f(G_{m}(n),n+1)>f(G_{m}(n+1),n+2)}$:

させて${\displaystyle G'_{m}(n)}$なれ${\displaystyle G_{m}(n)}$グッドスタイン配列の次の要素を生成する際に、最初の塩基置換操作を適用した後 、ただしこの生成における2番目のマイナス1操作の前に、次の点に注目してください。${\displaystyle G_{m}(n+1)=G'_{m}(n)-1}$。

それから${\displaystyle f(G_{m}(n),n+1)=f(G'_{m}(n),n+2)}$[^{注1 ]}ここでマイナス1演算^を適用し、${\displaystyle f(G'_{m}(n),n+2)>f(G_{m}(n+1),n+2)}$、 として${\displaystyle G'_{m}(n)=G_{m}(n+1)+1}$[^{注2 ]}

例えば、${\displaystyle G_{4}(1)=2^{2}}$そして${\displaystyle G_{4}(2)=2\cdot 3^{2}+2\cdot 3+2}$、 それで${\displaystyle f(2^{2},2)=\omega ^{\omega }}$そして${\displaystyle f(2\cdot 3^{2}+2\cdot 3+2,3)=\omega ^{2}\cdot 2+\omega \cdot 2+2}$これは厳密に小さい。 を計算するには、${\displaystyle f(G_{m}(n),n+1)}$まず最初に書く必要がある ${\displaystyle G_{m}(n)}$遺伝的基盤において${\displaystyle n+1}$表記法、例えば次の式${\displaystyle \omega ^{\omega }-1}$は序数ではありません。

したがって、シーケンス${\displaystyle P_{m}}$は厳密に減少します。順序数上の標準的な順序 < は正則であるため、無限の厳密に減少する数列は存在できません。言い換えれば、順序数の厳密に減少する数列はすべて終端します（そして無限にはなり得ません）。しかし${\displaystyle P_{m}(n)}$は直接計算されます${\displaystyle G_{m}(n)}$したがって、シーケンス${\displaystyle G_{m}}$終了する必要もある、つまり到達する必要がある${\displaystyle 0}$。

グッドスタインの定理の証明は比較的簡単ですが、グッドスタインの定理がペアノ算術の定理ではないことを示すカービー・パリスの定理^{[ 1 ]}は技術的で、かなり難しいです。これは、ペアノ算術の可算非標準モデルを利用します。

グッドスタイン関数、${\displaystyle {\mathcal {G}}:\mathbb {N} \to \mathbb {N} }$は次のように定義される。${\displaystyle {\mathcal {G}}(n)}$はnから始まるグッドスタイン数列の長さです。（すべてのグッドスタイン数列は終了するので、これは全関数です。） 極めて高い成長率${\displaystyle {\mathcal {G}}}$関数などのさまざまな標準的な順序インデックス付き関数階層に関連付けることで較正できます。${\displaystyle H_{\alpha }}$ハーディ階層と関数${\displaystyle f_{\alpha }}$急速に拡大するレーブとワイナーの階層構造の中で：

• カービーとパリス（1982）は、

${\displaystyle {\mathcal {G}}}$成長率はほぼ同じで${\displaystyle H_{\epsilon _{0}}}$（これは、${\displaystyle f_{\epsilon _{0}}}$より正確には、${\displaystyle {\mathcal {G}}}$支配する${\displaystyle H_{\alpha }}$すべての${\displaystyle \alpha <\epsilon _{0}}$、 そして${\displaystyle H_{\epsilon _{0}}}$支配する${\displaystyle {\mathcal {G}}\,\!.}$

（任意の２つの関数について）${\displaystyle f,g:\mathbb {N} \to \mathbb {N} }$、${\displaystyle f}$支配的であると言われている${\displaystyle g}$もし${\displaystyle f(n)>g(n)}$十分に大きいすべての${\displaystyle n}$）

• Cichon (1983) は、

${\displaystyle {\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,}$

どこ${\displaystyle R_{2}^{\omega }(n)}$これは、 n を遺伝的 2 進数表記で表し、すべての 2 を ω に置き換えた結果です(グッドスタインの定理の証明で行われたように)。

• カイセド（2007）は、${\displaystyle n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}}$と${\displaystyle m_{1}>m_{2}>\cdots >m_{k},}$それから

${\displaystyle {\mathcal {G}}(n)=f_{R_{2}^{\omega }(m_{1})}(f_{R_{2}^{\omega }(m_{2})}(\cdots (f_{R_{2}^{\omega }(m_{k})}(3))\cdots ))-2}$。

いくつかの例を挙げます。

（アッカーマン関数とグラハムの数の境界については、「急速に成長する階層」の項「 急速に成長する階層における関数」を参照してください。）

グッドスタインの定理を用いると、ペアノ算術では全関数であることが証明できない全関数を構築できる。ある数のグッドスタイン数列はチューリングマシンで効率的に列挙できるため、 nをnのグッドスタイン数列が終了するのに必要なステップ数にマッピングする関数は、特定のチューリングマシンで計算可能である。このマシンは単にnのグッドスタイン数列を列挙し、数列が 0 に達したら数列の長さを返す。すべてのグッドスタイン数列は最終的に終了するため、この関数は全関数である。しかし、ペアノ算術はすべてのグッドスタイン数列が終了することを証明しないため、ペアノ算術はこのチューリングマシンが全関数を計算することを証明しない。

• 非標準算術モデル
• 急速に成長する階層構造
• パリス・ハリントン定理
• 金森・マカルーンの定理
• クルスカルの木の定理
• ロープを燃やすパズル

• Kirby, L.; Paris, J. (1982). "Peano算術のアクセス可能な独立性結果" (PDF) . Bulletin of the London Mathematical Society . 14 (4): 285. CiteSeerX 10.1.1.107.3303 . doi : 10.1112/blms/14.4.285 . 
• マイケル・ラスジェン (2014)。 「グッドスタイン再訪」。arXiv : 1405.4484 [ math.LO ]。
• Goodstein, R. (1944). 「制限された順序数定理について」。Journal of Symbolic Logic . 9 (2): 33–41 . doi : 10.2307/2268019 . JSTOR 2268019. S2CID 235597 .  
• Cichon, E. (1983). 「再帰的理論的手法を用いた最近発見された2つの独立性結果の簡潔な証明」 .アメリカ数学会紀要. 87 (4): 704–706 . doi : 10.2307/2043364 . JSTOR 2043364 . 
• カイセド、A. (2007)。「グッドスタイン関数」(PDF)。レビスタ コロンビアナ デ マテマティカス。41 (2): 381–391。

• ワイスタイン、エリック・W. 「グッドスタイン・シーケンス」。マスワールド。
• グッドスタインの定理がPAの定理ではないことを証明するいくつかの要素（ジャスティン・T・ミラーの学部卒業論文より）
• グッドスタインの定理によるペアノ算術の非標準モデルの分類- ダン・カプランによる論文、フランクリン・アンド・マーシャル大学図書館
• Haskellとラムダ計算におけるグッドスタイン列の定義
• グッドスタイン・シーケンス：無限を経由する迂回路の力- グッドスタイン・シーケンスとヒドラ・ゲームのイラスト付きで分かりやすく解説されています。
• Goodstein Calculator ( 2017年2月4日時点のアーカイブ)