グッドスタインの定理

Theorem about natural numbers

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

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

遺伝的基盤n表記

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

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

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 進表記は次のようになります。

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

nの指数自体は、上記の 3 ⁴の場合のように、基数n表記法で書かれていないことに注意してください。

n進表記を継承n進表記に変換するには、まずすべての指数をnのべき乗の和として書き直します（係数には0 ≤ a _i < nという制限があります）。次に、指数内の任意の指数を再びn進表記で書き直します（係数には同じ制限があります）。これを繰り返し、式に現れるすべての数値（基数自体を除く）がn進表記で書かれるまで続けます。

例えば、遺伝的3進法の100は

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

グッドスタイン配列

数mのグッドスタイン数列 は、自然数の数列です。数列の最初の要素はと書き、 m自身です。2番目の要素を得るには、 mを遺伝的2進法で書き、すべての2を3に変え、結果から1を引きます。一般に、mのグッドスタイン数列の項は次のように計算されます。 $G_{m}$ $G_{m}(1)$ $G_{m}(2)$ $G_{m}(n+1)$

の遺伝的基数-( n + 1 )表現を取ります。 $G_{m}(n)$
基数 ( n + 1 )の各出現をn + 2に置き換えます。
1 を引きます。

はとインデックスn の両方に依存することに注意してください。 $G_{m}(n+1)$ $G_{m}(n)$

ここで、グッドスタインシーケンス内のさらなる値を計算し、0 に達するとシーケンスが終了されます。

初期グッドスタイン配列はすぐに終了する。例えば、6番目のステップで終了する。 $G_{3}$

ベース	遺伝表記	価値	注記
2	$2^{1}+1$	3	3を遺伝的2進法で書きます
3	$3^{1}+1-1=3^{1}$	3	2 を 3 に変換し、1 を引きます。遺伝的 3 進表記法で書きます。
4	$4^{1}-1=3$	3	3を4に変えて1を引く。これで4はなくなる。
5	$3-1=2$	2	5に変える4はもうありません。1を引いてください
6	$2-1=1$	1	5を6に変えるには、1を引くだけ。
7	$1-1=0$	0	7に変える6はもうありません。1を引くだけです

後半のグッドスタイン配列は、非常に大きなステップ数で増加します。例えば、OEIS :A056193は次のように始まります。 $G_{4}$

ベース	遺伝表記	価値
2	$2^{2^{1}}$	4
3	$3^{3^{1}}-1=2\cdot 3^{2}+2\cdot 3+2$	26
4	$2\cdot 4^{2}+2\cdot 4+1$	41
5	$2\cdot 5^{2}+2\cdot 5$	60
6	$2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5$	83
7	$2\cdot 7^{2}+7+4$	109
$\vdots$	$\vdots$	$\vdots$
11	$2\cdot 11^{2}+11$	253
12	$2\cdot 12^{2}+12-1=2\cdot 12^{2}+11$	299
$\vdots$	$\vdots$	$\vdots$
24	$2\cdot 24^{2}-1=24^{2}+23\cdot 24+23$	1151
$\vdots$	$\vdots$	$\vdots$
$B=3\cdot 2^{402\,653\,209}-1$	$2\cdot B^{1}$	$3\cdot 2^{402\,653\,210}-2$
$B=3\cdot 2^{402\,653\,209}$	$2\cdot B^{1}-1=B^{1}+(B-1)$	$3\cdot 2^{402\,653\,210}-1$
$\vdots$	$\vdots$	$\vdots$

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

しかし、グッドスタイン数列の要素が どのくらいの速さで増加するかについては、ではよくわかりません。ははるかに急速に増加し、次のように始まります。 $G_{4}$ $G_{19}$

