정수론, 그 네 번째 이야기 | 정렬성의 원리

 

정렬성의 원리(Well Ordering Principle) 란, 아래와 같이 서술되는 공리이다.

 

공집합이 아니고, 음이 아닌 정수들을 원소로 갖는 모든 집합 $S$ 는 최소 원소를 가진다.      다시 말해, $S$ 는 $S$에 속하는 모든 원소 $b$에 대해 $a \leq b$ 를 만족하는 $a$를 포함한다.

 

여기서 정수란, 해석학의 이 글에서 정의한 내용을 따른다. 또한, 위 명제는 증명 없이 참으로 받아들인다.

 

우리는 위의 정리를 이용하여, 아르키메데스 성질(Archimedian Property)이라 불리는 정리를 증명할 수 있다.

아르키메데스의 원리는 아래의 명제를 말한다.

 

$\forall a, b \in \mathbb{N},\;\exists n \in \mathbb{N}\;s.t.\;na\geq b$

 

Proof :

귀류법을 사용하기 위해, 위 정리가 참이 아니라고 가정하자. 그러면, $a, b$에 대해 모든 양의 정수 $n$은 $na < b$를 만족한다. 이 때, 집합 $S$를 다음과 같이 정의하자. $$S = \left \{ b - na : n \in \mathbb{N} \right \}$$ 이는 양의 정수로만 이루어지고, 모든 $n$에 대해 성립하므로 공집합이 아니다.

따라서, $S$는 최소원소가 존재하고, 이를 $\mathrm{min}S = b - ma$ 라고 쓰자. (단, $m \in \mathbb{N})$

그런데 $m \in \mathbb{N} \Rightarrow \left ( m + 1 \right ) a \in \mathbb{N}$ 이므로, $$b - \left (m + 1 \right ) a = \left ( b - ma \right ) - a < b - ma$$

이는 $\mathrm{min}S = b - ma$ 임에 모순이다.

$\therefore$ 아르키메데스의 원리는 참이다.

 

 

또한, 이는 유한 귀납법의 기본 원리(First Principle of Finite Induction) 를 증명하는데 쓸 수도 있다.

이 원리는 다음과 같은 명제이다.

 

$S \subseteq \mathbb{N}$ 인 집합 $S$가 다음 두 가지 성질을 만족한다고 하자.      (i) $1 \in S$      (ii) $k \in S \Rightarrow \left ( k + 1 \right ) \in S$      그러면 $S$는 모든 양의 정수를 가진다.

 

Proof :

$T = \mathbb{N} - S$ 인 집합 $T$를 생각하자. 이 때, $T$가 공집합이 아니라고 가정하자.

그러면 정렬성의 원리에 의해 $\mathrm{min}T = a$ 인 $a$가 존재한다. 그런데 $1 \in S$ 이므로 $a > 1$ 이다.

따라서 $a > a - 1 > 0$ 이고, 다음이 성립한다. $$\mathrm{min}T = a \Rightarrow a - 1 \notin T \Rightarrow a - 1 \in S$$ 그런데 두 번째 가정에 의해, $$ a - 1 \in S \Rightarrow a \in S \Rightarrow a \notin T$$ 따라서 모순이 되고, 처음의 가정은 부정되고 $T = \varnothing$ 이다.

그런데 $\left ( \mathbb{N} - S = \varnothing \right ) \wedge \left ( S \subseteq \mathbb{N} \right ) \Rightarrow S = \mathbb{N}$

$\therefore S$는 모든 양의 정수를 가진다.