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

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

 

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

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

 

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

어떤 $n\in N$을 더하는 함수를 ${+}_n:\mathbb{N}\to \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 에 의해 덧셈이 유일하게 존재함이 증명된다.

 

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

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

 

Part 1. $x+(y+z)=(x+y)+z$

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

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

$$(x+y)+S\left(z\right)=S((x+y)+z)=S(x+(y+z))=x+S(y+z)=x+(y+S\left(z\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=(x+1)+1=(1+x)+1=1+(x+1)=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(x+y)=S(y+x)=y+S\left(x\right)$$ $$=y+(x+1)=y+(1+x)=(y+1)+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(x+k)=S(y+k)\Rightarrow x+k=y+k\Rightarrow x=y$$

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

 

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

$1.\mathrm{\forall }n\in \mathbb{N},n\times 1=n$      $2.\mathrm{\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}\to \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 에 의해 곱셈이 유일하게 존재함이 증명된다.

 

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

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

 

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

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

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

$$x\times (y+S\left(k\right))=x\times \{y+(k+1)\}=x\times \{(y+k)+1\}$$ $$=x\times (y+k)+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 (y\times z)=(x\times y)\times z$

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

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

$$x\times (y\times S\left(k\right))=x\times (y\times k+y)=x\times (y\times k)+x\times y$$ $$=(x\times y)\times k+(x\times y)=(x\times y)\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(1\times k)=1\times k+1=1\times k+1\times 1=1\times (k+1)=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 (k+1)=x\times k+x\times 1=k\times x+1\times x=(k+1)\times x=S\left(k\right)\times x$$

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

 

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

만약 $x=1$ 일 때, $y\ne 1$ 이라면, $\mathrm{\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(z\times n)=1$$

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

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

어떤 자연수 $k$에 대해 $k\times z=y\times z\Rightarrow k=y$ 라고 가정하자. $y=1$ 일 때는 위에서 증명하였으므로, $y\ne 1\Rightarrow \mathrm{\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$ 수학적 귀납법에 의해 소거법칙은 참이다.