정렬 원리
수학에서 정렬 원리(well-ordering principle) 또는 정렬 성질(well-ordering property)은 공집합이 아닌 모든 양의 정수 집합은 최소 원소를 갖는다는 정리이다.[1] 이것은 다른 말로 임의의 자연수 집합은 순서에 따른 정렬을 갖는다는 뜻이 된다.
속성
[편집]이 정리는 자연수가 도입되는 방식에 따라서 공리 혹은 증명 가능한 명제가 된다.
- 페아노 산술 등에서는 공리로 간주되는 수학적 귀납법에서 유도할 수 있다. 또한 정렬 원리는 수학적 귀납법과 동치이다.
- 자연수가 실수의 부분 집합이며 실수가 완전하다는 것을 가정하면 자연수의 임의의 부분 집합은 언제나 최소 원소를 갖는다는 것을 유도할 수 있다.[2]
- 집합론에서 자연수는 가장 작은 귀납 집합, 즉 0을 포함하고 다음수 연산에서 닫힌 집합으로 정의된다. 이로부터 이 정렬 성질을 갖는 모든 자연수 의 집합은 귀납적이며, 따라서 모든 자연수를 포함해야 함을 보일 수 있다.
응용
[편집]나눗셈 정리
[편집]정리: 두 정수 와 에 대하여 이라 하자. 그러면 을 만족하는 정수 와 이 유일하게 존재하며, 이때 이다. (이 경우 와 을 각각 를 로 나눈 몫과 나머지라고 한다.)
증명: 를 보다 큰 양의 정수의 집합이라고 하자. 그러면 정렬 원리에 의해 의 최소 원소 가 존재해야 한다. 즉, 가 성립한다. 여기서 이라 놓으면 이 되어 가 성립한다. 이제 라 놓으면 을 얻는다. 그러면 앞서 얻은 부등식에 의해 가 만족된다.
소인수 분해
[편집]정리: 1보다 큰 모든 정수는 소수의 곱으로 분해할 수 있다. (이것은 산술의 기본 정리에 포함된다.)
증명: 를 소수의 곱으로 분해할 수 없는 1보다 큰 모든 정수의 집합이라고 놓자. 우리는 가 공집합임을 보이려 한다. 귀류법을 위해 가 공집합이 아니라고 가정하자. 그러면 정렬 원리에 의해 이 집합의 최소 원소 이 존재해야 한다. 임의의 소수는 1과 자기 자신으로 분해할 수 있으므로 은 소수가 아니어야 한다. 따라서 의 소인수로써 1보다 크고 보다 작은 정수 와 가 존재한다. 이므로 이들은 의 원소가 아니다. 그러므로 와 는 소수의 곱으로 분해될 수 있으며, 와 로 놓을 수 있다. 그러면 이므로 소수들을 인수로 갖는 수가 되어 이라는 가정에 모순된다. 따라서 가 공집합이 아니라는 가정은 거짓이며, 는 공집합이다. 즉, 1보다 큰 모든 정수는 소수의 곱으로 분해할 수 있다.[3]
각주
[편집]- ↑ Apostol, Tom (1976). 《Introduction to Analytic Number Theory》. New York: Springer-Verlag. 13쪽. ISBN 0-387-90163-9.
- ↑ Binmore K.G. (1982). 《Mathematical Analysis: A Straightforward Approach》 2판. 21쪽. ISBN 9780521288828.
- ↑ Lehman, Eric; Meyer, Albert R; Leighton, F Tom. 《Mathematics for Computer Science》 (PDF). 2023년 6월 10일에 원본 문서 (PDF)에서 보존된 문서. 2023년 6월 24일에 확인함.