자연수의 정렬성

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

자연수의 정렬성(Well-ordering Principle)은 공집합이 아닌 모든 자연수 집합의 부분집합은 하나의 최소 정수를 포함한다는 정리이다.

증명[편집]

A \subset \mathbb{N}_0, A \not = \varnothing 이면  \forall n \in \mathbb{N}_0 \exists a \in A : n \in A \rightarrow a \le n 이다.


수학적 귀납법을 사용하기 위하여 ' P(n): n \in A 이면, 집합  A 는 최소원소를 갖는다.' 로 놓자.

이때,  P(0) 는 ,  \forall n \in A : 0 \le n 이므로, 참이다.

 P(0),P(1),...,P(k) 가 참이라 가정하고,  k+1 \in A 이면 (단,  k \in \mathbb{N}_0 ),

(1)  \exists n \le k : n \in A 인 경우,  P(n) 이 참이므로, 집합  A 는 최소원소를 갖는다.

(2)  \not\exists n \le k : n \in A 인 경우,  k+1 은 집합  A 의 최소원소이다.

따라서  P(k+1) 은 참이다.

수학적 귀납법에 의하여 , \forall n \in A : P(n) 은 참, 이다. 즉,  \exists n \in A 이면, 집합  A 는 최소원소를 갖는다.