집합론, 그 서른두 번째 이야기 | '원소관계의 무한 강하 사슬은 존재하지 않는다'의 증명 ( Proof of 'No Infinitely Descending Membership Chains' )  By 초코맛 도비

이번 글에서는 제목 그대로 원소관계의 무한 강하 사슬은 존재하지 않다는 사실을 보일 것이다. 이 사실은 상당히 중요한 사실 중 하나인데, 이를 통해 x={x}와 같은 집합이 존재하지 않는다는 사실을 얻을 수 있기 때문이다. 다음 정리를 보자.

 

Theorem 1.

집합의 열 {Xn}nN을 생각하자. 그러면 반드시 다음을 만족하는 자연수 n이 존재한다.
Xn+1Xn

 

Proof.

정리가 틀렸다고 가정하자. 즉, 임의의 자연수 n에 대하여 Xn+1Xn을 만족하는 집합의 열 {Xn}nN이 존재한다고 가정하자.

그러면 치환 공리꼴에 의해 모임 S={Xn|nN}는 집합이다.

그러면 정칙성 공리에 의해 XS=XS가 존재한다.

이때, S의 정의에 의해 어떤 자연수 m에 대하여 X=Xm이다.

따라서 XmS=이며, Xm+1S로부터, Xm+1Xm임을 알 수 있다.

이는 임의의 자연수 n에 대하여 Xn+1Xn이라는 가정에 모순되며, 따라서 정리가 증명된다.

 

위 정리는 다음과 같은 따름정리들을 이끌어낸다.

 

Corollary 1.

집합 X와 임의의 양의 정수 n에 대하여 명제 P(n)을 다음과 같이 정의하자.
(x1,x2,,xn) s.t. X=xnxn1x1X
그러면 임의의 양의 정수 n에 대하여 ¬P(n)이 성립한다.

 

Corollary 2.

{αn}nN가 서수의 열이라고 하자. 그러면, 다음을 만족하는 자연수 n이 존재한다.
αnαn+1

 

위 따름정리들은 Theorem 1의 자명한 결과이므로 굳이 증명을 서술하지는 않겠다. 궁금하다면 직접 증명을 시도해보는 것을 권한다. 또한, Corollary 1으로부터 서수의 모임이 집합이 아니라는 것을 증명할 수 있다. 다음을 보자.

 

Corollary 3.

서수의 모임 Ord는 집합이 아니다.

 

Proof.

귀류법을 사용하기 위해 따름정리를 부정하자. 즉, 서수의 모임인 Ord가 집합이라고 가정하자.

이때, Ord의 임의의 원소 α는 서수이므로 α보다 작은 모든 서수를 원소로 가진다.

따라서 αOrd이며, 이로 인해 Ord는 추이적 집합이다.

이제 Ord가 정렬집합임을 보이자.

Ord의 임의의 공집합이 아닌 부분집합 S를 생각하자.

이때, S가 최소원소를 가지면 Ord가 정렬집합이다.

S가 최소원소를 가진다는 것을 보이기 위해 β=S를 생각하자.

그러면 β는 서수의 교집합이므로 β는 서수이다.

또한, 임의의 γS에 대하여 βγ이므로 βS의 하계임이 자명하다.

이제 βS임을 보이면 βS의 최소원소임이 보여진다.

만약 βS라면, 임의의 γS에 대하여 βγ이다. (βγ이므로)

그런데, β의 정의에 의해 βS=β이며, 이는 Corollary 1에 의하여 모순이다.

따라서 βS이며, 이로 인해 S는 최소원소를 가진다. 즉, Ord는 정렬집합이다.

Ord가 추이적 집합이면서 동시에 정렬집합이므로 Ord는 서수이다.

그런데, Ord는 모든 서수의 모임이므로 OrdOrd이고, 이는 Corollary 1에 의하여 Ord가 집합이라는 가정에 모순이다.

따라서 Ord는 집합이 아니다.

댓글()