집합론, 그 서른세 번째 이야기 | Well-Founded Relation

이번 글에서는 Well-Founded Relation에 대해 다룰 것이다. Well-founded relation이란, 정의역의 임의의 공집합이 아닌 부분집합에 대해 최소원소를 가지는 이항관계를 말하는 것으로, 더 엄밀하게는 다음과 같이 정의한다.

 

Definition 1.

집합 $P$ 위의 이항관계 $E$에 대하여, 임의의 공집합이 아닌 부분집합 $X \subseteq P$에 대하여 $E$-최소원소를 가질 때, $E$를 well-founded라고 하며, well-founded인 관계를 well-founded relation이라고 한다. 여기서, $E$-최소원소란, 다음을 만족하는 $a \in X$를 말한다. $$\forall x \in X, \; \neg \left( xEa \right)$$

 

위와 같은 정의로부터, 다음과 같은 자명한 사실 하나를 얻을 수 있다.

 

Proposition 1.

임의의 정렬순서집합 $(X, \leq)$에 대하여 다음과 같이 정의되는 순서관계 $<$는 well-founded relation이다. $$ x < y \Leftrightarrow x \leq y \land \neg \left( y \leq x \right) $$

 

또한, well-founded relation의 정의를 보면 감이 오겠지만, well-founded relation은 일종의 순서관계처럼 생각할 수 있으며, 따라서 집합의 '높이'를 정의하는 것이 가능하다. 다음 정리를 보자.

 

Theorem 1.

집합 $P$ 위의 이항관계 $E$가 well-founded relation이라고 하자. 그러면 다음을 만족하는 함수 $\rho : P \to \text{Ord}$가 유일하게 존재한다. $$ \rho \left( x \right) = \sup \{ \rho \left( y \right) + 1 \;|\; y E x \} $$ 또한, 그러한 $\rho$의 치역은 서수이다.

 

Proof.

먼저 조건을 만족하는 함수 $\rho$의 존재성을 보이자.

초한 귀납법을 통해 다음을 만족하는 집합의 열을 정의할 수 있다.

1) $P_0 = \varnothing$

2) 임의의 서수 $\alpha$에 대하여, $P_{\alpha+1} = \{ x \in P \;|\; \forall y \in P, \; y E x \Rightarrow y \in P_\alpha \}$

3) 임의의 $0$이 아닌 극한 서수 $\alpha$에 대하여, $P_\alpha = \displaystyle \bigcup_{\xi < \alpha} P_\xi$

위와 같이 집합의 열 $P_\alpha$를 정의하면, 임의의 서수 $\alpha$에 대하여 $P_\alpha \subseteq P_{\alpha+1}$임은 귀납법으로부터 쉽게 알 수 있다. 이에 대한 증명은 아래의 '증명 보기'를 클릭하면 볼 수 있다.

 

임의의 서수 $\alpha$에 대하여 $P_\alpha \subseteq P_{\alpha+1}$임을 보이기 위해서는 임의의 원소 $x \in P_\alpha$에 대하여 $y E x \Rightarrow y \in P_\alpha$임을 보이면 충분하다. 이를 $\alpha$에 대한 귀납법을 통해 보이자.

 

Base Case.

$P_0$은 공집합이므로 임의의 $x \in P_0$에 대하여 $y E x \Rightarrow y \in P_0$임은 자명하다.

 

Successor Case.

서수 $\alpha$에 대하여 $P_\alpha \subseteq P_{\alpha+1}$이라고 가정하자.

이제 임의의 $x \in P_{\alpha+1}$을 생각하자.

그러면 $P_{\alpha+1}$의 정의에 의해 $y E x \Rightarrow y \in P_{\alpha}$가 성립하며, 귀납가정에 의해 $P_\alpha \subseteq P_{\alpha+1}$이므로 $y E x \Rightarrow y \in P_{\alpha+1}$이 성립한다.

따라서 $x \in P_{\alpha+2}$임을 알 수 있으며, 이로 인해 $P_{\alpha+1} \subseteq P_{\alpha+2}$이다.

 

Limit Case.

$0$이 아닌 극한 서수 $\alpha$를 생각하자.

임의의 서수 $\xi < \alpha$에 대하여 $P_\xi \subseteq P_{\xi+1}$이 성립한다고 가정하자.

이제 임의의 $x \in P_\alpha$를 생각하자.

그러면 $P_\alpha$의 정의에 의해 어떤 $\xi < \alpha$에 대하여 $x \in P_{\xi+1}$이 성립하며, 귀납가정에 의해 $y E x \Rightarrow y \in P_\xi$가 성립한다.

