グッドスタインの定理

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

カービーとパリスは、グッドスタイン数列に似た動作をするグラフ理論的なヒドラゲームを紹介した。「ヒドラ」（レルナ神話の多頭ヒドラにちなんで名付けられた）は根の張った木で、1つの動きは木の「頭」（木の枝）の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 を満たす。例えば、2を基数とする表記を実現するには、次のように書く。

${\displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}.}$

したがって、35 を 2 進数で表すと 100011 となり、これは2 ⁵ + 2 + 1を意味します。同様に、100 を3 進数で表すと10201 となります。

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

指数自体はn進表記で書かれていないことに注意してください。たとえば、上記の式には 2 ⁵と 3 ⁴、および 5 > 2、4 > 3 が含まれます。

n 進表記法 ( n進表現を実現するためのステップ)を継承n進表記法に変換するには、まずすべての指数をnの累乗の合計として書き直します(係数の制限は0 ≤ a _i < n )。次に、指数内の任意の指数をn進表記法で書き直します (係数の制限も同じ)。これを繰り返して、式に現れるすべての数値 (基数自体を除く) がn進表記法で書かれるまで続けます。

例えば、35は通常の2進法では2 ⁵ + 2 + 1ですが、遺伝的2進法では次のように表記されます。

${\displaystyle 35=2^{2^{2^{1}}+1}+2^{1}+1,}$

5 = 2 ^{2 1} + 1という事実を利用して。同様に、遺伝的3進法の100は

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

数mのグッドスタイン数列 G ( m )は、自然数の列です。数列G ( m ) の最初の要素はm自身です。2 番目の要素G ( m )(2) を得るには、m を継承 2 進表記で書き、2 をすべて 3 に変更し、結果から 1 を引きます。一般に、mのグッドスタイン数列の( n  + 1)番目の項G ( m )( n  + 1)は次のようになります。

• G ( m )( n )の遺伝的基数n  +1表現を取る。
• 基数n  + 1の各出現をn  + 2に置き換えます。
• 1 を引きます。(次の項は前の項とインデックスn の両方に依存することに注意してください。)
• 結果がゼロになるまで続行し、その時点でシーケンスは終了します。

初期のグッドスタイン配列はすぐに終了します。たとえば、G (3) は6番目のステップで終了します。

その後のグッドスタイン配列は非常に多くのステップで増加します。例えば、G (4) OEIS : A056193は次のように始まります。

G (4)の要素はしばらく増加し続けるが、基底で の最大値に達し、次のステップでもそこに留まり、その後下降し始める。 ${\displaystyle 3\cdot 2^{402\,653\,209}}$${\displaystyle 3\cdot 2^{402\,653\,210}-1}$${\displaystyle 3\cdot 2^{402\,653\,209}}$

しかし、G (4) でさえ、グッドスタイン数列の要素がどれだけ速く増加するかについてはよく分かりません。G ( 19 ) ははるかに急速に増加し、次のように始まります 。

この急速な成長にもかかわらず、グッドスタインの定理によれば、開始値が何であっても、すべてのグッドスタイン シーケンスは最終的に 0 で終了します。

グッドスタインの定理は次のように証明できる（ペアノ算術以外の手法を使用、下記参照）。グッドスタイン数列G ( m ) が与えられたとき、厳密に減少し終了するカントール標準形の順序数の並列数列P ( m ) を構築する。この証明のよくある誤解は、 G ( m ) はP ( m )に支配されているため0 になると考えることである。実際には、 P ( m ) がG ( m )を支配するという事実はまったく関係ない。重要な点は次のとおりである。G ( m )( k ) が存在するのは、 P ( m )( k ) が存在する場合のみであり（並列性）、G ( m ) の 2 つの要素の比較は、 P ( m )の対応するエントリを比較するときに保持される。^[2]このとき、P ( m ) が終了すれば、G ( m ) も終了する。無限後退により、G ( m ) は 0 に達する必要があり、これにより終了が保証される。

uの遺伝的基数k表現を計算し、基数kの各出現を最初の無限順序数ω に置き換える関数を定義します。たとえば、。 ${\displaystyle f=f(u,k)}$${\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}$

