数学的帰納法
r ∈ M {\displaystyle r\in M} を仮定すると、 M {\displaystyle M} の定義によって P ( r ) {\displaystyle P(r)} が成り立つ。このとき、数学的帰納法の手順より、 P ( r + 1 ) {\displaystyle P(r+1)} も成り立つ。ふたたび、 M {\displaystyle M} の定義によって r + 1 ∈ M {\displaystyle r+1\in M} である。これにより ∀ r . r ∈ M ⇒ r + 1 ∈ M {\displaystyle \forall r.\,r\in M\Rightarrow r+1\in M} が示されたことになる。
(1) および (2) により、ペアノの公理Vによって N ⊆ M {\displaystyle \mathbb {N} \subseteq M} が得られる。部分集合の定義により、これは ∀ n ∈ N . P ( n ) {\displaystyle \forall n\in \mathbb {N} .\,P(n)} であることを意味する。(証明終)
数学的帰納法が成り立つことを数学的帰納法の原理といい、ペアノの公理Vが数学的帰納法の原理そのものを表している。もし、公理Vを用いて、数学的帰納法をあえて証明するならば、以下のように示すことができる。
自然数の集合を N {\displaystyle \mathbb {N} } とし、命題 P ( n ) {\displaystyle P(n)} が成り立つ n {\displaystyle n} の集合を M {\displaystyle M} とする。
M ≡ { n ∈ N ∣ P ( n ) } {\displaystyle M\equiv \{n\in \mathbb {N} \mid P(n)\}}
(1) 数学的帰納法の仮定により、 1 {\displaystyle 1} は M {\displaystyle M} の要素である。
1 ∈ M {\displaystyle 1\in M}
(2) 任意に自然数 r {\displaystyle r} をとる。
例えば n → n + 1 ではなく、n → n + 2 で証明し、開始点が P(2) であれば、全ての正の偶数で証明できる。バリエーションとしては、P(2) から n → n + 2 で正の偶数を証明し、P(1) から n → n + 2 で正の奇数を証明し、よって全ての自然数で成立するという証明方法もある。他にも、P(0) から n → n + 1 と n → n − 1 を両方証明し、全ての整数で成立することを証明するという場合もある。