정렬 원리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

정렬 원리는 자연수의 속성으로, 자연수 집합의 모든 비어 있지 않은 부분 집합이 최소 원소를 갖는다는 것을 의미한다. 이 원리는 페아노 공리계, 집합론 등에서 공리 또는 증명 가능한 명제로 정의되며, 수학적 귀납법과 동치 관계에 있다. 정렬 원리는 나눗셈 정리, 산술의 기본 정리, 정수 덧셈 등 다양한 수학적 증명에 활용되며, '최소 범죄자' 방법으로도 알려져 있다.

정렬 원리

기본 정보

이름	정렬 원리
영어 이름	Well-ordering principle
설명	모든 공집합이 아닌 양의 정수의 부분집합은 최소 원소를 가진다는 정리

관련 개념	수학적 귀납법

같이 보기	정렬 정리

2. 속성

정렬 원리는 자연수가 어떻게 정의되는지에 따라 공리 또는 증명 가능한 명제가 된다.

* 페아노 산술 등에서는 수학적 귀납법을 통해 정렬 원리를 유도할 수 있다.
* 자연수를 실수의 부분 집합으로 보고 실수가 완전하다고 가정하면, 자연수의 임의의 부분 집합은 항상 최소 원소를 갖는다는 것을 보일 수 있다.
* 집합론에서 자연수는 가장 작은 귀납적 집합으로 정의된다. 이를 통해 모든 자연수의 집합이 정렬되어 있다는 것을 결론내릴 수 있다.

이러한 정렬 원리의 속성은 개릿 비르크호프와 사운더스 맥 레인이 《현대 대수학 개론》에서 언급했듯이, 정수의 대수적 속성에서 추론할 수 없는 비대수적 속성이다.

2.1. 페아노 공리계

페아노 산술 등에서는 수학적 귀납법을 공리로 간주하며, 이를 통해 정렬 원리를 유도할 수 있다. 또한 정렬 원리는 수학적 귀납법과 동치이다.

2.2. 실수의 부분 집합

자연수를 실수의 부분 집합으로 간주하고, 실수가 완전(모든 아래로 유계인 집합은 하한을 가진다)하다는 것을 가정하면, 자연수의 임의의 부분 집합은 언제나 최소 원소를 가진다는 것을 유도할 수 있다.

2.3. 집합론

집합론에서 자연수는 가장 작은 귀납적 집합, 즉 0을 포함하고 다음수 연산에 닫혀 있는 집합으로 정의된다. 이로부터 $\{0,\ldots,n\}$ 이 정렬 성질을 갖는 모든 자연수 $n$ 의 집합은 귀납적이며, 따라서 모든 자연수를 포함해야 함을 보일 수 있다. 이로부터 모든 자연수의 집합 또한 정렬되어 있다는 것을 결론내릴 수 있다.

3. 증명 방법으로서의 응용

정렬 원리는 어떤 명제가 모든 자연수에 대해 성립함을 증명하는 데 사용될 수 있다. 이는 "최소 범죄자" 방법이라고도 불리며, 피에르 드 페르마의 무한 강하법과 유사하다.

4. 응용

정렬 원리는 여러 수학적 증명에 유용하게 사용된다. 예를 들어, 1보다 큰 모든 정수가 소수의 곱으로 소인수분해될 수 있다는 산술의 기본 정리의 일부를 증명할 수 있다. 또한, 모든 양의 정수 $n$ 에 대해 $1 + 2 + 3 + ... + n = \frac{n(n + 1)}{2}$ 이라는 공식을 증명하는 데 사용될 수 있다.

이러한 증명들은 정렬 원리에 따라 어떤 집합이 공집합이 아니라고 가정했을 때 최소 원소가 존재한다는 성질을 이용한다. 이 최소 원소를 이용하여 모순을 이끌어내는 방식으로 증명이 이루어진다.

4.1. 나눗셈 정리

두 정수 $a$ 와 $b$ 에 대하여 $a > 0$ 이면, $b=qa+r$ ( $0\le r < a$ )을 만족하는 유일한 정수 $q$ 와 $r$ (각각 $b$ 를 $a$ 로 나눈 몫과 나머지)이 존재한다.

증명: $b/a$ 보다 큰 양의 정수의 집합 $S$ 의 최소 원소 $t$ 는 정렬 원리에 의해 존재한다. 즉, $t-1 \le b/a < t$ 가 성립한다. $q=t-1$ 이면, $q \le b/a < q+1$ 이므로 $qa \le b < qa + a$ 이다. 이제 $r = b-qa$ 이면, $b=qa+r$ 을 얻고, 앞의 부등식에 의해 $0\le r < a$ 가 성립한다.

4.2. 소인수 분해

1보다 큰 모든 정수는 소수의 곱으로 분해될 수 있다는 산술의 기본 정리의 일부를 정렬 원리를 이용하여 증명할 수 있다.

4.2.1. 소인수분해 증명

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

4.3. 정수 덧셈

정렬 원리는 모든 양의 정수 n에 대해 1 + 2 + 3 + ... + n = n(n + 1)/2 이라는 공식을 증명하는 데 사용될 수 있다.

4.3.1. 정수 덧셈 증명

모든 양의 정수 $n$ 에 대해 $1 + 2 + 3 + ... + n = \frac{n(n + 1)}{2}$ 이라는 정리가 거짓이라고 가정하고 반증법을 사용하자. 그러면 양의 정수의 공집합이 아닌 집합 $C = \{n \in \mathbb N \mid 1 + 2 + 3 + ... + n \neq \frac{n(n + 1)}{2}\}$ 이 존재한다. 정렬 원리에 의해, $C$ 는 $c$ 를 최소 원소로 갖는다. $n = c$ 일 때, 방정식은 거짓이지만, $c$ 보다 작은 모든 양의 정수에 대해서는 참이다. 방정식은 $n = 1$ 에 대해 참이므로, $c > 1$ 이다. $c - 1$ 은 $c$ 보다 작은 양의 정수이므로, 방정식은 $c - 1$ 에 대해 성립한다. 왜냐하면 그것은 $C$ 에 없기 때문이다. 그러므로, 다음이 성립한다.
$\begin{align}1 + 2 + 3 + ... + (c - 1) &= \frac{(c - 1)c}{2} \\1 + 2 + 3 + ... + (c - 1) + c &= \frac{(c - 1)c}{2} + c\\&= \frac{c^2 - c}{2} + \frac{2c}{2}\\&= \frac{c^2 + c}{2}\\&= \frac{c(c + 1)}{2}\end{align}$
이것은 방정식이 $c$ 에 대해 성립함을 보여주며, 이는 모순이다. 따라서, 방정식은 모든 양의 정수에 대해 성립해야 한다.

5. 비대수적 속성

정렬 원리는 최소 상계 공리와 마찬가지로 비대수적 속성이다. 즉, 정수의 대수적 속성(정렬된 정수 영역)에서 추론할 수 없다. 개릿 비르크호프와 사운더스 맥 레인은 《현대 대수학 개론》에서 이와 같이 설명했다.