整列順序
自然数以外で帰納法が使える例を見ていきましょう. 自然数全体の集合 N = { 0, 1, 2, ... } に, 全ての自然数より大きい新しい元 'ω' を追加します. ω が何者なのか ? という疑問は一旦脇に置いて下さい. 新しい元を追加して, 0 < ω, 1 < ω, 2 < ω, ... という大小関係が成り立っていると勝手に約束するのです.
今約束した大小関係に基いて, 小さいものを左に, 大きいものを右に置いて並べると,
{ 0, 1, 2, 3, 4, ... , ω }
という並びになります.
さてここでこれらについて,
(ii') n 未満の全ての k で P(k) が成立するならば, P(n) も成立する
が成り立っているとしましょう.
すると通常の (自然数全体に対する) 帰納法によって, 全ての自然数 n に対し P(n) が成立します.
そしてさらに (ii': n = ω) によって, P(ω) も成立します. 従って, { 0, 1, 2, ... , ω } 全体で P(n) が成立することが確かめられました.
このように自然数全体の集合に新しい元を追加し, 大小関係を決めたもので, 帰納法の原理 ((ii') ⇒ 全体で成立) が成立するものが色々あります.
{ 0, 1, 2, 3, 4, ... , ω, ω' }
{ 0, 1, 2, 3, 4, ... , ω, ω', ω'' }
{ 0, 1, 2, 3, 4, ... , ω, ω', ω'', ω''' }
これらで (ii') が成立するときに全ての要素での成立が導かれることを確認できます.
ところが並び方 (大小関係の構造) によっては全ての要素での成立が導かれないのです. そのような例も見ましょう.
{ 0, 1, 2, 3, ... , ... '''ω, ''ω, 'ω, ω }
自然数に無限個の新しい元 ω, 'ω, ''ω, ... を追加し, これらは全て自然数よりも大きいと約束します. 新しい元同士の大小は, 「'」 の個数が多いものほど小さい と約束します. 大小順に並べれば上のようになりますね.
この集合の上では帰納法の原理が成立しません. つまり (ii') が満たされているとしても集合全体の上で成立するとはいえないのです.
実際, (ii') によって全ての自然数での成立はいえますが, そこから "右側に伸びる" ことが出来ないのです.
今まだ成立が確認されていない { ... '''ω, ''ω, 'ω, ω } たちの中には "左端", つまり大小関係の意味での "最小" が存在しません. するとどの元も (ii') によっては P(n) の成立を確かめられません.
この例が "帰納法の原理" が成立する条件の本質を表しています. 発見的に見ていくと話が長くなりすぎるので, 結論を述べてしまいます.
集合上に大小関係 (全順序) が定められているとき, 帰納法の原理が成り立つのは次のときであり, そのときに限る.
(W_0) 空集合以外の部分集合が必ず最小元を持つ.
またこれは次のように言い換えても同じである.
(W_1) 大小関係の意味で無限に小さくなっていく列 (a > b > c > ...) が存在しない
この無限に小さくなっていく列のことを "無限降下列" と呼びます.
上で挙げた帰納法の原理が成立しない例では, 例えば { ... '''ω, ''ω, 'ω, ω } が無限降下列となっています.
(W_0) が成立するような大小関係の順序のことを "整列順序" と呼びます. つまり整列順序とは, 帰納法の原理が成立するような大小関係の並び方であるといえます.
(W_0) が成立するときに帰納法の原理が成り立つことの証明は, なかなか美しいので見てみましょう.
(W_0) が成立するとします. またある条件 P(n) について, 帰納法の前提 (ii') が成立しているとします.
ここで P(n) が成立しない n を全て集めた部分集合を考えます. この部分集合を X と名付けます.
"全ての n で P(n) が成立" とは X が空集合となることに他ならないですから, X が空集合だと示すことを目指します.
X は最小元を持ちません. 実際, n ∈ X を任意に取ると, X の定義より P(n) は成立していません. すると "n より小さい全ての k で P(k) が成立" は成り立たないのです. なぜならば, もし仮に "n より小さい全ての k で P(k) が成立" であったとすると帰納法の前提 (ii') により n でも P(n) が成立してしまうからです.
従って, "n より小さいある k で P(k) が成立しない" となります. (全ての k では無いことに注意してください.) この k に対し k ∈ X となります. すると k < n ですから, n が X の最小元でないことがわかります.
ここで n は任意に取っていたので, X の全ての元が最小元でない, つまり X が最小元を持たないことが確かめられました. ところで (W_0) より, 最小元を持たない部分集合は空集合しかありません. 従って X が空集合であること, つまり "全ての n で P(n) が成立" することが確かめられました.
