|| 基礎的な公理を証明に応用
「 n 番目の存在」を保証する証明方法
スポンサーリンク
習った数学的帰納法
復習しておくと
\begin{array}{ccc} a_0 &&\mathrm{or}&& a_1 \end{array}
まず「初期値」を定めて
\begin{array}{ccc} a_{n} &&\to&& a_{n+1}=f(a_n) \end{array}
「 n 番目を仮定」してから「 n+1 番目を求める」
これが「数学的帰納法の手順」です。
なんかよく分かりませんが
\begin{array}{lcl} a_1 &=&1 \\ \\ a_2&=&1+1 \\ \\ a_n &=& n \\ \\ a_{n+1} &=& n+1 \end{array}
この手順に問題が無ければ
「 a_n の形は正しい」ということが保証されます。
ペアノの公理
これを保証するのは
「ペアノの公理」と呼ばれるもので
（この公理は自然数の存在などを保証する）
\begin{array}{ccc} 0 &\in& N \end{array}
「数学的帰納法」は
\begin{array}{ccc} \forall P & \Bigl( & \Bigl( P(0) ∧ \Bigl( \forall n \,\, P(n)⇒P(\mathrm{Suc}(n)) \Bigr) \Bigr) &⇒& \forall n \,\, P(n) & \Bigr) \end{array}
この「公理」の一部により保証されています。
（つまり正しくなる理由は公理）
ちなみに「自然数の存在」は
\begin{array}{lcl} P(0)&=& 0 \\ \\ P(n) &=& n \\ \\ \mathrm{Suc}(n)&=&n+1 \end{array}
このように定める場合で保証されるものになります。
（この感覚を一般化した主張がペアノの公理）
ドメインが生成される順番
ややこしいですが
\begin{array}{ccc} \forall P & \Bigl( & \Bigl( P(0) ∧ \Bigl( \forall n \,\, P(n)⇒P(\mathrm{Suc}(n)) \Bigr) \Bigr) &⇒& \forall n \,\, P(n) & \Bigr) \end{array}
↑ の n は正確には n\in N で
\begin{array}{ccc} \forall n\in N \,\, P(n) \end{array}
この自然数 N は
「ペアノの公理」によって保証されています。
（これもペアノの公理の一部です）
ということは
\begin{array}{ccc} n&\in &N \end{array}
これ自体はこの段階で明確には定義されておらず
N の中身 n はまだきちんと定められていません。
（どの順番で N と n が定まるか不明）
自然数 N の生成手順
形式的には
「全体が同時に決まる」ということになっていますが
\begin{array}{ccc} ？ &\in& N \end{array}
N の中身がどのような順番で決まっていくか
これには正確な順番があります。
というのも
\begin{array}{ccc} 0 \,\, \mathrm{or} \,\, 1 &\in& N \end{array}
まず「初期値」が N に含まれるのは確実です。
（この時点で n は 0,1 しかとれない）
全てはここから始まり
\begin{array}{ccc} \forall n \in N & n\in N ⇒ \mathrm{Suc}(n) \in N \end{array}
この公理により
（この N は現時点では初期値しか持たない）
\begin{array}{ccc} \mathrm{Suc}(0) &\in& N \end{array}
「初期値の後者」が N に含まれることになります。
（これにより N に２つ目の要素が入る）
\begin{array}{ccc} \mathrm{Suc}(0) \in N &⇒& \mathrm{Suc}(\mathrm{Suc}(0)) \in N \end{array}
ここから「後者の後者」が含まれることも決定され
n の中身が無限に生成されていくので
つまり
\begin{array}{rcc} 0 &\in& N \\ \\ \mathrm{Suc}(0) &\in& N \\ \\ \mathrm{Suc}(\mathrm{Suc}(0)) &\in& N \\ \\ &\vdots \end{array}
これらはこのような順番で N に入っているため
（初期値の公理と後者の公理のみ）
この手順を経ていない場合
\begin{array}{ccc} n&\in&N \end{array}
いきなり n に触れることはできません。
\begin{array}{ccc} n&=&\mathrm{Suc}(\mathrm{Suc}(\mathrm{Suc}(0))) \end{array}
n を扱いたい場合には
まず N の中身を明確に定める必要があります。
（生成されてない段階では n が何を指すか不明）
自然数による数学的帰納法
我々が用いる「数学的帰納法」のほとんどは
\begin{array}{ccc} \mathrm{Suc}(n)&=& n+1 \end{array}
「後者関数 \mathrm{Suc} 」がこれの場合なので
実際に使っている数学的帰納法の根拠は
\begin{array}{ccc} P(0)∧\Bigl( \forall n \,\,P(n)⇒P(n+1) \Bigr) &&⇒&& \forall n \,\, P(n) \\ \\ P(1)∧\Bigl( \forall n \,\,P(n)⇒P(n+1) \Bigr) &&⇒&& \forall n \,\, P(n) \end{array}
このような命題になります。
（ペアノの公理の具体的な形の一つ）
ちなみに「証明したいこと」は
\begin{array}{ccc} \forall n & P(n) \end{array}
この「命題 P 」です。
（ n は自然数である みたいなのが入る）
数学的帰納法が正しくなる感覚
これは「 N の生成手順」の時の
\begin{array}{ccc} P(0)∧\Bigl( \forall n \,\,P(n)⇒P(n+1) \Bigr) \end{array}
「初期値」と「後者」さえあれば
「他の要素を全て生成できる」という
\begin{array}{l} P(0) \\ \\ P(0+1) \\ \\ P(0+1+1) \end{array}
この感覚から来ていて
（これにより n 番目もそうなるという予想が得られる）
P(0) から P(n) とするプロセスについては
\begin{array}{lcl} P(0) &\to& P(0+1) \\ \\ P(n) &\to& P(n+1) \end{array}
「初期値」を n と置き換える感覚から来ています。
（初期値が n の代表例であることから）