グッドスタインの定理

グッドスタインの定理（グッドスタインのていり、Goodstein's theorem）は、数理論理学における自然数に関する命題であり、「全てのグッドスタイン数列は必ず0で終わる」という主張。ペアノ算術からは決定不能（証明も反証もできないこと）が知られている。

ペアノ算術に決定不能な命題があること自体は、ゲーデルの不完全性定理により示されている。しかし、不完全性定理の一般的な証明で用いる命題が自己言及のパラドックスを利用した「人工的」なものであるのに対し、グッドスタインの定理は「自然な」決定不能命題の例として知られる。

なお、グッドスタインの定理は集合論の公理系、特に無限集合の公理を用いて証明できる。

グッドスタイン数列の定義

グッドスタイン数列を定義するに当たり、まず「nを底とした遺伝的記法」を定義する。ある自然数をｎを底とした遺伝的記法で表すためには、まずその数を $a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0}$ （ただし、 $a_{i}$ は0とn-1の間の値をとる整数）という形に書き換える。次に、ここに現れる各項を独立したnの積で表す。たとえば $a_{k}n^{k}$ は $n^{k}+n^{k}+\cdots +n^{k}$ という形になる。そのあと今度は全ての指数kをnを底とした遺伝的記法に書き換える。以下、再帰的に繰り返して、記述中に現れる全ての数字がnか0になるまで続ける。つまり指数でない全ての数字はnとなり、全ての指数（とその指数）はnまたは0になる（ $n^{0}=1$ である点に注意）。

例えば、35は2を底として普通に書くと $2^{5}+2+1$ となるが、遺伝的記法で書くと

$2^{2^{2}+1}+2+1$

となる。

数字mのグッドスタイン数列をG(m)と書き、次のように定義する。数列の初項はmとする。次項を得るには、mを2を底とした遺伝的記法で書いてから、現れる「2」を全て3に置換し、結果から1を引く。これがG(m)の第2項である。G(m)の第3項を得るには、一つ前の項（の3を底とした遺伝的記法）の「3」を全て4に置換し、結果からまた1を引く。以下、同様に繰り返し、結果が0になった時が数列の終わりである。

グッドスタイン数列の例

初めのほうのグッドスタイン数列はすぐに終結する。G(3)の様子を見てみよう。

底	遺伝的記法	値	備考
2	2¹ + 1	3	1は2⁰を表す。
3	3¹ + 1 − 1 = 3	3	2を3に置換してから1を引く
4	4¹ − 1 = 1 + 1 + 1	3	3を4に置換してから1を引く。得られる3は底である4よりも小さいので、4¹-1という表現は4⁰ + 4⁰ + 4⁰つまり1 + 1 + 1となる。
5	1 + 1 + 1 − 1 = 1 + 1	2	ここに現れる1は皆5⁰のこと。もはや底を換えても意味はない。この数列は以後0に行き着くことが明らかである。
6	1 + 1 − 1 = 1	1
7	1 − 1 = 0	0

この後の多くのグッドスタイン数列は非常に長い間に渡って増大し続ける。例えば、G(4)は次のように始まる。

遺伝的記法	値
2²	4
2·3² + 2·3 + 2	26
2·4² + 2·4 + 1	41
2·5² + 2·5	60
2·6² + 6 + 5	83
2·7² + 7 + 4	109
...
2·11² + 11	253
2·12² + 11	299
...

G(4)の項はしばらく増大し続けるが、底が3 · 2^402653209となったところで最大値3 · 2^402653210 − 1に達し、そのまま3 · 2^402653209項の間同じ値を取り続けてから、最初で最後の下降を始める。

値が0となるのは底が3 · 2^402653211 − 1の時である。しかしながら、G(4)はグッドスタイン数列が「いかに」急速に増大し得るかについて、良い例とは言えない。G(19)ははるかに急速に増大する。立ち上がりを見てみよう。

