정렬 원리

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

1. 개요
2. 속성
3. 증명 방법으로서의 응용
4. 응용
5. 비대수적 속성
참조

1. 개요

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

더 읽어볼만한 페이지

기초관계 - 전체집합
전체집합은 특정 맥락에서 고려되는 모든 객체를 포함하는 집합을 의미하나, 집합론에서는 모순을 피하기 위해 존재가 인정되지 않으며, 공리적 집합론에서는 고유 클래스 개념을 사용해 전체성을 표현한다.
기초관계 - 정렬 원순서 집합
정렬 원순서 집합은 무한 증가 부분열 존재, 내림 사슬 조건 만족 등 여러 동치 조건을 만족하며, 시뮬레이션과 순서형 개념으로 분석되고, 선택 공리와 동치 관계에 있으며, 순서 위상을 부여하여 위상 공간으로 만들 수 있다.
수론 - 타원곡선
타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
수론 - 최소공배수
최소공배수는 둘 이상의 정수들의 공배수 중 가장 작은 양의 정수로서, 소인수분해나 최대공약수와의 관계를 이용하여 구할 수 있으며, 분수 통분이나 기어 회전 수 계산 등 여러 분야에 응용된다.

정렬 원리
기본 정보
이름	정렬 원리
영어 이름	Well-ordering principle
설명	모든 공집합이 아닌 양의 정수의 부분집합은 최소 원소를 가진다는 정리
관련 개념
관련 개념	수학적 귀납법
같이 보기
같이 보기	정렬 정리

2. 속성

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

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

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

2. 1. 페아노 공리계

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

2. 2. 실수의 부분 집합

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

2. 3. 집합론

집합론에서 자연수는 가장 작은 귀납적 집합, 즉 0을 포함하고 다음수 연산에 닫혀 있는 집합으로 정의된다. 이로부터

\{0,\ldots,n\}

이 정렬 성질을 갖는 모든 자연수

n

의 집합은 귀납적이며, 따라서 모든 자연수를 포함해야 함을 보일 수 있다.^[4] 이로부터 모든 자연수의 집합 또한 정렬되어 있다는 것을 결론내릴 수 있다.

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

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

4. 응용

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

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보다 큰 모든 정수는 소수의 곱으로 분해할 수 있다.^[5]

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

에 대해 성립함을 보여주며, 이는 모순이다. 따라서, 방정식은 모든 양의 정수에 대해 성립해야 한다.^[2]

5. 비대수적 속성

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

참조

_[1] 서적 Introduction to Analytic Number Theory https://archive.org/[...] Springer-Verlag
_[2] 서적 Mathematics for Computer Science https://courses.csai[...] 2023-05-02
_[3] 서적 Introduction to Analytic Number Theory https://archive.org/[...] Springer-Verlag
_[4] 서적 Mathematical Analysis: A Straightforward Approach
_[5] 서적 Mathematics for Computer Science https://courses.csai[...] 2023-06-24

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com