이때, $P_\alpha = \displaystyle \bigcup_{\xi < \alpha} P_\xi$이므로 임의의 $\xi < \alpha$에 대하여 $P_\xi \subseteq P_\alpha$가 성립한다.

따라서 $y E x \Rightarrow y \in P_\alpha$가 성립하며, $P_{\alpha+1}$의 정의에 의해 $x \in P_{\alpha+1}$임을 알 수 있다. 이로 인해 $P_\alpha \subseteq P_{\alpha+1}$이다.

$\blacksquare$

 

따라서 임의의 두 서수 $\alpha < \beta$에 대하여 언제나 $P_\alpha \subseteq P_\beta$가 성립함을 알 수 있다.

이제 $\theta$를 $P_{\theta+1} = P_\theta$를 만족하는 최소의 서수로 정의하자.

이러한 $\theta$의 존재성의 증명은 아래의 '증명 보기'를 클릭하면 볼 수 있다.

 

그러한 $\theta$가 존재하지 않는다고 가정하자.

즉, 임의의 서수 $\alpha$에 대하여 $P_\alpha \subsetneq P_{\alpha+1}$라고 가정하자.

그러면, 임의의 두 서수 $\alpha < \beta$에 대하여 $P_\alpha \subsetneq P_\beta$임을 쉽게 알 수 있으며, 이는 $\text{Ord}$에서 $\mathcal{P}\left( P \right)$^[각주:1]로 가는 단사함수의 존재성을 시사한다.

이로부터 자연스럽게 $\mathcal{P}\left( P \right)$에서 $\text{Ord}$로 가는 전사함수의 존재성을 알 수 있으며, $\mathcal{P}\left( P \right)$가 집합이므로 치환 공리꼴에 의해 $\text{Ord}$는 집합이어야 한다.

하지만, 이는 이 글의 Corollary 3에 모순이며, 따라서 그러한 $\theta$는 존재할 수밖에 없다.

$\blacksquare$

 

이때 만약 $P \neq P_\theta$라면 $E$가 $P$ 위의 well-founded relation이므로 $P \setminus P_\theta$의 $E$-최소원소 $a$가 존재한다. 그러면, $x E a$를 만족하는 모든 $x \in P$는 $P_\theta$의 원소이어야만 하며, 이는 곧 $a \in P_{\theta+1}$을 의미한다. 그러나, 이는 서수 $\theta$의 정의에 모순이며, 따라서 $P = P_\theta$임이 증명된다.

이제 함수 $\rho : P \to \text{Ord}$를 $\rho \left( x \right)$가 $x \in P_{\alpha+1}$인 가장 작은 서수 $\alpha$로 정의하자. 그러면 $x E y \Rightarrow \rho \left( x \right) < \rho \left( y \right)$임이 자명하다.

따라서 $\rho$가 조건을 만족함을 쉽게 확인할 수 있으며, $\rho$의 치역은 $\theta$이다.

이제 조건을 만족하는 함수 $\rho$가 유일함을 보이자.

조건을 만족하는 또다른 함수 $\rho'$가 존재함을 가정하면, 집합 $S = \{ x \in P \;|\; \rho(x) \neq \rho'(x) \}$가 공집합이 아니므로 $S$ 역시 $E$-최소원소를 가진다.

$S$의 $E$-최소원소를 $m$이라고 하자. 그러면, $x E m$인 모든 $x \in P$에 대하여 $\rho(x) = \rho'(x)$임이 자명하다.

그러나, $\rho$와 $\rho'$ 모두 조건을 만족하므로 $\rho(m) = \sup \{ \rho(x)+1 \;|\; x E m\} = \rho'(x)$이며, 이는 $m$의 정의에 모순이다.

따라서 조건을 만족하는 함수 $\rho$는 유일하다.

$\blacksquare$

 

위 정리로부터 다음과 같은 두 가지의 개념을 정의할 수 있다.

 

Definition 1.

집합 $P$ 위의 이항관계 $E$가 well-founded relation이라고 하자. 그러면 Theorem 1에서 정의되는 함수 $\rho$의 치역을 $P$의 높이 (Height)라고 한다.

 

Definition 2.

집합 $P$ 위의 이항관계 $E$가 well-founded relation이라고 하자. 그러면 Theorem 1에서 정의되는 함수 $\rho$를 Rank Function이라고 하며, $\rho(x)$를 $x$의 Rank라고 한다.

 

1. 여기서 P(P)는 P의 멱집합을 의미한다. [본문으로]