グッドスタインの定理

グッドスタイン（Reuben Louis Goodstein）が考察した（1944年）、数理論理学における自然数に関する命題であり、「全てのグッドスタイン数列は必ず 0 で終わる」という主張。
ペアノの公理系では証明できない。

始めに、自然数のカントール型 n-進表示とは、以下のような表示をいう。
x ＝ a(0)n^k(0) ＋ a(1)n^k(1) ＋ … ＋ a(p)n^k(p)
但し、0 ＜ a(0) , … , a(p) ＜ n 、k(0) ＞ k(1) ＞ … ＞ k(p) ≧ 0 で、各 k(i) も同じ表示をする。
例えば、10^8 を 3 進表現すると、
100000000 ＝ 2･3^16 ＋ 2･3^14 ＋ 2･3^13 ＋ 2･3^12 ＋ 3^10 ＋ 3^9 ＋ 3^8 ＋ 3^7 ＋ 2･3^6 ＋ 3^4 ＋ 2･3^3 ＋ 2･3^2 ＋ 3^0
　＝ 2･3^(3^2 + 2･3 + 1) ＋ 2･3^(3^2 + 3 + 2) ＋ 2･3^(3^2 + 3 + 1) ＋ 2･3^(3^2 + 3) ＋ 3^(3^2 + 1) ＋ 3^(3^2) ＋ 3^(2･3 + 2) ＋ 3^(2･3 + 1) ＋ 2･3^(2･3) ＋ 3^(3 + 1) ＋ 2･3^3 ＋ 2･3^2 ＋ 1
となる（n^0 ＝ 1 である点に留意）。

次に、自然数 x の n 進展開を n+1 進展開と見たものから 1 を引いたものを y とする写像を N:(x,n)→(y,n+1) とする。
(x,n) から N を適用して得られる系列 Nk(x,n) の第一成分を x(k) とするとき、(x(0) ＝ x,x(1),x(2),…) を (x,n) から始まるグッドスタイン数列という。
例えば、(28,3) から始まるグッドスタイン数列を取り上げる。
28 ＝ 3^3 + 1 だから、第一成分は、
→ 4^4 ＝ 256
→ 5^5 − 1 ＝ 4･5^4 ＋ 4･5^3 ＋ 4･5^2 ＋ 4･5 ＋ 4 ＝ 3124
→ 4･6^4 ＋ 4･6^3 ＋ 4･6^2 ＋ 4･6 ＋ 3 ＝ 6219
…
→ 4･100^4 ＋ 4･100^3 ＋ 4･100^2 ＋ 59 ＝ 404040059
…
→ 4･1000^4 ＋ 4･1000^3 ＋ 3･1000^2 ＋ 157･1000 ＋ 279 ＝ 4004003157279
…
→ 4･10000^4 ＋ 4･10000^3 ＋ 3･10000^2 ＋ 154･10000 ＋ 239 = 40004000301540239
というように急速に大きくなるように見える。
しかし、グッドスタインの定理はグッドスタイン数列が必ず 0 で終わると主張する。

グッドスタイン数列がどの (x,n) から出発しても有限ステップで第一成分が 0 になることの証明は以下の通り。
(x,n) (x ＞ 0) に対しベース n を順序数 ω に置き換えた順序数 Ord(x,ω) を対応させると Ord(N(x,n)) ＜ Ord(x,n) となり、グッドシュタイン列は順序数の下降列に対応する。
従って有限で終らなければならない。というのも、順序数は整列順序（well-order）なので、無限に減り続けるような順序数の数列は存在しないからである。
ω^ω ＋ 1
＞ ω^ω
＞ 4･ω^4 ＋ 4･ω^3 ＋ 4･ω^2 ＋ 4･ω + 4
＞ 4･ω^4 ＋ 4･ω^3 ＋ 4･ω^2 ＋ 4･ω + 3
…
＞ 4･ω^4 ＋ 4･ω^3 ＋ 4･ω^2 ＋ 59
…
＞ 4･ω^4 ＋ 4･ω^3 ＋ 3･ω^2 ＋ 157･ω ＋ 279
…
＞ 4･ω^4 ＋ 4･ω^3 ＋ 3･ω^2 ＋ 154･ω ＋ 239

グッドスタイン数列の十進法表示は、最初のいくつかを除くと、一旦は、宇宙を埋めつくすほど巨大になる。これが、いつか減少を始めやがて 0 に達するという主張は自明ではない。

グッドスタイン数列の有限性はペアノの公理系では証明できないことを示した証明の概要は以下の通り。
グッドスタイン数列が 0 に達することは、順序数 ε(0) までの超限帰納法と同値である。
この超限帰納法によりカット除去定理が証明されペアノの公理系の無矛盾性が証明できるので、もしもペアノの公理系によりグッドスタイン数列の有限性が証明できるならば、ペアノの公理系の無矛盾性がペアノの公理系により証明できることになり、ゲーデルの第二不完全性定理と矛盾する。

ttp://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%83%E3%83%89%E3%82%B9%E3%82%BF%E3%82%A4%E3%83%B3%E3%81%AE%E5%AE%9A%E7%90%86
ttp://en.wikipedia.org/wiki/Goodstein's_theorem
ttp://ac-net.org/tjst/archives/05710-tjst-kyouritsu.pdf
ttp://mathworld.wolfram.com/GoodsteinSequence.html
ttp://mathworld.wolfram.com/GoodsteinsTheorem.html

参照（語彙）：
整列順序
ttp://ja.wikipedia.org/wiki/%E6%95%B4%E5%88%97%E9%9B%86%E5%90%88
ttp://en.wikipedia.org/wiki/Well-order
ttp://100.yahoo.co.jp/detail/%E9%A0%86%E5%BA%8F%E6%95%B0/
ゲーデルの不完全性定理
ttp://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%87%E3%83%AB%E3%81%AE%E4%B8%8D%E5%AE%8C%E5%85%A8%E6%80%A7%E5%AE%9A%E7%90%86
ttp://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems
ttp://mathworld.wolfram.com/GoedelsIncompletenessTheorem.html
ttp://100.yahoo.co.jp/detail/%E3%82%B2%E3%83%BC%E3%83%87%E3%83%AB%E3%81%AE%E4%B8%8D%E5%AE%8C%E5%85%A8%E6%80%A7%E5%AE%9A%E7%90%86/

参照（過去の日記）：
コラッツの予想
ttp://mixi.jp/view_diary.pl?id=647453433&owner_id=14882521
仮説
ttp://mixi.jp/view_diary.pl?id=762009812&owner_id=14882521

参照（未来の日記）：ペアノの公理
ttp://mixi.jp/view_diary.pl?id=1920541881&owner_id=14882521