자연수의 기본 연산과 순서 관계

요약

이 수업은 페아노 공리의 후자로부터 재귀 정리를 이용하여 자연수의 덧셈, 곱셈, 거듭제곱을 정의한다. 재귀 정리는 재귀적 정의가 유일한 연산을 결정함을 보장한다. 이 수업은 그 정리의 존재 부분을 받아들이고, 유일성 부분을 귀납법으로 증명하며, 연산의 성질인 교환법칙, 결합법칙, 분배법칙, 소거법칙을 이끌어 낸다. 이어서 덧셈을 이용하여 순서 관계를 정의하고 그 성질인 삼분법, 추이성, 단조성을 다루며, 역연산인 뺄셈과 나눗셈을 그것들이 존재하는 조건과 함께 정의한다. 수학적 귀납법의 원리가 모든 증명의 도구이다.

학습 목표

재귀 정리를 진술하고, 이를 이용하여 자연수의 덧셈, 곱셈, 거듭제곱의 재귀적 정의를 쓴다.
연산의 성질을 그 정의로부터 귀납법으로 증명한다.
자연수의 순서를 덧셈으로 정의하고, 그 성질인 삼분법, 추이성, 단조성을 적용한다.
두 자연수의 뺄셈과 나눗셈이 언제 가능한지 알아보고, 자연수의 범위를 벗어나지 않고 이것들로 계산한다.

덧셈

자연수의 연산은 학교에서부터 잘 알려져 있다. 여기서는 그것을 수학적 엄밀함으로 기초 짓는 것이 목적이다. 페아노 공리에 관한 수업에서 자연수는 $1$ 에서 출발하여 후자를 취하는 연산으로 정의되었다. 이 연산은 각 자연수 $n$ 에 그다음 수 $S(n)$ 을 대응시킨다. 덧셈은 후자로부터 두 규칙으로 정의된다. $1$ 을 더하는 것은 후자를 취하는 것이고, $m$ 의 후자를 더하는 것은 $m$ 과의 합의 후자를 취하는 것이다.

n + 1 = S(n), \qquad n + S(m) = S(n + m)

이런 종류의 정의를 재귀적 정의라고 한다. 첫째 규칙은 $1$ 에서의 값을 정하고, 둘째 규칙은 각 경우를 바로 앞의 경우로 환원한다. 그런데 이러한 두 규칙이 실제로 하나의 연산을 정의한다는 것에는 서로 다른 두 주장이 담겨 있다. 모든 자연수에 대하여 그 규칙들을 만족하는 함수가 존재한다는 것(존재)과, 그 규칙들을 만족하는 서로 다른 두 함수는 없다는 것(유일성)이다. 둘을 합친 것이 데데킨트에 의한 재귀 정리이다. 이 강좌는 상자 다음에 설명하듯이 존재 부분을 받아들이고, 유일성 부분을 증명한다. 정리는 곱셈, 거듭제곱, 그리고 이후 수업들의 재귀적 정의에도 쓰일 수 있도록 일반적인 형태로 진술한다.

증명 없이 받아들이는 사실 (재귀 정리). $X$ 가 집합이고 $c$ 가 $X$ 의 원소이며, 각 자연수 $n$ 에 대하여 규칙 $g_n$ 이 주어져 있어서 그 규칙이 $X$ 의 각 원소에 $X$ 의 다른 원소를 대응시킨다고 하자. 그러면 함수 $f$ ( $\mathbb{N}$ 에서 $X$ 로의)로서 $f(1) = c$ 이고 $f(S(n)) = g_n(f(n))$ 가 모든 자연수 $n$ 에 대하여 성립하는 것이 존재하며, 그 함수는 유일하다.

존재는 이 강좌에서 증명 없이 받아들인다. 그 증명에는 함수 $f$ 를 순서쌍의 집합으로 구성하는 것, 즉 $(1, c)$ 를 포함하고 각 순서쌍 $(n, x)$ 와 함께 $(S(n), g_n(x))$ 도 포함하는 가장 작은 순서쌍의 집합으로 구성하고, 이어서 각 자연수에 그 안에서 대응하는 둘째 성분이 유일함을 귀납법으로 확인하는 것이 필요하다. 이 구성은 집합론에 속하며, 뒤따르는 산술에 아무것도 보태지 않는다. 반면에 유일성은 페아노의 다섯째 공리의 직접적인 귀결이다.

보조정리재귀로 정의된 함수의 유일성

두 함수 $f$ 와 $h$ ( $\mathbb{N}$ 에서 $X$ 로의)가 재귀 정리의 두 조건을 만족하면, 두 함수는 같다. 그림은 처음 몇 자연수에서 두 함수의 값을 나타낸다.

증명

$\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}$
두 함수가 일치하는 자연수들의 집합을 $A$ 라 하자. $A$ 가 모든 자연수의 집합임을 보이면 된다.
$f(1) = \resaltar{c} = h(1)$
수 $1$ 은 $A$ 에 속한다. 두 함수의 값이 모두 $c$ 이기 때문이다( $1$ 에서).
$f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))$
$k$ 가 $A$ 에 속하면 $S(k)$ 도 속한다. 두 함수는 같은 값에 같은 규칙 $g_k$ 를 적용하기 때문이다.
$A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))$
페아노의 다섯째 공리에 의해 $A$ 는 모든 자연수의 집합이다. 두 함수는 같다.

첫째 더하는 수 $n$ 을 고정하고 $X = \mathbb{N}$ , $c = S(n)$ , 그리고 각 $m$ 에 대하여 규칙 $g_m$ (각 자연수에 그 후자를 대응시키는 것)를 택하면, 정리로부터 덧셈을 얻는다. 정리가 주는 함수 $f$ 는 각 $m$ 에 수 $n + m$ 을 대응시키는 함수이고, 덧셈의 두 규칙은 정리의 두 조건이다. 마찬가지로 $c = n$ 과 $n$ 을 더하는 규칙으로부터 곱셈을, $c = b$ 와 $b$ 를 곱하는 규칙으로부터 거듭제곱을 얻는다. 결국 $m$ 을 더하는 것은 후자를 취하는 연산을 $m$ 번 적용하는 것과 같다.

예시둘 더하기 둘은 넷

산술에서 가장 잘 알려진 명제는 하나의 정리이며, 덧셈의 두 규칙과 이름 $2 = S(1)$ , $3 = S(2)$ , $4 = S(3)$ 으로 증명된다.

증명

$2 + 2 = 2 + S(1)$
둘째 더하는 수를 $1$ 의 후자로 쓴다.
$2 + S(1) = S(2 + 1)$
둘째 규칙에 의해, 후자를 더하는 것은 합의 후자를 취하는 것이다.
$S(2 + 1) = S(S(2))$
첫째 규칙에 의해, $1$ 을 더하는 것은 후자를 취하는 것이다.
$S(S(2)) = S(3) = 4$
$S(2) = 3$ 이고 $S(3) = 4$ 이므로 결과를 얻는다.

덧셈의 규칙으로부터 그 성질들이 귀납법으로 이끌어진다. 모든 자연수 $a$ , $b$ , $c$ 에 대하여:

교환법칙: $a + b = b + a$ .
결합법칙: $(a + b) + c = a + (b + c)$ . 그러므로 괄호 없이 $a + b + c$ 로 써도 된다.
소거법칙: $a + c = b + c$ 이면 $a = b$ 이다.

교환법칙은 페아노 공리에 관한 수업의 예제 5에서 증명되었고, 결합법칙은 그 수업의 연습 문제 가운데 하나이다. 소거법칙은 이 수업의 예제 1에서 증명한다.