자연수의 덧셈

II-eugene-II Note

자연수의 덧셈

자연수 집합 $\mathbb{N}$ 은 다음과 같은 페아노 공리계를 만족합니다.

1. $\mathbb{N}$ 은 $0$ 이라는 원소를 갖는다.
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$ 이다. ( 수학적 귀납법 )

$n^{+}$ 만 정의했을 뿐, 덧셈과 곱셈은 정의하지 않았음을 알 수 있습니다.
먼저 덧셈부터 정의해줍니다.

$n$ ,

$m$ 은 자연수 이고,

$A := B$ 는

$A$ 를

$B$ 라 정의한다는 뜻입니다.

자연수의 덧셈
1. $0 + m := m$
2. $n^{+} + m := (n + m)^{+}$

덧셈이 재귀적으로 잘 정의되었습니다. (사실 Recursion Theorem을 증명해야 합니다.) 자연수 집합에서 엄밀하게 덧셈을 정의하면 이와 같이 됩니다.
우선 덧셈한 결과물이 자연수 집합안에 존재하는지 (자연수 집합에서 덧셈이 닫혀있는지) 증명할 수 있습니다.

자연수 덧셈 연산의 닫힘
$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$

보조정리 1 증명

수학적 귀납법 기반 증명
덧셈의 정의에서 $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)^{+}$

보조정리 2 증명

수학적 귀납법 기반 증명
$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 := 0^{+}$ 라 하면 다음과 같은 정리를 얻을 수 있습니다.

따름정리 1.
모든 자연수 $n$ 에 대하여 $n + 1 = n^{+}$

따름정리 1 증명

$1 := 0^{+}$ , 보조정리 2에서 $n + 0^{+} = (n + 0)^{+}$ 이고, 보조정리 1에서 $n + 0 = n$ 이므로 $(n + 0)^{+} = n^{+}$ 이다. 따라서 $n + 1 = n^{+}$ 이다.

$2 := 1^{+}$ 라 하면 그 유명한 $1 + 1 = 2$ 를 증명할 수 있게 됩니다.

따름정리 2.
$1 + 1 = 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$ 이다.

이와 똑같이 자연수의 곱셈 또한 정의하고 증명할 수 있습니다.