정수론, 그 세 번째 이야기 | 자연수의 연산

자연수의 연산에서는 덧셈과 곱셈을 정의할 필요가 있다.

 

우선 자연수의 덧셈은 다음과 같이 정의한다.

$1.\; \forall n \in \mathbb{N},\; n + 1 = S(n)$      $2.\; \forall m, n \in \mathbb{N}\; n + S(m) = S(n + m)$

 

위의 정의로 덧셈이 잘 정의됨을 확인하기 위해, Recursion Theorem 을 사용하자.

어떤 $n \in N$을 더하는 함수를 $+_n : \mathbb{N} \rightarrow \mathbb{N}$ 이라고 하면, 이는 $$+_n \left( 1 \right ) = S \left ( n \right )$$ $$+_n \left ( S \left ( m \right ) \right ) = S \left ( +_n \left ( m \right ) \right ) $$ 가 성립하므로, Recursion Theorem 에 의해 덧셈이 유일하게 존재함이 증명된다.

 

그리고 위처럼 정의된 덧셈은 $\forall x, y, z \in \mathbb{N}$ 에 대해 다음과 같은 성질을 만족한다.

$1.\; x + \left (y + z \right ) = \left (x + y \right) + z$ (결합법칙)      $2.\; x + y = y + x$ (교환법칙)      $3.\; x + z = y + z \Rightarrow x + y$ (소거법칙)

 

Part 1. $ x + \left (y + z \right ) = \left (x + y \right ) + z$

$z = 1$ 일 때, $\left ( x + y \right ) + 1 = S \left ( x + y \right ) = x + S \left ( y \right ) = x + \left ( y + 1 \right )$ 이므로 결합법칙이 성립한다.

어떤 자연수 $k$에 대해, $x + \left (y + k \right ) = \left ( x + y \right ) + k$ 라고 가정하자. 이 때, 

$$\left (x + y \right ) + S \left ( z \right ) = S \left ( \left ( x + y \right ) + z \right ) = S \left ( x + \left (y + z \right ) \right ) =x + S \left ( y + z \right ) = x + \left ( y + S \left ( z \right ) \right )$$

$\therefore$ 수학적 귀납법에 의해 결합법칙은 참이다.

 

Part 2. $ x + y = y + x $

먼저 $x + 1 = 1 + x$ 임을 보이자. $x = 1$ 이면 $1 + 1 = 1 + 1$ 이므로 자명하게 참이다.

어떤 자연수 $k$에 대해 $k + 1 = 1 + k$ 라 가정하면, $$S \left ( k \right ) + 1 = \left ( x + 1 \right ) + 1 = \left ( 1 + x \right ) + 1 = 1 + \left (x + 1 \right ) = 1 + S \left ( x \right )$$

$\therefore$ 수학적 귀납법에 의해 $x + 1 = 1 + x$ 은 참이다.

 

이제 $x + y = y + x$ 에서, $y = 1$ 이면 위의 증명에 의해 참이다.

어떤 자연수 $k$에 대해 $x + k = k + x$ 라 가정하면, $$x + S \left ( y \right ) = S \left ( x + y \right ) = S \left ( y + x \right ) = y + S \left ( x \right )$$ $$= y + \left ( x + 1 \right ) = y + \left ( 1 + x \right ) = \left ( y + 1 \right ) + x = S \left ( y \right ) + x$$

$\therefore$ 수학적 귀납법에 의해 교환법칙은 참이다.

 

Part 3. $x + z = y + z \Rightarrow x = y$

$z = 1$ 일 때, $x + 1 = y + 1 \Rightarrow S(x) = S(y) \Rightarrow x = y$ 이므로 참이다.

어떤 자연수 $k$에 대해 $x + k  = y + k \Rightarrow x = y$ 이라고 하자. $$x + S \left ( k \right ) = y + S \left ( k \right ) \Rightarrow S \left ( x + k \right ) = S \left (y + k \right ) \Rightarrow x + k = y + k \Rightarrow x = y$$

$\therefore$ 수학적 귀납법에 의해 소거법칙은 참이다.

 

자연수의 곱셈은 다음과 같이 정의한다.

$1.\;\forall n \in \mathbb{N},\; n \times 1 = n$      $2.\; \forall m, n \in \mathbb{N},\; n \times S \left ( m \right ) = n \times m + n$

 

위의 정의가 곱셈을 잘 정의하는지를 확인할 때도 Recursion Theorem 이 사용된다

어떤 $n \in N$을 곱하는 함수를 $\times_n : \mathbb{N} \rightarrow \mathbb{N}$ 이라고 하면, 이는 $$\times_n \left( 1 \right ) = n$$ $$\times_n \left ( S \left ( m \right ) \right ) = +_n \left ( \times_n \left ( m \right ) \right ) $$ 가 성립하므로, Recursion Theorem 에 의해 곱셈이 유일하게 존재함이 증명된다.

 

