16/06/04 05:29:14.71 CtkyGlEO.net
>>330 もどる
URLﾘﾝｸ(ja.wikipedia.org)
数学的帰納法
(抜粋)
集合論における定式化
集合論の枠組みでは、数学的帰納法の原理を次のように表すことができる。
自然数の部分集合 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 ? A であり、P(b) は成り立つことになる。
帰納法の仮定からP(a) も成り立つことになり、これは矛盾である。
逆に、「n以下の任意の自然数kについてk ? A」という形の命題 P(n) を考えることで、数学的帰納法から上の原理を導くことができる。