정렬성 원리와 수학적 귀납법

정수론을 시작함에 있어서 가장 중요한 두 가지를 꼽으라면 수학적 귀납법과 정렬성 원리라고 생각합니다. 이 글은 독자가 정수를 알고 있다는 가정 하에 전개됩니다.

 

정렬성 원리(Well Ordering Principle)란, 다음을 의미합니다.

 

어떤 집합 $S$ 가 공집합이 아니고, 모든 원소가 양의 정수일 때, $S$ 는 최소원소를 가진다. 즉, 어떤 $a \in S$ 가 존재하여 모든 $b \in S$ 에 대해 $a \geq b$ 가 성립한다.

 

위 명제는 증명 없이 참으로 받아들이겠습니다.

이를 이용하여, 아르키메데스의 성질(Archimedian Property)이라 불리는 다음 정리를 증명하겠습니다.

 

$\forall a, b \in \mathbb{N}, \exists n \in \mathbb{N} s.t. na \geq b$ 모든 자연수 $a, b$ 에 대해 어떤 자연수 $n$ 이 존재하여 $na \geq b$ 가 성립하도록 할 수 있다.

 

Proof

아르키메데스의 성질이 참이 아니라고 가정하겠습니다. 그렇다면 어떤 자연수 $a, b$ 가 존재하여 모든 자연수 $n$ 에 대해 $na < b$ 가 되도록 할 수 있습니다. 이제 집합 $S$ 를 다음처럼 정의하겠습니다. $$ S = \left\{ b - na : n \in \mathbb{N}\right\}$$ 위 집합이 공집합이 아님은 자명하고, 모든 원소가 양의 정수임 또한 그렇습니다. 따라서 정렬성 원리에 의해 $S$ 의 최소원소가 존재하고, 이를 $\min S = b - ma$ 라 할 수 있습니다. ($m \in \mathbb{N}$)

 

그런데 $m \in \mathbb{N} \Rightarrow (m+1) \in \mathbb{N}$ 임을 이용하면 $$ b - (m+1)a = (b - ma) - a < b - ma$$ 를 얻고, 이는 $\min S = b - ma$ 임에 모순입니다. 귀류법에 의해, 아르키메데스의 성질은 참입니다.

 

이제 수학적 귀납법(Principle of induction) 을 소개하고, 그를 증명하도록 하겠습니다.

 

수학적 귀납법은 다음의 정리를 말합니다.

 

정수만을 원소로 가지는 집합 $S$ 가 다음 성질을 만족한다고 하자. (a) $1 \in S$ (b) $n \in S \Rightarrow n+1 \in S$ 그렇다면 $S$ 는 $1$ 이상의 모든 정수를 원소로 갖는다.

 

Proof

$1$ 이상의 모든 정수를 원소로 갖는 집합은 곧 $\mathbb{N}$ 입니다. 그렇다면 집합 $T$ 를 $$T = \mathbb{N}- S$$ 처럼 정의하고, $T$ 가 공집합이 아니라고 가정하겠습니다. 그렇다면 정렬성 원리에 의해 $T$ 는 최소원소 $\min T = t$ 를 가집니다. 그런데 분명히 $1 \in S$ 이므로 $t > 1$ 입니다. 따라서 $t - 1 \in \mathbb{N}$ 인데, 그렇다면 $$ \min T = t \Rightarrow t - 1 \notin T \Rightarrow t - 1 \in S$$ 입니다. 그런데 성질 (b) 에 의해, $t - 1 \in S \Rightarrow t \in S$ 가 되고, 이는 곧 $T = \mathbb{N}- S$ 가 $t$ 를 원소로 가질 수 없음을 의미합니다. 귀류법에 의해 $T$ 는 공집합임이 보여지고, $\mathbb{N} - S$ 가 공집합이므로 $S$ 는 $1$ 이상의 모든 정수를 원소로 갖습니다.

 

수학적 귀납법은 몇 가지 변형된 꼴로도 존재하며, 그 중 대표적인 변형은 아래와 같습니다.

 

어떤 자연수 $m$ 에 대해 $Q$ 가 아래 조건을 만족하는 정수의 집합이라고 하자. (a) $m \in Q$ (b) $n \in Q \Rightarrow n+1 \in Q$ 그렇다면, $m$ 이상의 모든 정수는 $Q$ 의 원소이다.

 

위 정리의 증명은 변형되지 않은 경우와 같으므로 생략하겠습니다.