数列P(m)の各項P(m)(n)はf ( G ( m ) ( n ) , n + 1 )と定義されます。例えば、G (3)(1)=3=21 ⁺ 20 ^、 P ( 3)(1)= f ( ²¹ +20,2 ⁾ =ω1 + ^ω0 =ω+1^となります。序数の加算、乗算、累乗は明確に定義されています。

我々は次のことを主張します: ${\displaystyle f(G(m)(n),n+1)>f(G(m)(n+1),n+2)}$

グッドスタイン数列の次の要素を生成するために最初の 基底変換操作を適用した後、ただしこの生成における2番目のマイナス1操作の前に、をG ( m )( n )と します。 に注目してください。 ${\displaystyle G'(m)(n)}$${\displaystyle G(m)(n+1)=G'(m)(n)-1}$

すると になります。ここで、マイナス 1 の演算、およびを として適用します。たとえば、および なので、およびとなり、これは厳密には小さくなります。f (G(m)(n),n+1)を計算するには、まずG ( m )( n ) を遺伝基数n +1表記で記述する必要があることに注意してください。たとえば、式は序数ではないためです。 ${\displaystyle f(G(m)(n),n+1)=f(G'(m)(n),n+2)}$${\displaystyle f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)}$${\displaystyle G'(m)(n)=G(m)(n+1)+1}$${\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 \omega ^{\omega }-1}$

したがって、数列P ( m ) は厳密に減少します。順序数の標準的な順序 < は整列しているため、無限の厳密に減少する数列は存在できません。つまり、順序数の厳密に減少する数列はすべて終了します (無限になることはできません)。ただし、P ( m )( n ) はG ( m )( n )から直接計算されます。したがって、数列G ( m ) も終了する必要があり、つまり 0 に到達する必要があります。

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

上記の証明は、グッドスタイン数列の定義を変更して、基数変更操作によって基数bが出現するたびにb + 1ではなくb + 2に置き換える場合でも有効です。より一般的には、b ₁、b ₂、b _{3 、... を}b ₁ ≥ 2となる任意の非減少整数数列とします。この場合、拡張グッドスタイン数列mの( n + 1) 番目の項G ( m )( n + 1)は次のようになります。

• G ( m )( n )の遺伝基底bn表現_を取る。
• 基数b _{nの各出現を}b _{n +1}に置き換えます。
• 1 を引きます。

上記の証明を少し修正すると、この数列が依然として終了することがわかります。たとえば、b _n = 4でb _{n +1} = 9の場合、 となり 、したがって順序数は順序数よりも厳密に大きくなります。${\displaystyle f(3\cdot 4^{4^{4}}+4,4)=3\omega ^{\omega ^{\omega }}+\omega =f(3\cdot 9^{9^{9}}+9,9)}$${\displaystyle f(3\cdot 4^{4^{4}}+4,4)}$${\displaystyle f{\big (}(3\cdot 9^{9^{9}}+9)-1,9{\big )}.}$

拡張版は、実はグッドスタインの原著論文^[3]で検討されたものであり、グッドスタインはそれが制限された順序定理（すなわち、ε ₀以下の超限帰納法は有効であるという主張）と同等であることを証明し、（ までの超限帰納法と同等）の場合の有限主義的な証明を与えた。 ${\displaystyle m\leq b_{1}^{b_{1}^{b_{1}}}}$${\displaystyle \omega ^{\omega ^{\omega }}}$

シーケンスb _nに何の制限もない拡張グッドスタインの定理は、そのような任意の無限シーケンスを PA で表現できないため、ペアノ算術 (PA) では形式化できません。これが、ゲーデルの第二不完全性定理とゲンツェンの ε ₀帰納法を使用した PA の一貫性の証明により、拡張グッドスタインの定理は PA では証明不可能であると 1944 年にグッドスタインが主張できなかった理由のようです。^{[4]しかし、ゲンツェンの証明を調べると、}原始再帰的厳密減少無限シーケンスの順序数が存在しないという事実のみが必要であることがわかり、 b _{n を}原始再帰シーケンスに制限することでグッドスタインは証明不可能な結果を​​証明できたはずです。^[4]さらに、比較的初歩的な手法であるグジェゴルチク階層を用いると、すべての原始的な再帰的厳密減少無限順序数列を「遅く」して、b _n = n + 1となるグッドスタイン列に変換できることが示され、カービーとパリスが証明した結果の別の証明が得られる。^[4]

グッドスタイン関数 は、がnで始まるグッドスタイン数列の長さとなるように定義されます。(すべてのグッドスタイン数列は終了するため、これは全関数です。) の極めて高い増加率は、ハーディ階層の関数や、レーブとワイナーの急増加階層 の関数など、さまざまな標準的な順序インデックス付き関数階層に関連付けることで調整できます。 ${\displaystyle {\mathcal {G}}:\mathbb {N} \to \mathbb {N} }$${\displaystyle {\mathcal {G}}(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}}\,\!.}$

(任意の 2 つの関数 について、十分に大きいすべての に対してが優勢であると言える。)${\displaystyle f,g:\mathbb {N} \to \mathbb {N} }$${\displaystyle f}$${\displaystyle g}$${\displaystyle f(n)>g(n)}$${\displaystyle n}$

• チチョン（1983）は、

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

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

• Caicedo (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). 「ペアノ算術のアクセス可能な独立性結果」(PDF) .ロンドン数学会誌. 14 (4): 285. CiteSeerX  10.1.1.107.3303 . doi :10.1112/blms/14.4.285.
• マイケル・ラスジェン (2014)。 「グッドスタイン再訪」。arXiv : 1405.4484 [math.LO]。
• グッドスタイン、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。
• Caicedo, A. (2007)、「グッドスタインの関数」(PDF)、Revista Columbiana de Matemáticas、41 (2): 381–391。

• ワイスタイン、エリック・W.「グッドスタイン・シーケンス」。マスワールド。
• グッドスタインの定理が PA の定理ではないことの証明のいくつかの要素 (ジャスティン T ミラーの学部論文より)
• グッドスタインの定理によるペアノ算術の非標準モデルの分類 - ダン・カプランの論文、フランクラン・アンド・マーシャル大学図書館
• Haskell とラムダ計算におけるグッドスタイン列の定義
• Javaアプレットとして実装されたHydraゲーム
• Hydra ゲームのバリエーションの JavaScript 実装
• Goodstein シーケンス: 無限を介した迂回の力 - Goodstein シーケンスとヒドラ ゲームのイラストによる優れた解説。
• Goodstein Calculator は 2017-02-04 にWayback Machineでアーカイブされています