정렬 원리 문서 원본 보기

{{위키데이터 속성 추적}}
[[수학]]에서 '''정렬 원리'''(well-ordering principle) 또는 '''정렬 성질'''(well-ordering property)은 [[공집합]]이 아닌 모든 [[양의 정수]] 집합은 [[최대 원소와 최소 원소|최소 원소]]를 갖는다는 정리이다.<ref>{{서적 인용|url=https://archive.org/details/introductiontoan00apos_0/page/13|제목=Introduction to Analytic Number Theory|성=Apostol|이름=Tom|연도=1976|출판사=Springer-Verlag|위치=New York|쪽=[https://archive.org/details/introductiontoan00apos_0/page/13 13]|isbn=0-387-90163-9}}</ref> 이것은 다른 말로 임의의 자연수 집합은 순서에 따른 [[정렬 원순서 집합|정렬]]을 갖는다는 뜻이 된다.

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

* [[페아노 공리계|페아노 산술]] 등에서는 공리로 간주되는 [[수학적 귀납법]]에서 유도할 수 있다. 또한 정렬 원리는 수학적 귀납법과 동치이다.
* 자연수가 실수의 부분 집합이며 [[실수의 완비성|실수가 완전]]하다는 것을 가정하면 자연수의 임의의 부분 집합은 언제나 최소 원소를 갖는다는 것을 유도할 수 있다.<ref>{{서적 인용|제목=Mathematical Analysis: A Straightforward Approach|년도=1982|저자=Binmore K.G.|isbn=9780521288828|판=2|쪽=21}}</ref>
* [[집합론]]에서 자연수는 가장 작은 [[무한 공리|귀납 집합]], 즉 0을 포함하고 [[다음수 연산]]에서 닫힌 집합으로 정의된다. 이로부터 <math>\{0,\ldots,n\}</math>이 정렬 성질을 갖는 모든 자연수 <math>n</math>의 집합은 귀납적이며, 따라서 모든 자연수를 포함해야 함을 보일 수 있다.

== 응용 ==
=== 나눗셈 정리 ===

{{본문|나눗셈 정리}}

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

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

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

''증명:'' <math>C</math>를 소수의 곱으로 분해할 수 없는 1보다 큰 모든 정수의 집합이라고 놓자. 우리는 <math>C</math>가 공집합임을 보이려 한다. 귀류법을 위해 <math>C</math>가 공집합이 아니라고 가정하자. 그러면 정렬 원리에 의해 이 집합의 최소 원소 <math>n</math>이 존재해야 한다. 임의의 소수는 1과 자기 자신으로 분해할 수 있으므로 <math>n</math>은 소수가 아니어야 한다. 따라서 <math>n</math>의 소인수로써 1보다 크고 <math>n</math>보다 작은 정수 <math>a</math>와 <math>b</math>가 존재한다. <math>a, b < n</math>이므로 이들은 <math>C</math>의 원소가 아니다. 그러므로 <math>a</math>와 <math>b</math>는 소수의 곱으로 분해될 수 있으며, <math>a = p_1p_2...p_k</math>와 <math>b = q_1q_2...q_l</math>로 놓을 수 있다. 그러면 <math>n = p_1p_2...p_k \cdot q_1q_2...q_l</math>이므로 소수들을 인수로 갖는 수가 되어 <math>n \in C</math>이라는 가정에 모순된다. 따라서 <math>C</math>가 공집합이 아니라는 가정은 거짓이며, <math>C</math>는 공집합이다. 즉, 1보다 큰 모든 정수는 소수의 곱으로 분해할 수 있다.<ref name="mit">{{서적 인용|url=https://courses.csail.mit.edu/6.042/spring17/mcs.pdf|제목=Mathematics for Computer Science|성=Lehman|이름=Eric|성2=Meyer|이름2=Albert R|성3=Leighton|이름3=F Tom|access-date=2023-06-24|archive-date=2023-06-10|archive-url=https://web.archive.org/web/20230610154641/https://courses.csail.mit.edu/6.042/spring17/mcs.pdf|url-status=}}</ref>

== 각주 ==
{{각주}}

[[분류:기초관계]]
[[분류:수론]]