정렬 원리

수학에서 정렬 원리(well-ordering principle) 또는 정렬 성질(well-ordering property)은 공집합이 아닌 모든 양의 정수 집합은 최소 원소를 갖는다는 정리이다. 이것은 다른 말로 임의의 자연수 집합은 순서에 따른 정렬을 갖는다는 뜻이 된다.

속성

이 정리는 자연수가 도입되는 방식에 따라서 공리 혹은 증명 가능한 명제가 된다.

• 페아노 산술 등에서는 공리로 간주되는 수학적 귀납법에서 유도할 수 있다. 또한 정렬 원리는 수학적 귀납법과 동치이다.
• 자연수가 실수의 부분 집합이며 실수가 완전하다는 것을 가정하면 자연수의 임의의 부분 집합은 언제나 최소 원소를 갖는다는 것을 유도할 수 있다.
• 집합론에서 자연수는 가장 작은 귀납 집합, 즉 0을 포함하고 다음수 연산에서 닫힌 집합으로 정의된다. 이로부터 $\{0,\ldots ,n\}$이 정렬 성질을 갖는 모든 자연수 $n$의 집합은 귀납적이며, 따라서 모든 자연수를 포함해야 함을 보일 수 있다.

응용

나눗셈 정리

 이 부분의 본문은 나눗셈 정리입니다.

정리: 두 정수 $a$와 $b$에 대하여 $a>0$이라 하자. 그러면 $b=qa+r$을 만족하는 정수 $q$와 $r$이 유일하게 존재하며, 이때 $0\leq r<a$이다. (이 경우 $q$와 $r$을 각각 $b$를 $a$로 나눈 몫과 나머지라고 한다.)

증명: $S$를 $b/a$보다 큰 양의 정수의 집합이라고 하자. 그러면 정렬 원리에 의해 $S$의 최소 원소 $t$가 존재해야 한다. 즉, $t-1\leq b/a<t$가 성립한다. 여기서 $q=t-1$이라 놓으면 $q\leq b/a<q+1$이 되어 $qa\leq b<qa+a$가 성립한다. 이제 $r=b-q$라 놓으면 $b=qa+r$을 얻는다. 그러면 앞서 얻은 부등식에 의해 $0\leq r<a$가 만족된다.

소인수 분해

정리: 1보다 큰 모든 정수는 소수의 곱으로 분해할 수 있다. (이것은 산술의 기본 정리에 포함된다.)

증명: $C$를 소수의 곱으로 분해할 수 없는 1보다 큰 모든 정수의 집합이라고 놓자. 우리는 $C$가 공집합임을 보이려 한다. 귀류법을 위해 $C$가 공집합이 아니라고 가정하자. 그러면 정렬 원리에 의해 이 집합의 최소 원소 $n$이 존재해야 한다. 임의의 소수는 1과 자기 자신으로 분해할 수 있으므로 $n$은 소수가 아니어야 한다. 따라서 $n$의 소인수로써 1보다 크고 $n$보다 작은 정수 $a$와 $b$가 존재한다. $a,b<n$이므로 이들은 $C$의 원소가 아니다. 그러므로 $a$와 $b$는 소수의 곱으로 분해될 수 있으며, $a=p_{1}p_{2}...p_{k}$와 $b=q_{1}q_{2}...q_{l}$로 놓을 수 있다. 그러면 $n=p_{1}p_{2}...p_{k}\cdot q_{1}q_{2}...q_{l}$이므로 소수들을 인수로 갖는 수가 되어 $n\in C$이라는 가정에 모순된다. 따라서 $C$가 공집합이 아니라는 가정은 거짓이며, $C$는 공집합이다. 즉, 1보다 큰 모든 정수는 소수의 곱으로 분해할 수 있다.