順序数と帰納法の対応
二重帰納法の自然な例が中々見つからない...
ω までの帰納法は普通の帰納法, つまり全ての自然数に対する帰納法と同じです. これは ω より小さい順序数全体が全ての自然数と一致するのである意味当然です.
それではもっと大きい順序数ではどんな帰納法になるのでしょうか?
ω + n は普通の帰納法の後, 有限個で個別に示しているだけなので余り面白くありません. 極限順序数だと有意義な帰納法になっています.
ω2 までの帰納法は, 普通の帰納法を 2 回行うことと同じです. 0 ≦ α < ω の部分で ∀n P(n) を示し, ω ≦ α < ω2 の部分で ∀n Q(n) を示し, 最終的に ∀n (P(n) ∧ Q(n)) が示せたことになります. ω3 は帰納法 3 回, ωn は n 回です.
ω^2 までの帰納法はどのようなものかというと, 一般の数学でいう "二重帰納法" というものと対応しています.
まず二重帰納法による証明がどのような流れか説明しましょう.
いま自然数の変数 m, n を持つ条件 P(m, n) があり, ∀m ∀n P(m, n) (全ての自然数 m, n に対し P(m, n) が成立する) を証明したいとしましょう.
このとき二重帰納法による証明は次のような流れで行われます.
Q(m) ⇔ ∀n P(m, n) とします. つまり例えば Q(3) とは, ∀n P(3, n) (全ての自然数 n に対し P(3, n) が成立) を意味します.
証明したい ∀m ∀n P(m, n) は, Q を使えば ∀m Q(m) ですから, これを (m に関して) 帰納法によって証明しましょう.
そのためにはまず Q(0) を証明します. これは ∀n P(0, n) です. これを n に注目して帰納法によって証明します.
次に Q(m) → Q(m + 1) を証明します. これは (∀n P(m, n)) → (∀n P(m + 1, n)) です. これは ∀n P(m, n) が使える状態で ∀n P(m + 1, n) を n について帰納法で証明します.
そうして Q(0) ∧ ∀m (Q(m) → Q(m + 1)) が証明されれば, m について帰納法の原理により ∀m Q(m) が証明できます.
中々ややこしいので整理します.
(i) Q(0) を証明する. (← そのために別の帰納法を行う.)
(ii) Q(m) → Q(m + 1) を証明する (← そのために別の帰納法を行う.)
(i), (ii) 自体が帰納法による証明になっていますが, その内部でさらに別の帰納法を行っています. ですからこのような流れの証明を二重帰納法というのです.
余談ですが (i) の中でやる帰納法と (ii) の中でやる帰納法は本質的にほぼ同じものであることがほとんどです. しかし問題によっては違う内容であることもあります.
この二重帰納法を ω^2 までの帰納法に翻訳することが出来ます. α < ω^2 とします. このような α は α = ωm + n (m, n < ω つまり m, n は自然数) と必ず表され, しかも m, n は α に対して一意に定まります.
R(α) ⇔ P(m, n) (ただし α = ωm + n)
このとき ∀m ∀n P(m, n) と ∀α < ω^2 R(α) が同値になりますから, α について ω^2 までの超限帰納法によって ∀m ∀n P(m, n) が証明できることになります.
問題によって, 二重帰納法で考えた方がわかりやすい場合と, 順序数による帰納法の方がわかりやすい場合があります.
二重帰納法が自然な例は, ペアノ算術の公理から自然数の性質 (和, 積の可換性やら結合法則) を証明していくときに出てくると思いますが, 説明がかなり長くなってしまうので割愛します. 順序数による帰納法がわかりやすい例を, 些か人工的ですが説明します.
A, B 2 人による次のようなゲームを行います. 0 と書かれた箱と 1 と書かれた箱, 2 つの箱があり, 最初それぞれの箱にいくつかの玉が入っています.
A, B は交互に, 次のルールのように玉を操作します.
・A はどちらか好きな箱を選んで, その箱の中の玉を 1 個減らす. ただし玉が 0 個の箱は選べず, 必ず玉が入った箱を選ばなければならない.
・B は, 先に A が 0 の箱から玉を減らした場合, 何もせずに終わる. A が 1 の箱から玉を減らした場合, 0 の箱の玉を有限個増やす. 増やす個数は, 有限個であればどれだけ大きくても良い. (B が任意に決められる)
・A が操作して, その後 B が操作してこれを 1 ターンとする.
上のようにして A, B, A, B, ... と交互に操作していって, 両方の箱に玉が入っていない状態になったらゲームは終了します.
このゲームで次が成立します.
"最初の箱の中の玉の個数に関わらず, A, B の行動に関わらず, 必ず有限回のターンでゲームは終了する (両方の箱から玉が全て除かれる)."
これの証明は ω^2 までの帰納法で証明すると見やすいです. いま 1 の箱の中に m 個, 0 の箱の中に n 個の玉が入っているとします. この状態に対し α := ωm + n という順序数を対応させます.
P(α) ⇔ "対応する順序数が α である箱の状態から必ず有限回のターンでゲームが終了する"
とします. ここで P(0) は箱に玉が入っていない状態なので既に終了しています (0 回の操作で終了する).
α (> 0) に対し, β < α なる全ての β で P(β) が成立しているとしましょう. 対応する順序数が α である箱の状態から, 1 ターン (A → B) 操作をします. その後の対応する順序数を β とします. このとき必ず β < α となっていることを確認してみてください.
この事実が本質的です. いま "β < α なる全ての β で P(β) が成立" を仮定したので, 1 ターン後の箱の状態から必ず有限のターンで終了します. すると最初の状態からも有限のターンで終了することがわかります. つまり P(α) が成立し, 帰納法の原理によって全ての α で P(α) が成立することがいえます.
またこの場合, 無限降下列による説明も出来ます. ゲームの進行と並行して, 対応する順序数の列を考えます. すると上で書いたとおり, 1 ターン後の状態での対応する順序数は必ず減少していますから, 対応する順序数の列は減少列となります
α > β > ...
順序数の無限降下列は存在しないので, この対応する順序数の列は有限の長さで止まります. 止まるというのはゲームのターン進行が出来ないということで, ルールを確認するとこれは両方の箱に玉が入っていない状態になったときに限ることがわかります.
順序数と帰納法の対応の話に戻ります. ω^2 までの帰納法は二重帰納法と対応していて, その説明をしました. ω^3 は三重帰納法と対応しています. ω^n (n < ω) は n 重帰納法です.
ω^ω は "n 重帰納法の証明の n に関して帰納法を行うことで証明できる" という感じの帰納法と対応しています.
