>>757

つづき

https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95
学的帰納法（すうがくてききのうほう、英: mathematical induction）は証明の手法の一つ。自然数に関する命題 P(n) が全ての自然数 n に対して成り立つ事を証明するために、次のような手続きを行う[注 1]。
1.P(1) が成り立つ事を示す。
2.任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つ事を示す。
3. 1と2の議論から任意の自然数 n について P(n) が成り立つ事を結論づける。
自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。

同値な定式化
集合論の枠組みでは、数学的帰納法の原理を次のように表すことができる[3]。
自然数 N の部分集合 A が空でないとき、A に属する最小の自然数が存在する。
この原理からもともとの形の数学的帰納法が導かれることは，次のようにして示せる。
帰納法の仮定 1., 2. を満たす論理式 P(n) が与えられたとする。自然数の部分集合 A を A = { n ∈ N : ¬ P(n) } によって定める。
この A が空集合であるということを示したい。
そうでないと仮定すると、Aに属する最小の自然数 a を取ることができるが、P(0)は成り立っていることから a は0でない。
従って、ある自然数 b について a = b + 1となっているが、a は A に属する最小の自然数であったということから、b not∈ A であり、P(b) は成り立つことになる。
帰納法の仮定から P(a) も成り立つことになり、これは矛盾である。

逆に、「n 以下の任意の自然数 k について k not∈ A」という形の命題 P(n) を考えることで、数学的帰納法から上の原理を導くことができる。
A を自然数のある集合とし、A に属する最小の自然数が存在しないと仮定する。
もし P(0) が成り立たないと、0 が A に属する最小の自然数となって仮定に反するから、P(0) は成り立つ。
P(n) が成り立つとし、もし P(n + 1) が成り立たないとすると、n + 1 が A の最小の自然数となって仮定に反するから、P(n + 1) も成り立つ。
よって数学的帰納法により A は空となる。
(引用終り)
以上