数学的帰納法
数学的帰納法は自然数に関する論法だが、自然数以外の集合に対しても、集合の元を適切に順序づけることで数学的帰納法を適用できることがある。例えば直積集合 N × N 上に辞書式順序
(x, y) > (x′, y′)
:⇔ (x > x′) または (x = x′ かつ y > y′)
を入れることで N × N 上でも数学的帰納法が使える。
これは k {\displaystyle k} の最小性に矛盾するから、背理法により、 P ( n ) {\displaystyle P(n)} が成立しないような自然数 n {\displaystyle n} は存在しない。すなわち、すべての自然数 n {\displaystyle n} に対して P ( n ) {\displaystyle P(n)} が成り立つ。
この議論と前に述べた「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 N {\displaystyle \mathbb {N} } が通常の大小関係 < {\displaystyle <} によって整列されていることによる。 < {\displaystyle <} が N {\displaystyle \mathbb {N} } 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。
自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。
なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は帰納ではなく、純粋に自然数の構造に依存した演繹論理の一種である。2 により次々と命題の正しさが"伝播"されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられた。ジョン・ウォリスによって、彼の著作Arithmetica Infinitorumの中で、この方法にinductionという名前が与えられたとされる。