数学的帰納法

サイエンス

数学的帰納法

すうがくてききのうほう

数学における証明法の一つ。Mathematical induction(Deduction) しばしば帰納法と略されるが、れっきとした演繹法である。帰納的に定義される対象(自然数や論理式、形式的証明など)に関する命題の証明に多用される。数学の証明は有限回で行わなければならない。そのことがこの数学的帰納法ε-δ論法(イプシロンデルタ論法?)などを尊ぶ所以でもある。

(自然数上の)数学的帰納法とは P(1)¥forall n¥in¥mathbb{N}(P(n)¥Rightarrow P(n+1)) の証明を以って ¥forall n¥in¥mathbb{N}P(n) の証明とするという推論規則である。この例では1から始めているが、必ずしも1から始める必要はない。実際 P(n)k から始めて帰納法で証明をすることと、Q(n)¥equiv k¥leq n¥Rightarrow P(n)帰納法で証明することとは同じ事である。

整列集合? P 上の超限帰納法とは、Q(¥min¥{P¥})¥forall x¥in P(¥forall y¥in P(y¥lt x¥Rightarrow Q(y))¥Rightarrow Q(x)) の証明を以って ¥forall x¥in P, Q(x) の証明とするという推論である。P自然数の場合、超限帰納法数学的帰納法の形式に書き換えられる。何となれば R(m)¥equiv ¥forall n¥in¥mathbb{N}(n¥lt m¥Rightarrow Q(n))¥Rightarrow Q(m) とすれば良いからである。

素数は無限にある」という証明

証明:仮にk個の素数 p_1,¥ldots,p_k が存在すると仮定する。ここで p=p_1¥cdots p_k+1 とする。すると定義より pp_1,¥ldots,p_k のどの素数でも割れないから、p はそれ自身素数であるか、p_1,¥ldots,p_k 以外の素因数を持つかのいづれかである。したがってそのどちらかを新たに p_{k+1} としてk+1個の素数を得る。この操作はいくらでも続けられるから、素数は有限個ではありえない。

最初の素数をなんでも良いが例えば p_1=2 とすると、上記の議論により、まず2+1=3なので次の素数p_2=3 とできる。その次は2×3+1=7なので次の素数p_3=7 とできる。次に生成される2*3*7+1=43は2でも3でも7でも割り切れない故に次の素数p_4=43 とおける。次の2*3*7*43+1=1807=13×139で合成数であるが、2でも3でも7でも43でもわりきれないので新たな素数p_5=13(あるいは139)とおける。 このように次々に出てくる数の素因数を素数とおくことによって(しかもそれがそれ以前の素数でないことはあきらかである)次々に素数を指定でき、それは際限がない。

この証明は互いに素な数列を具体的に構成するアルゴリズムを記述しているものであるとも考えられる。

*リスト:リスト::数学関連