遺伝的記法	値
$2^{2^{2}}+2+1$	19
$3^{3^{3}}+3$	7625597484990
$4^{4^{4}}+3$	約 1.3 × 10¹⁵⁴
$5^{5^{5}}+2$	約 1.8 × 10²¹⁸⁴
$6^{6^{6}}+1$	約 2.6 × 10³⁶³⁰⁵
$7^{7^{7}}$	約 3.8 × 10⁶⁹⁵⁹⁷⁴
$7\times 8^{(7\times 8^{7}+7\times 8^{6}+7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+7)}$ $+7\times 8^{(7\times 8^{7}+7\times 8^{6}+7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+6)}+\cdots$ $+7\times 8^{(8+2)}+7\times 8^{(8+1)}$ $+7\times 8^{8}+7\times 8^{7}+7\times 8^{6}$ $+7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+7$	約 6 × 10^15151335
$7\times 9^{(7\times 9^{7}+7\times 9^{6}+7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+7)}$ $+7\times 9^{(7\times 9^{7}+7\times 9^{6}+7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+6)}+\cdots$ $+7\times 9^{(9+2)}+7\times 9^{(9+1)}$ $+7\times 9^{9}+7\times 9^{7}+7\times 9^{6}$ $+7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+6$	約 4.3 × 10^369693099
...

これだけ急速に増大するにもかかわらず、グッドスタインの定理は、初項mが何であろうとグッドスタイン数列は必ず0で終わると主張する。

証明

グッドスタインの定理は（ペアノ算術を逸脱する技法を用いて）以下のようにして証明できる。まず、与えられたグッドスタイン数列G(m)について、これと並行する順序数の数列を作る。この並行する数列の各項は、元のグッドスタイン数列に含まれる各項よりも小さくはないこととする。もしこの並行数列の項が0に収束するならば、グッドスタイン数列も同じく0に収束しなければならない。

並行数列を作るには、グッドスタイン数列の第(n − 1)番目の項のnを底とした遺伝的記法をもとに、そこに現れる全てのnを最初の超限順序数であるωで置換する。順序数は加算、乗算、冪乗についてWell-definedであり、かつ、結果として得られる順序数は元の項より小さくないことが明らかである。

グッドスタイン数列における「底の変更」操作は、並行数列の項には影響しない。つまり、 $4^{4^{4}}+4$ に現れる全ての「4」をωで置換する代わりに、全ての「4」を「5」で置換した後に改めてωで置換しても結果は同じである。ところが「1を引く」操作のほうは、並行数列の超限順序数を減算することに対応する。今の例では、この操作を施すと $\omega ^{\omega ^{\omega }}+\omega$ は $\omega ^{\omega ^{\omega }}+4$ に減算される。順序数は整列順序 (well-order) なので、無限に減り続けるような順序数の数列は存在しない。従って並行数列は有限個の項の後で必ず0で終わらなければならない。グッドスタイン数列も、並行数列によって頭を押えられているので、同じく0で終わることになる。

グッドスタインの定理に関するこの証明はかなり易しいが、一方この定理がペアノ算術には含まれないと述べる「Kirby-Parisの定理」はテクニカルではるかに難しい。その中ではペアノ算術の可算で非標準的なモデルが利用される。そこでKirbyはグッドスタインの定理からゲンツェンの定理(en)が導かれることを示した。つまり、グッドスタインの定理はε₀までの帰納法の代わりとなるのである。

計算可能関数への応用

グッドスタインの定理を応用すると、全域関数であって、かつ全域関数であることがペアノ算術では証明できないような計算可能関数を構成できる。個々の数のグッドスタイン数列はチューリングマシンによって算出できる。したがって、n を「n のグッドスタイン数列が停止するまでに要する項の数」に対応づけるような関数も、何らかのチューリングマシンによって計算できる。この計算機は単に n のグッドスタイン数列を算出し、もし数列が 0 に収束したならば、その数列の長さを返すだけである。全てのグッドスタイン数列は最終的には収束するので、この関数は全域関数である。ところがペアノ算術からは全てのグッドスタイン数列が収束することは証明できないので、ペアノ算術はこのチューリングマシンが計算しているのが全域関数であることを証明できない。

参考文献

Goodstein, R., On the restricted ordinal theorem, Journal of Symbolic Logic, 9 (1944), 33-41.
Kirby, L. and Paris, J., Accessible independence results for Peano arithmetic, Bull. London. Math. Soc., 14 (1982), 285-93.

脚注

外部リンク

“3 Independence of Goodstein's Theorem”. On the Independence of Goodstein's Theorem. (2001-07-23) [2001-04-30]. オリジナルの2006-09-12時点におけるアーカイブ。. https://web.archive.org/web/20060913094157/http://www.u.arizona.edu/~miller/thesis/node11.html
グッドスタインの定理がペアノ算術からは導けないことの証明について
John Tromp. “How fast can you grow?”. Programming Pearls. Centrum Wiskunde & Informatica. 2005年11月30日時点のオリジナルよりアーカイブ。2007年9月24日閲覧。
プログラミング言語RubyとHaskellによるグッドスタイン数列の定義と、大規模な計算例