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

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

 

Theorem 1.

집합의 열 $\{ X_n \} _{n \in \mathbb{N}}$을 생각하자. 그러면 반드시 다음을 만족하는 자연수 $n$이 존재한다. $$ X_{n+1} \notin X_n $$

 

Proof.

정리가 틀렸다고 가정하자. 즉, 임의의 자연수 $n$에 대하여 $ X_{n+1} \in X_n $을 만족하는 집합의 열 $\{ X_n \}_{n \in \mathbb{N}}$이 존재한다고 가정하자.

그러면 치환 공리꼴에 의해 모임 $S = \{ X_n \;|\; n \in \mathbb{N} \}$는 집합이다.

그러면 정칙성 공리에 의해 $X \cap S = \varnothing$인 $X \in S$가 존재한다.

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

따라서 $X_m \cap S = \varnothing$이며, $X_{m+1} \in S$로부터, $X_{m+1} \notin X_m$임을 알 수 있다.

이는 임의의 자연수 $n$에 대하여 $X_{n+1} \in X_n$이라는 가정에 모순되며, 따라서 정리가 증명된다.

$\blacksquare$

 

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

 

Corollary 1.

집합 $X$와 임의의 양의 정수 $n$에 대하여 명제 $P(n)$을 다음과 같이 정의하자. $$ \exists \left( x_1, x_2, \cdots, x_n \right) \text{ s.t. } X = x_n \in x_{n-1} \in \cdots \in x_1 \in X $$ 그러면 임의의 양의 정수 $n$에 대하여 $\neg P(n)$이 성립한다.

 

Corollary 2.

$\{ \alpha_n \}_{n \in \mathbb{N}}$가 서수의 열이라고 하자. 그러면, 다음을 만족하는 자연수 $n$이 존재한다. $$ \alpha_n \leq \alpha_{n+1} $$

 

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

 

Corollary 3.

서수의 모임 $\text{Ord}$는 집합이 아니다.

 

Proof.

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

이때, $\text{Ord}$의 임의의 원소 $\alpha$는 서수이므로 $\alpha$보다 작은 모든 서수를 원소로 가진다.

따라서 $\alpha \subseteq \text{Ord}$이며, 이로 인해 $\text{Ord}$는 추이적 집합이다.

이제 $\text{Ord}$가 정렬집합임을 보이자.

$\text{Ord}$의 임의의 공집합이 아닌 부분집합 $S$를 생각하자.

이때, $S$가 최소원소를 가지면 $\text{Ord}$가 정렬집합이다.

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

그러면 $\beta$는 서수의 교집합이므로 $\beta$는 서수이다.

또한, 임의의 $\gamma \in S$에 대하여 $\beta \subseteq \gamma$이므로 $\beta$는 $S$의 하계임이 자명하다.

이제 $\beta \in S$임을 보이면 $\beta$가 $S$의 최소원소임이 보여진다.

만약 $\beta \notin S$라면, 임의의 $\gamma \in S$에 대하여 $\beta \in \gamma$이다. ($\beta \subseteq \gamma$이므로)

그런데, $\beta$의 정의에 의해 $\beta \in \bigcup S = \beta$이며, 이는 Corollary 1에 의하여 모순이다.

따라서 $\beta \in S$이며, 이로 인해 $S$는 최소원소를 가진다. 즉, $\text{Ord}$는 정렬집합이다.

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

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

따라서 $\text{Ord}$는 집합이 아니다.

$\blacksquare$