グッドスタインの定理
グッドスタインの定理は、数理論理学における重要な命題であり、自然数に関する興味深い性質を示しています。この定理は、「全てのグッドスタイン数列は必ず0で終わる」という主張を述べています。この命題の特筆すべき点は、ペアノ算術からは決定不能である（つまり、証明も反証もできない）という事実です。
ペアノ算術に決定不能な命題が存在すること自体は、ゲーデルの不完全性定理によって既に示されていました。しかし、ゲーデルの不完全性定理で用いられる命題は、自己言及のパラドックスを利用した「人工的」なものでした。一方、グッドスタインの定理は、より「自然な」決定不能命題の例として知られています。
さらに興味深いことに、グッドスタインの定理は集合論の公理系、特に無限集合の公理を用いることで証明できるという点です。この事実は、ペアノ算術の限界と、より強力な公理系の必要性を示唆しています。
グッドスタイン数列を理解するためには、まず「nを底とした遺伝的記法」という概念を理解する必要があります。ある自然数をnを底とした遺伝的記法で表すには、まずその数を通常のn進数のように、以下の形式で表現します。
aₖnᵏ + aₖ₋₁nᵏ⁻¹ + ... + a₀
ここで、aᵢ は0からn-1の整数です。次に、各項を独立したnの積で表現します。例えば、aₖnᵏ は nᵏ + nᵏ + ... + nᵏ (aₖ個のnᵏの和)のように書き換えられます。さらに、指数kもnを底とした遺伝的記法で表現します。この操作を、記述中に現れる全ての数字がnか0になるまで再帰的に繰り返します。つまり、指数でない全ての数字はnとなり、全ての指数（とその指数）はnまたは0になります。ここで、n⁰=1であることに注意してください。
例として、35を2を底とした遺伝的記法で表すと、以下のようになります。
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になった時が数列の終わりです。
最初のいくつかのグッドスタイン数列は比較的早く0に到達します。例えば、G(3)は以下のように推移します。
G(3) = 3,
2^2 - 1 = 3,
3^2 - 1 = 8,
2 3^2 + 1 - 1 = 17, ... , 0
一方、多くのグッドスタイン数列は、非常に長い間増大し続けます。例えば、G(4)は次のように始まります。
G(4) = 4,
3^3 + 1 - 1 = 27,
4^4 + 1 - 1 = 256,
...
G(4)の項はしばらく増大を続け、底が3 2402653209となったところで最大値3 2402653210 - 1に達し、その後、3 2402653209項の間同じ値を取り続けます。そして、底が3 2402653211 - 1の時に初めて0になります。しかし、G(4)はグッドスタイン数列が「いかに」急速に増大し得るかの良い例ではありません。G(19)はさらに急速に増大します。
しかし、グッドスタインの定理は、初項mがどのような自然数であっても、グッドスタイン数列は必ず0で終わると主張しています。この事実は直感的には理解しづらいですが、厳密な数学的証明が存在します。
グッドスタインの定理は、ペアノ算術では証明できないものの、集合論の枠組みを利用することで証明可能です。証明の鍵となるのは、グッドスタイン数列と並行する順序数の数列を構成することです。
具体的には、グッドスタイン数列G(m)の各項を、対応する底での遺伝的記法で表し、現れる全ての底nを超限順序数ωで置き換えます。この操作によって、順序数の数列が生成されます。この数列は、元のグッドスタイン数列の各項よりも小さくなることはありません。
グッドスタイン数列における底の変更は、並行数列には影響を与えません。しかし、「1を引く」操作は、並行数列の超限順序数を減少させることに対応します。順序数は整列順序を持つため、無限に減少するような順序数の数列は存在しません。したがって、並行数列は有限個の項の後で必ず0に収束します。グッドスタイン数列も、並行数列によって上から押さえられているため、同じく0で終わらなければなりません。
この証明は比較的容易ですが、グッドスタインの定理がペアノ算術には含まれないという「Kirby-Parisの定理」の証明は、より複雑で高度な数学的な議論を必要とします。
グッドスタインの定理は、全域関数でありながら、それが全域関数である事をペアノ算術では証明できないような計算可能関数の構成に応用できます。任意の数のグッドスタイン数列は、チューリングマシンで計算可能です。したがって、「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.
パリス＝ハーリントンの定理
ペアノ算術に決定不能な命題が存在すること自体は、ゲーデルの不完全性定理によって既に示されていました。しかし、ゲーデルの不完全性定理で用いられる命題は、自己言及のパラドックスを利用した「人工的」なものでした。一方、グッドスタインの定理は、より「自然な」決定不能命題の例として知られています。
さらに興味深いことに、グッドスタインの定理は集合論の公理系、特に無限集合の公理を用いることで証明できるという点です。この事実は、ペアノ算術の限界と、より強力な公理系の必要性を示唆しています。
グッドスタイン数列の定義
グッドスタイン数列を理解するためには、まず「nを底とした遺伝的記法」という概念を理解する必要があります。ある自然数をnを底とした遺伝的記法で表すには、まずその数を通常のn進数のように、以下の形式で表現します。
aₖnᵏ + aₖ₋₁nᵏ⁻¹ + ... + a₀
ここで、aᵢ は0からn-1の整数です。次に、各項を独立したnの積で表現します。例えば、aₖnᵏ は nᵏ + nᵏ + ... + nᵏ (aₖ個のnᵏの和)のように書き換えられます。さらに、指数kもnを底とした遺伝的記法で表現します。この操作を、記述中に現れる全ての数字がnか0になるまで再帰的に繰り返します。つまり、指数でない全ての数字はnとなり、全ての指数（とその指数）はnまたは0になります。ここで、n⁰=1であることに注意してください。
例として、35を2を底とした遺伝的記法で表すと、以下のようになります。
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になった時が数列の終わりです。
グッドスタイン数列の例
最初のいくつかのグッドスタイン数列は比較的早く0に到達します。例えば、G(3)は以下のように推移します。
G(3) = 3,
2^2 - 1 = 3,
3^2 - 1 = 8,
2 3^2 + 1 - 1 = 17, ... , 0
一方、多くのグッドスタイン数列は、非常に長い間増大し続けます。例えば、G(4)は次のように始まります。
G(4) = 4,
3^3 + 1 - 1 = 27,
4^4 + 1 - 1 = 256,
...
G(4)の項はしばらく増大を続け、底が3 2402653209となったところで最大値3 2402653210 - 1に達し、その後、3 2402653209項の間同じ値を取り続けます。そして、底が3 2402653211 - 1の時に初めて0になります。しかし、G(4)はグッドスタイン数列が「いかに」急速に増大し得るかの良い例ではありません。G(19)はさらに急速に増大します。
しかし、グッドスタインの定理は、初項mがどのような自然数であっても、グッドスタイン数列は必ず0で終わると主張しています。この事実は直感的には理解しづらいですが、厳密な数学的証明が存在します。
証明
グッドスタインの定理は、ペアノ算術では証明できないものの、集合論の枠組みを利用することで証明可能です。証明の鍵となるのは、グッドスタイン数列と並行する順序数の数列を構成することです。
具体的には、グッドスタイン数列G(m)の各項を、対応する底での遺伝的記法で表し、現れる全ての底nを超限順序数ωで置き換えます。この操作によって、順序数の数列が生成されます。この数列は、元のグッドスタイン数列の各項よりも小さくなることはありません。
グッドスタイン数列における底の変更は、並行数列には影響を与えません。しかし、「1を引く」操作は、並行数列の超限順序数を減少させることに対応します。順序数は整列順序を持つため、無限に減少するような順序数の数列は存在しません。したがって、並行数列は有限個の項の後で必ず0に収束します。グッドスタイン数列も、並行数列によって上から押さえられているため、同じく0で終わらなければなりません。
この証明は比較的容易ですが、グッドスタインの定理がペアノ算術には含まれないという「Kirby-Parisの定理」の証明は、より複雑で高度な数学的な議論を必要とします。
計算可能関数への応用
グッドスタインの定理は、全域関数でありながら、それが全域関数である事をペアノ算術では証明できないような計算可能関数の構成に応用できます。任意の数のグッドスタイン数列は、チューリングマシンで計算可能です。したがって、「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.
関連項目
パリス＝ハーリントンの定理
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。