수학적 귀납법 (Mathematical Induction) 은 다음과 같습니다.
$\mathbb{N}$의 부분집합 $S$가 $0 \in S$이고, 임의의 $n \in S$에 대하여 $n^{+} \in S$이면 ($n + 1 \in S$이면) $\mathbb{N} \subset S$이다.$\mathbb{N}$은 자연수 집합 표기 입니다.
(즉, $S = \mathbb{N}$)
$P(0)$이 참이고, 임의의 $n \in \mathbb{N}$에 대하여 $P(n)$이 참일 때 $P(n + 1)$도 참이라면, 모든 $n \in \mathbb{N}$에 대하여 $P(n)$이 참이다.명제 $P(n)$이 $0$부터 $k - 1$까지는 성립하지 않고 $k$ 이상에서만 성립하더라도 $Q(n) = P(n + k)$로 평행이동 시키면 $Q(n)$이 성립하는게 자연수 집합 전체임을 알 수 있습니다.
$Q(0) = P(k)$이 참이고, 임의의 $n \in \mathbb{N}$에 대하여 $Q(n) = P(n + k)$이 참일 때 $Q(n^{+}) = P(n^{+} + k)$도 참이라면, 모든 $n \in \mathbb{N}$에 대하여 $Q(n)$이 참이다.
예시 1. $0$이 아닌 모든 자연수 $n$에 대하여, $n = m^{+}$인 자연수 $m$이 존재한다.
$n = 1$인 경우에는 $1 := 0^{+}$라는 정의에 따라 $n = 0^{+}$이므로, $n = m^{+}$인 자연수 $m$이 존재한다.
$n = m^{+}$인 자연수 $m$이 있다고 가정하면, $n^{+} = {m_{1}}^{+}$인 자연수 ${m_{1}}$가 있음을 보이면 충분한데, $n = m^{+}$에서 $n^{+} = {m^{+}}^{+}$이므로, $n^{+} = {m_{1}}^{+}$인 자연수 ${m_{1}} = {m}^{+}$이 존재한다.
귀납법에 의해 $0$이 아닌 모든 자연수 $n$에 대해 $n = m^{+}$인 자연수 $m$이 존재한다.