言いたいことも言えないこんな4次元じゃ
- 2022年5月14日
- 2022年5月22日
- 対象
- 大学2.0年
- 前提知識
- 集合の基礎
P(n) を n∈N についての命題とします.
ベースケースが1以上の帰納法 n=2 のとき成り立ち,∀n≧2P(n)⟹P(n+1) が成り立てば,任意の n≧2 に対し P(n) は成り立ちます.一応証明しましょう.
命題 b∈N,b>0 とする.以下が成り立つとき,∀n≧bP(n):
P(b), ∀n≧bP(n)⟹P(n+1). S(n) は切片を表すものとします.つまり, S(n)={m∈N∣m<n} です.
証明 M=S(b)∪{n∈N∣P(n)} とおき,M=N を示せばよい.b>0 より 0∈S(b).ゆえに 0∈M.n∈M を任意にとる.n<b−1 のとき,n+1<b だから n+1∈S(b).∴n+1∈M.n=b−1 のとき,(1) より P(b) は成り立ち n+1=b∈M.n>b−1 のとき,n+1>b,i.e.,n≧b だから,(2) より P(n+1) は成り立ち,n+1∈M.ペアノの公理系 (P3) より M=N.
累積帰納法 普通の帰納法は n=0 のとき成り立つことを仮定し,n のとき成り立つとすると n+1 のときも成り立つことを主張し,任意の n∈N で成り立つことを帰結する証明法です.大学以降でしばしば使われる累積帰納法は,n=0 のとき正しいことと,0,1,…,n のとき成り立つことを仮定して n+1 のとき成り立つことを示し,任意の n∈N で成り立つことを帰結する証明法です.n+1 のとき正しいことを示す材料が増えるのでかなり便利です.
例えば,1 より大きい n が1つ以上の素数の積で表せる(つまり,素数 p はそれ自身が素数の積とみなす)ことは,累積帰納法で簡単に示せます.MORE