遺伝表記	価値
$2^{2^{2}}+2+1$	19
$3^{3^{3}}+3$	7 625 597 484 990
$4^{4^{4}}+3$	$\approx 1.3\times 10^{154}$
$5^{5^{5}}+2$	$\approx 1.8\times 10^{2\,184}$
$6^{6^{6}}+1$	$\approx 2.6\times 10^{36\,305}$
$7^{7^{7}}$	$\approx 3.8\times 10^{695\,974}$
$8^{8^{8}}-1=7\cdot 8^{7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7}$ ${}+7\cdot 8^{7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+6}+\cdots$ ${}+7\cdot 8^{8+2}+7\cdot 8^{8+1}+7\cdot 8^{8}$ ${}+7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}$ ${}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7$	$\approx 6.0\times 10^{15\,151\,335}$
$7\cdot 9^{7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+7}$ ${}+7\cdot 9^{7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6}+\cdots$ ${}+7\cdot 9^{9+2}+7\cdot 9^{9+1}+7\cdot 9^{9}$ ${}+7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}$ ${}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6$	$\approx 5.6\times 10^{35\,942\,384}$
$\vdots$	$\vdots$

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

グッドスタインの定理の証明

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

の遺伝的基数表現を計算し、その基数の各出現を最初の無限順序数に置き換える関数を定義します。例えば、です。 $f=f(u,k)$ $k$ $u$ $k$ $\omega$ $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}(n)$ $P_{m}$ $f(G_{m}(n),n+1)$ $G_{3}(1)=3=2^{1}+2^{0}$ $P_{3}(1)=f(2^{1}+2^{0},2)=\omega ^{1}+\omega ^{0}=\omega +1$

我々は次のことを主張する： $f(G_{m}(n),n+1)>f(G_{m}(n+1),n+2)$

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

するとになります。ここでマイナス1の演算を適用し、とを適用してになります。例えば、とを適用するととなり、はより小さくなります。を計算するには、まずをという式が序数ではないなど、遺伝的基数記法で記述する必要があることに注意してください。 $f(G_{m}(n),n+1)=f(G'_{m}(n),n+2)$ $f(G'_{m}(n),n+2)>f(G_{m}(n+1),n+2)$ $G'_{m}(n)=G_{m}(n+1)+1$ $G_{4}(1)=2^{2}$ $G_{4}(2)=2\cdot 3^{2}+2\cdot 3+2$ $f(2^{2},2)=\omega ^{\omega }$ $f(2\cdot 3^{2}+2\cdot 3+2,3)=\omega ^{2}\cdot 2+\omega \cdot 2+2$ $f(G_{m}(n),n+1)$ $G_{m}(n)$ $n+1$ $\omega ^{\omega }-1$

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

グッドスタインの定理の証明は比較的容易であるが、グッドスタインの定理がペアノ算術の定理ではないことを示すカービー・パリスの定理^[1]は専門的で、かなり難しい。この定理は、ペアノ算術の可算な非標準モデルを用いている。

拡張グッドスタインの定理

上記の証明は、グッドスタイン数列の定義を変更し、基数変換操作によって各基数がではなくに置き換えられた場合でも有効です。より一般的には、、、をとなる任意の非減少整数数列とします。このとき、の拡張グッドスタイン数列のst 項を以下のようにします。 $b$ $b+2$ $b+1$ $b_{1}$ $b_{2}$ $b_{3},\ldots$ $b_{1}\geq 2$ $(n+1)$ $G_{m}(n+1)$ $m$

の遺伝的基本表現を取ります。 $b_{n}$ $G_{m}(n)$
基底の各出現箇所をに置き換えます。 $b_{n}$ $b_{n+1}$
1 を引きます。

上記の証明を少し修正するだけで、この数列が依然として終了することがわかります。例えば、かつならばとなり、したがって順序数はよりも必ず大きくなります。 $b_{n}=4$ $b_{n+1}=9$ $f(3\cdot 4^{4^{4}}+4,4)=3\omega ^{\omega ^{\omega }}+\omega =f(3\cdot 9^{9^{9}}+9,9)$ $f(3\cdot 4^{4^{4}}+4,4)$ $f{\big (}(3\cdot 9^{9^{9}}+9)-1,9{\big )}.$

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

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

