数学的帰納法
上記の形で自然数について定式化された数学的帰納法は、任意の整列集合に対して次のように一般化することができる。この一般化を超限帰納法 (ちょうげんきのうほう、英: transfinite induction)という。任意濃度の集合は選択公理と同値な整列可能定理により整列順序を持つとすることができるので、選択公理を含む公理系であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。
変数変換によって明らかなように、変数 n が表す範囲は n → n + 1 という操作で閉じていれば {1, 2, ...} である必要はなく、0 を自然数に含めることにしたり、あるいは任意の整数 m に関する {m, m + 1, ...} という範囲でもよいことになる。
次の等式が成り立つという命題を P(n) とし、この命題が任意の自然数 n について成立することを数学的帰納法を用いて証明する。
1 + 2 + ⋯ + n = n ( n + 1 ) 2 . {\displaystyle 1+2+\cdots +n={\frac {n(n+1)}{2}}.}
まず、P(1) は右辺を計算することで、正しいことが確かめられる。
右辺 = (1(1+1))/2 = 1 = 左辺。
次に、任意の自然数 k をとる。P(k) は下記の通りであり、これが成立すると仮定する。
1 + 2 + ⋯ + k = k ( k + 1 ) 2 . {\displaystyle 1+2+\cdots +k={\frac {k(k+1)}{2}}.}
これが成立することを使い、 P(k + 1) の左辺を計算すると、P(k + 1) も成立することが分かる。
1 + 2 + ⋯ + k + ( k + 1 ) = ( 1 + 2 + ⋯ + k ) + ( k + 1 ) = k ( k + 1 ) 2 + ( k + 1 ) = ( k + 1 ) ( k + 2 ) 2 {\displaystyle 1+2+\cdots +k+(k+1)=(1+2+\cdots +k)+(k+1)={\frac {k(k+1)}{2}}+(k+1)={\frac {(k+1)(k+2)}{2}}}
以上から、数学的帰納法により、任意の自然数 n について命題 P(n) が成立する。(証明終)