그리고 자연수의 곱셈은 $\forall x, y, z \in \mathbb{N}$ 에 대해, 다음과 같은 성질을 가진다.

$1.\; x \times \left ( y + z \right ) = x \times y + x \times z$ (분배법칙)      $2.\; x \times \left ( y \times z \right ) = \left ( x \times y \right ) \times z$ (결합법칙)      $3.\; x \times y = y \times x$ (교환법칙)      $4.\; x \times z = y \times z \Rightarrow x = y$ (소거법칙)

 

Part 1. $x \times \left ( y + z \right ) = x \times y + x \times z$

$z = 1$ 일 때, $x \times \left ( y + 1 \right ) = x \times S \left ( y \right ) = x \times y + x = x \times y + x \times 1$ 이므로 분배법칙이 성립한다.

어떤 자연수 $k$에 대해 $x \times \left ( y + k \right ) = x \times y + x \times k$ 라고 가정하자.

$$x \times \left ( y + S \left ( k \right ) \right ) = x \times \left \{ y + \left ( k + 1 \right ) \right \} = x \times \left \{ \left ( y + k \right ) + 1 \right \}$$ $$= x \times \left ( y + k \right ) + x \times 1 = x \times y + x \times k + x \times 1 = x \times y + x \times S \left ( k \right )$$

$\therefore$ 수학적 귀납법에 의해 분배법칙은 참이다.

 

Part 2. $x \times \left ( y \times z \right ) = \left ( x \times y \right ) \times z$

$z = 1$ 일 때, $x \times \left ( y \times 1 \right ) = x \times y = \left ( x \times y \right ) \times 1 $ 이므로 결합법칙이 성립한다.

어떤 자연수 $k$에 대해 $x \times \left ( y \times k \right ) = \left ( x \times y \right ) \times k$ 라고 가정하자.

$$x \times \left ( y \times S \left ( k \right ) \right ) = x \times \left ( y \times k + y \right ) = x \times \left ( y \times k \right ) + x \times y$$ $$= \left ( x \times y \right ) \times k + \left ( x \times y \right ) = \left ( x \times y \right ) \times S \left ( k \right )$$

$\therefore$ 수학적 귀납법에 의해 결합법칙은 참이다.

 

Part 3. $x \times y = y \times x$

$x \times 1 = 1 \times x$ 임을 먼저 보이자.

$x = 1$ 이면 $1 \times 1 = 1 \times 1$ 이므로 교환법칙이 성립한다.

어떤 자연수 $k$에 대해 $k \times 1 = 1 \times k$ 라고 가정하자. $$S \left ( k \right ) \times 1 = S \left ( k \right ) = S \left ( 1 \times k \right ) = 1 \times k + 1 = 1 \times k + 1 \times 1 = 1 \times \left ( k + 1 \right ) = 1 \times S \left ( k \right )$$

$\therefore$ 수학적 귀납법에 의해 $x \times 1 =  1 \times x$ 는 참이다. 

 

$y = 1$ 이라면 위에서 증명했듯이 $x \times 1 = 1 \times x$ 이므로 교환법칙이 성립한다.

어떤 자연수 $k$에 대해 $x \times k = k \times x$ 라고 가정하자.

$$x \times S \left ( k \right ) = x \times \left ( k + 1 \right ) = x \times k + x \times 1 = k \times x + 1 \times x = \left ( k + 1 \right ) \times x = S \left ( k \right ) \times x$$

$\therefore$ 수학적 귀납법에 의해 교환법칙은 참이다.

 

Part 4, $x \times z = y \times z \Rightarrow x = y$

만약 $x = 1$ 일 때, $y \neq 1$ 이라면, $\exists n \in \mathbb{N}\;s.t.\; S \left ( n \right ) = y$

$$1 \times z = S \left ( n \right ) \times z \Rightarrow z = z \times n + z \Rightarrow z \times n + 1 = 1 \Rightarrow S \left ( z \times n \right ) = 1$$

그런데 $S \left ( k \right ) = 1$ 인 자연수 $k$는 존재하지 않으므로 모순 $\therefore y = 1$

그런데 곱셈 $\times_n : \mathbb{N} \rightarrow \mathbb{N}$ 이므로 모순. 따라서 $x = 1 \Rightarrow y = 1$ 이다.

어떤 자연수 $k$에 대해 $k \times z = y \times z \Rightarrow k = y$ 라고 가정하자. $y = 1$ 일 때는 위에서 증명하였으므로, $y \neq 1 \Rightarrow \exists n \in \mathbb{N}\;s.t.\; S \left ( n \right ) = y$ 일 때를 보자.

$$S \left ( k \right ) \times z = S \left ( n \right ) \times z \Rightarrow k \times z + z = n \times z + z \Rightarrow k \times z = n \times z \Rightarrow k = n \Rightarrow y = S \left ( n \right ) = S \left ( k \right )$$

$\therefore$ 수학적 귀납법에 의해 소거법칙은 참이다.