정수론 | 자연수의 정렬원리와 수학적 귀납법

읽기 전

• 작성자가 공부하고 있는 교재와 해석에 따라 보완될 여지가 있습니다.
• 어디까지나 복습을 위해 정리하는 글이니 오개념이 있을 수 있으며 이를 바로잡기 위한 지적은 매우 감사히 받겠습니다.
• 공부하고 있는 교재에 따라 정리할 지 난이도에 따라 정리할 지 고민 중입니다. ;ㅅ;
• 수학 블로그가 아니기 때문에 다루는 내용의 카테고리가 일치하지 않을 수 있습니다.

자연수의 정렬원리(Well-ordering Principle)

자연수 정렬성의 증명은 현재 다루고 있는 초등해석학 수준에선 어렵기 때문에 공리로써 받아들이려 한다.

자연수 집합 $N$의 부분집합 $S$가(공집합(∅) 제외) 주어지면 그 집합 안에서 항상 최소원소를 찾을 수 있다. 즉, $S \subset N$이고 공집합이 아니면 집합 S는 최소값을 가진다.

$$
\exists \;a\in S \;\ s.t \;\ a\le b,\;\ \forall\ b \in S
$$

아르키메디안 성질 증명

• 임의의 자연수 $a,b$가 있으면 $na \ge b$를 만족하는 자연수 n이 존재한다

위 개념이 아르키메디안 성질이다. 자연수의 정렬성을 활용한 아르키메디안 성질 증명과정은 다음과 같다.

우선 위의 정의가 성립하지 않는다고 가정하자. 어떤 자연수 $a,b$가 존재하여 모든 자연수 $n$에 대해 $na < b$를 만족한다고 할 때 모든 자연수 $n$에 대하여 $0<b-na$이므로 $b-na$는 자연수가 된다. 따라서 자연수 $b-na$를 원소로 갖는 공집합이 아닌 집합 S가 존재하게 된다.
$$
S = {b-na \;\ | \;\ n \in N }
$$
$S \subset N$이므로 자연수의 정렬원리에 따라 집합 $S$에는 최소원소가 존재한다. 그리고 그 최소원소를 $b-ma$라 가정하자. 그런데 집합 $S$의 정의에 따라 $b-(m+1)a \in S$또한 성립하는데 앞서 $b-ma$가 최소원소라고 가정했음에도 $b-(m+1)a < b-ma$인 관계 또한 성립되므로 모순이 된다. 그러므로 집합 $S$는 자연수의 부분집합임에도 최소원소가 존재하지 않음을 의미하고 자연수의 정렬성에 위배된다. 아르키메디안 성질을 부정했을 때 부정할 수 없음이 증명되었음을 확인할 수 있다.

수학적 귀납법

수학적 귀납법은 모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법 중 하나로 그 바탕에는 자연수의 정렬원리가 있다. 수학적 귀납법을 표현하면 아래와 같다.
$$
S \subset N인\;집합\;S가\;다음\;두\;조건을\;만족하면\;S=N이다.\\
1)\; 1 \in S\qquad 2)\;k \in S \implies k+1 \in S
$$
위 전제를 증명하기 위해 1,2번 조건은 충족하지만 결론이 $S \neq N$라고 가정한 뒤 공집합이 아닌 $N-S$를 집합 $T$라고 두자. 자연수의 정렬원리에 따라 집합 $T$는 자연수인 최소원소 $x$를 가져야 하고 1번 조건에 따라 $1<x$와 $0<x-1<x$가 성립한다. 앞에서 $x$가 집합 $T$의 최소원소임을 확인했으므로 자연수 $x-1$은 집합 $S$의 원소여야 한다. 그런데 2번 조건에 따라 $x-1 \in S$일 때 $x \in S$이므로 $x \in T, x \in S$가 됨에 따라 $S \ne N$이라는 가정에 모순되므로 $S=N$이 성립한다.

위의 증명을 응용하면 $S$의 원소인 임의의 자연수 $a$에 대해 2번 조건을 만족하면 적어도 $S$는 $N-\{1,2,\;\dots,\;a-1\}$임을 알 수 있다.

예제

• 모든 자연수 $n$에 대해 $n^5-n$이 5의 배수임을 증명하여라.

  $n^5-n$이 5의 배수가 되는 자연수 $n$의 집합을 $S$라 가정하자.

  1. $n=1$이면 $1^5-1=0$으로 5의 배수다.

  2. $n=k$일 때 성립한다고 가정하여 $(k^5-k) \; mod\ 5 = 0$이라고 하면

     $(k+1)^5-(k+1)=(k^5+5k^4+10k^3+10k^2+5k+1)-(k+1)$

     ​ $= (k^5-k)+5(k^4+2k^3+2k^2+k)$가 되어 5의 배수이다.

  (1), (2)번에 의해 수학적 귀납법으로 증명되었음을 확인할 수 있다.

자연수의 거듭제곱의 합

기호 $\sum$의 정의

$\sum_{k=1}^n a_k=a_1+a_2+\dots+a_n$

기호 $\sum$의 성질

1. $\sum_{k=1}^n(a_k \pm b_k)=\sum_{k=1}^n a_k \pm \sum_{k=1}^n b_k$
2. $\sum_{k=1}^n ca_k = c\sum_{k=1}^n a_k$
3. $\sum_{k=1}^n c = cn$

자연수의 거듭제곱의 합

1. $\sum_{k=1}^n k = 1+2+\dots+n=\dfrac{n(n+1)}{2}$
2. $\sum_{k=1}^n k^2=1^2+2^2+\dots+n^2=\dfrac{n(n+1)(2n+1)}{6}$
3. $\sum_{k=1}^n k^3 = 1^3+2^3+\dots+n^3 = \{\dfrac{n(n+1)}{2}\}^2$

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저
• 위키피디아