今回は, ある質問サイトで見かけた,
数学的帰納法がなぜ正しいのか?
という話題です.
実は, 数学的帰納法が「正しい」と言う時,
その意味は, 大きく分けて, 次のふた通りの問題に解釈できます.
その 1
数学的帰納法は, 数学のもっと基礎的な考え方から証明できるか?
その 2
数学的帰納法を含む, (自然数についての) 数学理論は矛盾しないか?
結論を, 順次, なるべく正確に言います.
その 1
数学的帰納法は, ZF の元で証明可能です.
ZF においては, 順序数なる概念が定義されます.
順序数 x で x = y∪{y} なる順序数 y が存在するものを
後継者順序数と呼ぶことにして,
任意の y∈x に対して y が空集合または後継者順序数になるような
後継者順序数 x の全体と {φ} の合併 N を, ZF の下では
自然数全体の集合と定義します.
任意の x∈N と 任意の y ∈ x に対して,
y ∈ N が成り立つことは, 明らかであろう.
x ∈ N に対して,
x+1 = x∪{x}
とおくと,
次の形の超数学的定理が成り立ちます:
定理 (数学的帰納法の原理)
ZF の任意の論理式 A(x) に対し,
次の形の論理式は, ZF から証明可能である:
( A(0) ∧ ( ∀ x∈N )( A(x) ⇒ A(x+1) ) ) ⇒ ( ∀x∈N ) A(x)
証明
A(0) ∧ ( ∀x∈N )( A(x) ⇒ A(x+1) )
を仮定する.
仮に, 結論 ( ∀x∈N ) A(x) を否定すると,
ある自然数 x に対して, ￢A(x) が成り立つ.
そのような自然数 x のうち, 最小のものを n とおく.
もし, n = 0 ならば, 仮定 A(0) に反する.
もし, n ≠ 0 ならば, 自然数の定義より,
n = y + 1 なる自然数 y が存在するので,
n の最小性より, A(y) が成り立つ.
したがって, 帰納法の仮定
A(y) ⇒ A(y + 1)
より,
A(y+1), すなわち A(n) が成り立ち, 矛盾する.
証明終わり.
その 2
G. Genzen によって, 次の超数学的定理が証明されている:
土台となる論理体系は等号述語論理で,
定数記号 0,
1 変数関数記号 S ,
2 変数関数記号 +, ・
を持ち,
以下の公理 A1 ～ A6,
公理シェーマ I からなる形式的体系である:
A1
∀x ( S(x) ≠ 0 )
A2
∀x ∀y ( S(x) = S(y) ⇒ x = y )
A3
∀x ( x+0 = x )
A4
∀x ∀y ( x + S(y) = S(x+y) )
A5
∀x ( x・0 = 0 )
A6
∀x ∀y ( x・S(y) = (x・y) + x )
I
任意の論理式 B(x) に対して, 次の論理式は公理である:
( B(0) ∧ (∀x)( B(x) ⇒ B( S(x) ) ) ) ⇒ (∀x) B(x)
その 2 の超数学的定理の証明は,
非常に難しいので, このエッセーでは述べることはできない.
文献として, 竹内外史, 八杉満理子共著
「証明論入門」
を挙げておく.
文責: Dr. Kazuyoshi Katogi
