グッドスタインの定理 (証明)
前回, 任意の自然数を初期値として, グッドスタイン列と呼ばれる数列を定めました. そして, その数列が有限の項で 0 となるか? という問いを挙げました. それに答えるのがグッドスタインの定理 (Goodstein's Theorem) です.
定理 (Goodstein): (in ZFC)
任意の自然数 m に対し, 自然数 n が存在して次が成り立つ. "m を初期値とするグッドスタイン列は第 n 項において初めて 0 となる."
論理式で書けば,
∀m ∃n (g_n = 0 ∧ ∀k<n g_k ≠ 0).
まずは概略ですがこの定理の証明を述べましょう. 初期値 m のグッドスタイン列と並行して, 順序数の列 α_n を考えます.
具体的に初期値 4 の例で見ていきます.
g_1 = 2^2 → α_1 = ω^ω
g_2 = (3^2)×2 + 3×2 + 2 → α_2 = (ω^2)×2 + ω2 + 2
g_3 = (4^2)×2 + 4×2 + 1 → α_3 = (ω^2)×2 + ω2 + 1
g_4 = (5^2)×2 + 5×2 → α_4 = (ω^2)×2 + ω2
g_5 = (6^2)×2 + 6 + 5 → α_5 = (ω^2)×2 + ω + 5
このように, g_n が 遺伝的 (n+1) 進表記で表されているとき, この表記の (n+1) を全て ω で置き換えて得られる順序数を α_n とします. この証明の最も本質的な事実を見ましょう.
事実: 上のように定義された順序数の列 α_n は減少列である.
つまり,
α_1 = ω^ω
> α_2 = (ω^2)×2 + ω2 + 2
> α_3 = (ω^2)×2 + ω2 + 1
> α_4 = (ω^2)×2 + ω2
> α_5 = (ω^2)×2 + ω + 5
> …
となっているのです. このとき "順序数の無限降下列は存在しない" ことから, この α_n が無限列となり得ないこと, すなわち α_n が有限で停止することがわかります.
α_n は g_n から得られるものでしたから, α_n が有限項で終わるというのは g_n 自体が有限項で終わることを意味します. g_n の定義を見直すと, g_n = 0 であるとき, そのときに限り次の項が存在せずに終わりになるので, グッドスタイン列が有限項で g_n = 0 となり終了することが示されました.
前に話した二重帰納法の証明を順序数を使って示す方法と似ていることを確認してください (箱からボールを取り出すゲームの話です). どうしてこんな証明が出てきたのでしょうか? 実のところ, 発想の第一歩はそれほど難しくはありません. グッドスタイン列の各項を, 少し違う書き方をして見てみましょう. 初期値はまた 4 とします.
g_1 = x^x, where x = 2.
g_2 = (x^2)×2 + x2 + 2, where x = 3.
g_3 = (x^2)×2 + x2 + 1, where x = 4.
g_4 = (x^2)×2 + x2, where x = 5.
g_5 = (x^2)×2 + x + 5, where x = 6.
このように 遺伝的 n 進表記の底 n の部分を x で置き換えて書きます. このように書くこと自体も, 地道に g_n を書き表して進めていくと, n が大きくなってきたときに面倒なので自然と出てくる発想です.
そしてこのように表したとき, この x を使った表記が, 数列の項が進むほどに "x の関数として増加の度合いが弱まっている" ことに気付きます.
そうして最終的に 0 になることを証明してやろうと思うと, まだ現段階では少し上手くいきません. それは "x の関数を増加の度合いで順序をつけたとき, 一般には整列していない" という点が障害なのです (例えば f_n := x^(1+1/n) などを考えてみてください). すると減少列があったからといってそれが有限で止まることが導けません.
・どうにか整列していることを確かたい. 整列性 → 順序数.
・上から押さえて 0 になることを示すには, g_n: x = n+1 には n+1 以上の値を代入する必要がある.
・関数としての減少から値としての減少を導くには n に関わらず同じ値を代入するのが自然.
以上の状況を整理すれば, "x に ω を代入する" ことが必然であることが了解されると思います.
