자연수 집합 $\mathbb{N}$ 은 다음과 같은 페아노 공리계를 만족합니다.
1. $\mathbb{N}$은 $0$이라는 원소를 갖는다.$n^{+}$만 정의했을 뿐, 덧셈과 곱셈은 정의하지 않았음을 알 수 있습니다.
2. $\mathbb{N}$의 임의의 원소 $n$에 대하여 $n$의 (다음 수 / 후계) (Successor) $n^{+}$도 $\mathbb{N}$의 원소이다.
3. $0$이 다음 수인 원소는 $\mathbb{N}$에 존재하지 않는다.
4. $\mathbb{N}$의 두 원소가 같은 다음 수를 가지면, 두 원소는 같다.
5. $\mathbb{N}$의 부분집합 $S$가 $0 \in S$이고, 임의의 $n \in S$에 대하여 $n^{+} \in S$이면 $\mathbb{N} = S$이다. ( 수학적 귀납법 )
자연수의 덧셈덧셈이 재귀적으로 잘 정의되었습니다. (사실 Recursion Theorem을 증명해야 합니다.) 자연수 집합에서 엄밀하게 덧셈을 정의하면 이와 같이 됩니다.
1. $0 + m := m$
2. $n^{+} + m := (n + m)^{+}$
자연수 덧셈 연산의 닫힘
$$ n + m \in \mathbb{N} $$
수학적 귀납법 기반 증명
먼저, $0 + m = m$에서 $m$은 자연수이므로 $0 + m \in \mathbb{N}$이다.
이제 $n + m \in \mathbb{N}$이라 가정하고, $n^{+} + m \in \mathbb{N}$임을 보이면 된다.
덧셈의 정의에서 $n^{+} + m = (n + m)^{+}$이고, 페아노 공리계 2번에 따라 $(n + m) \in \mathbb{N}$이면 $(n + m)^{+} \in \mathbb{N}$이고, 가정에서 $n + m \in \mathbb{N}$이므로 $n^{+} + m \in \mathbb{N}$이다.
따라서 수학적 귀납법에 따라 모든 자연수 $n$에 대해 $n + m \in \mathbb{N}$이다.
보조정리 1.
모든 자연수 $n$에 대하여 $$ n + 0 = n $$
수학적 귀납법 기반 증명
덧셈의 정의에서 $0 + m = m$이므로 $0 + 0 = 0$을 만족한다. ($m \leftarrow 0$)
$n + 0 = n$이라 가정하고 $n^{+} + 0 = n^{+}$임을 보이면 충분하다.
덧셈의 정의에서 $n^{+} + 0 = (n + 0)^{+}$인데, $n + 0 = n$이라 가정했으니 $n^{+} + 0 = (n + 0)^{+} = (n)^{+} = n^{+}$이다.
보조정리 2.
모든 자연수 $n$, $m$에 대하여 $$ n + m^{+} = (n + m)^{+} $$
수학적 귀납법 기반 증명
$m$은 고정하고 $n$에 대한 성질 $n + m^{+} = (n + m)^{+}$으로 볼 수 있다.
$n = 0$이면 좌변은 $0 + m^{+}$에서 덧셈의 정의에 의해 $m^{+}$의 값을 갖는다.
우변은 $(0 + m)^{+}$에서 덧셈의 정의에 의해 $0 + m = m$에서 $m^{+}$의 값을 가지므로, $n = 0$일 때 $n + m^{+} = (n + m)^{+}$이 성립한다.
$n + m^{+} = (n + m)^{+}$이라 가정하고 $n^{+} + m^{+} = (n^{+} + m)^{+}$임을 보이면 충분하다.
먼저, 좌변은 덧셈의 정의에 의해 $(n + m^{+})^{+}$이고, $n + m^{+} = (n + m)^{+}$이라 가정했으니 $(n + m^{+})^{+} = ((n + m)^{+})^{+}$이다.
우변은 덧셈의 정의에 의해 $(n^{+} + m)^{+} = ((n + m)^{+})^{+}$이므로, 좌변과 우변 두 값이 동일하다.
따름정리 1.
모든 자연수 $n$에 대하여 $$ n + 1 = n^{+} $$
$1 := 0^{+}$, 보조정리 2에서 $n + 0^{+} = (n + 0)^{+}$이고, 보조정리 1에서 $n + 0 = n$이므로 $(n + 0)^{+} = n^{+}$이다. 따라서 $n + 1 = n^{+}$이다.
따름정리 2.
$$ 1 + 1 = 2 $$
따름정리 1에서 $n \leftarrow 1$을 대입하면 $1 + 1 = 1^{+}$인데, $2 = 1^{+}$이므로 $1 + 1 = 2$이다.
혹은 덧셈의 정의에서 $1 + 1 = 0^{+} + 1 = (0 + 1)^{+} = 1^{+} = 2$이다.
자연수 덧셈의 교환법칙
$$ n + m = m + n $$
수학적 귀납법 기반 증명
$m$은 고정하고 $n$에 대한 성질 $n + m = m + n$로 볼 수 있다.
$n = 0$일 때 $0 + m$의 값은 덧셈의 정의에서 $m$이고, $m + 0$의 값은 보조정리 1에서 $m$이다.
따라서 $0 + m = m + 0$이다.
$n + m = m + n$이라 가정하고 $n^{+} + m = m + n^{+}$임을 보이면 충분하다.
좌변의 값은 덧셈의 정의에 따라 $(n + m)^{+}$이고, 우변의 값은 보조정리 2에서 $(m + n)^{+}$이다.
$n + m = m + n$이라 가정했으므로 $(n + m)^{+} = (m + n)^{+}$이다.
귀납법에 의해 모든 자연수 $n$에 대해 $n + m = m + n$이 성립한다.
자연수 덧셈의 결합법칙
$$ (a + b) + c = a + (b + c) $$
수학적 귀납법 기반 증명
$a$, $b$는 고정하고 $c$에 대한 성질 $(a + b) + c = a + (b + c)$로 볼 수 있다.
$c = 0$일 때 좌변은 $(a + b) + 0$에서 보조정리 1에 의해 $a + b$이다.
우변은 $a + (b + 0)$에서 보조정리 1에 의해 $b + 0 = b$에서 $a + (b + 0) = a + b$이므로, 좌변과 우변 두 값이 같다.
$(a + b) + c = a + (b + c)$이라 가정하고 $(a + b) + c^{+} = a + (b + c^{+})$임을 보이면 충분하다.
좌변의 값은 보조정리 2에 따라 $((a + b) + c)^{+}$이고, 우변의 값은 보조정리 2에서 $a + (b + c)^{+}$이다. 우변의 값에 다시 한 번 보조정리 2를 적용하면 $(a + (b + c))^{+}$이다.
$(a + b) + c = a + (b + c)$라고 가정했으니 $((a + b) + c)^{+} = (a + (b + c))^{+}$이다. 귀납법에 의해 모든 자연수 $c$에 의해 $(a + b) + c = a + (b + c)$이다.
자연수 덧셈의 소거법칙
$$ a + c = b + c $$ 이면 $$ a = b $$
수학적 귀납법 기반 증명
$a$, $b$는 고정하고 $c$에 대한 성질 $a + c = b + c \Rightarrow a = b$로 볼 수 있다.
$c = 0$일 때 $a + 0 = b + 0$에서 보조정리 1에 의해 각 변은 $a$, $b$이므로 $a = b$이다.
"$a + c = b + c$이면 $a = b$"이라 가정하고 "$a + c^{+} = b + c^{+}$이면 $a = b$"임을 보이면 된다.
$a + c^{+} = b + c^{+}$의 좌변은 보조정리 2에 의해 $(a + c)^{+}$이고 우변은 보조정리 2에 의해 $(b + c)^{+}$이다.
페아노 공리계 4번에 의해 $n^{+} = m^{+}$이면 $n = m$이고 $(a + c)^{+} = (b + c)^{+}$이므로 $a + c = b + c$이고, 가정에 의해 $a = b$이다.
따라서 모든 자연수 $c$에 대해 $a + c = b + c \Rightarrow a = b$ 이다.