開始値の関数としてのシーケンス長

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

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

{\mathcal {G}}

はとほぼ同じ成長率を持ちます（これはの成長率と同じです）。より正確には、はすべてのに対して支配的であり、はを支配する

H_{\epsilon _{0}}

f_{\epsilon _{0}}

{\mathcal {G}}

H_{\alpha }

\alpha <\epsilon _{0}

H_{\epsilon _{0}}

{\mathcal {G}}\,\!.

(任意の 2 つの関数について、十分に大きいすべてのに対してが優勢であると言える。)

f,g:\mathbb {N} \to \mathbb {N}

f

g

f(n)>g(n)

n

チチョン（1983）は、

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

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

R_{2}^{\omega }(n)

Caicedo (2007)は、 $n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}$ $m_{1}>m_{2}>\cdots >m_{k},$

{\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			${\mathcal {G}}(n)$
1	$2^{0}$	$2-1$	$H_{\omega }(1)-1$	$f_{0}(3)-2$	2
2	$2^{1}$	$2^{1}+1-1$	$H_{\omega +1}(1)-1$	$f_{1}(3)-2$	4
3	$2^{1}+2^{0}$	$2^{2}-1$	$H_{\omega ^{\omega }}(1)-1$	$f_{1}(f_{0}(3))-2$	6
4	$2^{2}$	$2^{2}+1-1$	$H_{\omega ^{\omega }+1}(1)-1$	$f_{\omega }(3)-2$	3·2 ^402653211 − 2 ≈ 6.895080803×10 ^121210694
5	$2^{2}+2^{0}$	$2^{2}+2-1$	$H_{\omega ^{\omega }+\omega }(1)-1$	$f_{\omega }(f_{0}(3))-2$	> A (4,4) > 10 ^{10 ^{10 ¹⁹⁷²⁷}}
6	$2^{2}+2^{1}$	$2^{2}+2+1-1$	$H_{\omega ^{\omega }+\omega +1}(1)-1$	$f_{\omega }(f_{1}(3))-2$	> A (6,6)
7	$2^{2}+2^{1}+2^{0}$	$2^{2+1}-1$	$H_{\omega ^{\omega +1}}(1)-1$	$f_{\omega }(f_{1}(f_{0}(3)))-2$	> A (8,8)
8	$2^{2+1}$	$2^{2+1}+1-1$	$H_{\omega ^{\omega +1}+1}(1)-1$	$f_{\omega +1}(3)-2$	> A ³ (3,3) = A ( A (61, 61), A (61, 61))
$\vdots$
12	$2^{2+1}+2^{2}$	$2^{2+1}+2^{2}+1-1$	$H_{\omega ^{\omega +1}+\omega ^{\omega }+1}(1)-1$	$f_{\omega +1}(f_{\omega }(3))-2$	> f _ω+1 (64) >グラハム数
$\vdots$
19	$2^{2^{2}}+2^{1}+2^{0}$	$2^{2^{2}}+2^{2}-1$	$H_{\omega ^{\omega ^{\omega }}+\omega ^{\omega }}(1)-1$	$f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2$

(アッカーマン関数とグラハムの数の境界については、急成長階層 § 急成長階層の関数を参照してください。)

計算可能関数への応用

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

参照

参考文献

^ abc カービー＆パリ 1982年。
^ Rathjen 2014、補題2.2。
^ グッドスタイン 1944年。
^ abc Rathjen 2014.

参考文献

カービー, L.;パリス, 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年2月4日アーカイブ - Wayback Machine

[FOOTNOTEKirbyParis1982-1] カービー＆パリ 1982年。

[FOOTNOTERathjen2014lemma_2.2-2] Rathjen 2014、補題2.2。

[FOOTNOTEGoodstein1944-3] グッドスタイン 1944年。

[FOOTNOTERathjen2014-4] Rathjen 2014.