이제 선택공리를 통해 하우스도르프 극대원리를 증명해 봅시다. 이 명제의 증명을 위해 필요한 개념과 보조정리가 있어서 그를 먼저 확인할 것입니다. 다만 이 보조정리는 사실상 집합론에서 가장 어려운 증명으로 손꼽아도 무리가 아닐 정도로 호흡도 길고 논리가 복잡합니다. 길이로 따지면 제가 블로그에서 한 여느 증명보다도 긴 것 같네요. 다만 이러한 복잡하고 긴 증명을 하지 않으려면 조금 더 고급 수학 과목의 지식을 가져와야 합니다. 집합론 수준에서는 이러한 증명이 최선이라 보시면 됩니다.
썸네일은 앞으로 유머삼아 만드려고 합니다. '하우스'가 꼭대기에 있음을 상징하는 그림입니다.
1. 허용가능함
정의($S.T$) 5-7) 허용가능함 어떤 $a\in A$ 를 생각하자. $B\subseteq A$ 인 집합 $B$가 다음 세 조건을 만족할 때, $B$ 를 '허용가능함(admissible)'이라 한다. ① $a\in B$ ② $B$ 가 함수 $f$ 에 대해 닫혀있음 : $f(B)\subseteq B$ ③ $B$ 의 모든 사슬(전순서 부분집합)의 최소상계가 $B$ 에 속한다.
보조정리($S.T$) 5.1) 부분순서집합 $(A,\leq)$ 에 대해, 이것의 모든 사슬(전순서 부분집합)들의 최소상계들이 $A$ 에 포함되어 있다고 가정하자. 함수 $f:A\longrightarrow A$ 를 모든 $a\in A$ 에 대해 $a\longmapsto f(a)\geq a$ 로 정의하면, $f(p)=p$ 를 만족하는 어떤 $p\in A$ 가 반드시 존재한다.
증명) $\mathcal{B}=\left\{ B_i \right\}_i\in I$ 를 $A$ 의 모든 허용가능한 부분집합들로 이루어진 집합족(collection, family) 라 하자. $A$ 는 그러면 허용가능한데, 모든 $B_i$ 가 가진 원소를 $a\in A$ 라 하면 말그대로 $a\in A$ 가 성립하고, $f(A)\subseteq A$ 이며, 가정에 의하여 ③의 조건도 만족되기 때문이다.
1) 허용가능한 집합들의 교집합도 허용가능하다 : $T=\displaystyle\bigcap_{i\in I}B_i$ 라 하면 $T$ 도 허용가능하다. 우선 모든 $B_i$ 들이 허용가능하니 각각의 $B_i$ 가 $a\in A$ 를 가지고 있어서, $a\in T$ 이기 때문이다. 두번째로 $x\in T$ 라 하면 모든 $i\in I$ 에 대하여 $B_i$ 는 허용가능하니 모든 $i\in I$ 에 대하여 $x\in B_i$, $f(x)\in B_i$ 이다. 이는 $f(x)\in T$ 임을 뜻한다. 마지막으로 $Q$ 를 $T$ 의 한 사슬이라고 하자. 각각의 $i\in I$ 에 대하여 $T\subseteq B_i$ 가 성립하므로 $Q$ 는 각각의 $B_i$ 의 사슬이기도 하다. 즉, 각각의 $i\in I$ 에 대하여 $q:=\sup Q\in B_i$ 이기 때문에, $q=\sup Q\in T$ 이다.
2) 허용가능한 집합들의 교집합에서 순서관계를 집합의 포함관계로 부여했을 때 극소원소는 $B_0$ 이다 : $a\in A$ 으로 $A\neq \emptyset$ 이므로 $\mathcal{B}\neq \emptyset$ 이다. $\mathcal{B}$ 의 모든 원소들의 교집합을 $B_0$ 라 하자. 이 역시 허용가능하고, 모든 $i\in I$ 에 대하여 $B_0\subseteq B_i$ 이다. 그러면 $B_0$ 의 정의에 의해 $B_0$ 는 곧 $(\mathcal{B},\subseteq)$ 의 극소원소다. $B_0$ 보다 작은(= 포함관계로서 집합의 크기가 더 작은 = 순서관계가 밀리는) 집합이 존재한다고 가정하면 이는 $B_0$ 정의에 모순이다. 이로부터 부분순서집합 $(\mathcal{B},\subseteq)$ 은 극소원소 $B_0=\displaystyle\bigcap_{B_i\in \mathcal{B}} B_i$ 을 가진다는 것을 알 수 있다. 그리고 $B_0$ 유일하다.[각주:1]
3) $B$ 를 다음과 같이 생각하자 : 집합 $B=\left\{ x\in A\mid x\geq a \right\}$ 를 생각하고 $a\in A$ 에 대하여 집합 $B$ 가 허용가능한지 확인하자. $a\geq a$ 임은 자명하다. 한편 임의의 $x\in B,\;, a\in A$ 에 대하여 가정에 주어진 것과 같이 함수 $f$ 를 정의하면 $f(x)\geq x\geq a$ 가 성립하여, $f(x)\geq a$ 이므로 $f(x)\in B$ 가 된다. 이는 $f(B)\subseteq B$ 를 뜻한다. 또한 $S$ 를 $B\subseteq A$ 의 사슬이라고 하자. $B$ 의 정의에 의하여 $S$ 의 모든 원소 $s$ 는 $s\geq a$ 를 만족해야 하고, 보조정리의 가정에 의해 $S$ 는 $A$ 의 한 사슬이기도 하니 $\sup S \in A$ 가 존재하며 $\sup S\in B$ 이기도 하다. 따라서 $B$ 의 사슬의 최소상계가 $B$ 에 속하기도 하니 $B$ 는 허용가능하다. 이상에서 $\subseteq\left\{ x\in A\mid x\geq a \right\}$ 가 허용가능하므로, 2)의 내용과 연결하면 $B_0\subseteq\left\{ x\in A\mid x\geq a \right\}$ 이다. 그러면 모든 $x\in B_0$ 에 대하여 $x\geq a$ 가 성립한다.
이제부터 할 일은 아래에서 정의할 두 집합 $C,D$ 에 대하여 $C=D=B_0$ 임을 보이는 것이다. 우선 4)에서 $D=B_0$ 를 보이고 5)에서 $C=B_0$ 를 보일 것이다. 참고로 $C$ 집합은 $f$ 를 타고 넘어가도 순서관계가 바뀌지 않으니 $f$ 의 상한 역할을 보여주고, $D$ 는 $x$ 를 기준으로 분할의 역할을 담당한다고 볼 수 있다 결과적으로 세 집합이 같음을 보이면 $f(p)=p$ 인 고정점 $p$ 의 존재를 암시한다.
4) 집합 $C=\left\{ x\in B_0\mid y\in B_0\;\wedge \; y < x \;\Rightarrow \; f(y)\leq x \right\}$ 를 생각하자.
$$x\in C \;\wedge \; z\in B_0 \;\Longrightarrow \; z\leq x \; \vee \; z\geq f(x)\;\;\;\;\;\cdots \;\;\;(1)$$ 임을 보이고 싶다. $x\in C$ 를 고정시키고 $D=\left\{ z\in B_0\mid z\leq x \; \vee \; z\geq f(x) \right\}$ 라 하자. 3)에서 그러면 $a\in B_0$ 이고, $x\geq z=a$ 로 $z$ 를 택하면 $a\in D$ 가 만족됨을 알 수 있다. 두번째로 $f(D)\subseteq D$ 를 보여야 하고, 이는 곧 $f(z)\in D$ 임을 의미하는 것이니 $f(z)\leq x$ 또는 $f(z)\geq f(x)$ 를 뜻한다.
세번째 조건을 확인하라면 $E\subseteq D$ 가 $D$ 의 사슬이고 $u:=\sup E$ 라 하자. 그러면 모든 $e\in E$ 에 대해 $e\leq x$ 이거나 $e\geq f(x)$ 여야 한다. 전자의 경우 $y\leq x$, 후자의 경우 $u\geq f(x)$ 가 성립하니 결국 $u\in D$ 이다. 이상에서 $D$ 는 허용가능한데 $D$ 의 정의를 고려하면 이는 $B_0$ 의 원소들로 이루어져 있고 이 집합은 2)에서 유일하고 극소임을 보였다. 결국 $D=B_0$ 가 성립한다.
5) 3)에서 보인 내용에 의해 모든 $y\in B_0$ 에 대해서 반드시 $y\geq a$ 이다. 첫째, 만일 '그리고'로 연결된 문장 $y\in B_0\;\wedge \; y<a$ 을 고려하면, 이 명제는 거짓이니, 조건문의 가정[각주:2]이 거짓이면 조건문은 참이므로 $a\in C$ 이다. 둘째, $f(C)\subseteq C$ 를 확인해야 하고 이것은 임의의 $x\in C$ 에 대해 $f(x)\in C$ 인지를 보이는 것과 같다. 확인해야할 것은 결국
$$y\in B_0\; \wedge\; y < f(x) \; \Longrightarrow \; f(y)\leq f(x)\;\;\;\;\;\cdots \;\;\;(2)$$ 인지에 해당한다.
i) $y\geq f(x)$ : $y < f(x)$ 가 거짓이다. 위에서와 동일한 논리로 조건문의 가정이 거짓이 된다. 고로 $f(x)\in C$ ii) $y\leq x$ : $y=x$ 이면 $f(y)=f(x)$ 가 되니 $(2)$ 가 참이다. $y < x$ 이면 $f(y) \leq x\leq f(x)$[각주:3] 이므로, 다시 $(2)$ 가 참이다.
세번째 조건을 확인하자. $G\subseteq C$ 가 $C$ 의 사슬이고 $w:=\sup G$ 라 하자. 보이고 싶은 것은 $w\in C$ 이다. 우선 $w=\sup G$ 이므로 $y<w$ 인 $y\in B_0$ 가 존재한다. 이때 우리는 $f(y)\leq w$ 임을 보이면 된다. 그런데 3)으로부터 $B_0=D$ 임을 알기 때문에 $y\in B_0 = D$ 이고, 고로 임의의 $g\in G$ 에 대해 $y\leq g$ 또는 $y\geq f(g)$ 가 성립해야 한다. 후자가 성립하면 $y\geq f(g) \geq g$ 에서 $y \leq g$ 가 성립하고, $g=w$ 는[각주:4] 모순이다. 고로 $y\leq g$ 다.
i) $y<g$ : $f(g)\leq g \leq w$ 이다. 첫째 부등호는 $g\in C$ 이기 때문에, 둘째 부등호는 $g\in G$ 이기 때문에 성립한다.
ii) $y=g$ : $y=g < w \;\Longrightarrow \; y < h$ 인 $h\in G$ 가 존재한다. 그러면 다시 $C$ 의 정의와 $w=\sup G$ 로부터 $f(y)\leq z \leq w$ 가 성립한다.
6) 따라서 i),ii) 모두에 $y<w \;\Longrightarrow \; f(y)\leq w$ 가 성립하므로 $w\in C$ 이며, 세 조건을 모두 확인한 결과 $C$ 는 허용가능하다. 2) 에서 $B_0$ 는 유일하고 극소원소라고 하였으니 $B_0=C$ 이다.
여기까지의 관계를 정리하면 $B_0=C=D$ 이다. 그러면 $(1)$ 에서 $B_0$ 는 전순서집합이다. 허용가능함의 세 번째 조건에서 $p:=\sup B_0=\sup C$ 가 존재한다. $p$ 가 최소상계이니 $p\leq f(p)$ 이어야 한다. 그러나 애초에 함수 $f$ 의 정의에 의하면 $f(p)\geq p$ 이다. 고로, $f(p)=p$ 인 $p\in B_0$ 가 존재한다. $B_0\subseteq A$ 이니 $p\in A$ 이기도 하다. $_\blacksquare$
정리($S.T$) 5.1) 하우스도르프 극대원리(Hausdorff Maximality Principle) 부분순서집합 $(A,\leq)$ 의 모든 전순서 부분집합(사슬)들을 원소로 갖는 집합족을 $\mathcal{T}$ 라 하고, $\mathcal{T}$ 에 부분순서로서 포함관계 $\subseteq$ 가 주어졌다고 하자. 그러면 $(\mathcal{T}, \subseteq)$ 는 극대원소를 가진다.
증명) 귀류법을 사용하기 위해 $\mathcal{T}$ 가 극대원소를 가지지 않는다고 가정하자. 그러면 각각의 $T\in\mathcal{T}$ 에 대하여 $$T^*=\left\{ T'\in \mathcal{T}\mid T\subset T' \right\}$$ 라는 집합을 정의할 수 있고 $T^*\neq \emptyset$ 이다.[각주:5] 그러면 선택공리에 의하여 다음과 같은 선택함수 $$g:\left\{ T^*\mid T\in\mathcal{T} \right\}\longrightarrow \displaystyle \bigcup_{T\in\mathcal{T}}^{}T^* $$ 를 $g(T^*)\in T^*$ 를 만족하도록 잡을 수 있고, 다시 모든 $T\in\mathcal{T}$ 에 대하여 $f(T):g(T^*)$ 가 되도록 함수 $f:\mathcal{T}\longrightarrow \mathcal{T}$ 를 생각할 수 있다.
그 다음으로 $(\mathcal{T},\subseteq)$ 가 공집합이 아닌 부분순서집합이고, 이것의 모든 사슬이 $\mathcal{T}$ 내에 최소상계를 가짐을 보이려고 한다. $\mathcal{B}$ 를 $(\mathcal{T},\subseteq)$ 의 임의의 한 사슬이라 하자.[각주:6] 그러면 $\displaystyle \bigcup_{B\in\mathcal{B}}^{}B$ 는 사슬 $\mathcal{B}$ 에 속하는 모든 집합들의 원소로 이루어진 집합[각주:7]으로, $\mathcal{B}$ 의 모든 원소들의 합집합이다.
* $\mathcal{B}$ 는 사슬이니, 원소가 집합이다. 반면 반복되어 등장하는 $\displaystyle \bigcup_{B\in\mathcal{B}}^{}B$ 라는 친구는 원소가 모두 집합이 아니다. 사슬 $\mathcal{B}$ 를 구성하는 하나 하나의 집합들 $B_i$ 의 원소들을 전부 다 끌어모은 합집합인 것이다. 둘을 잘 구분해서 따라와야 한다.
이때 $\mathcal{T}$ 내의 다른 원소 즉 사슬을 생각하고, 그것이 $\mathcal{B}$ 를 포함한다고 해보자. 그러면 그 집합 역시 $\displaystyle \bigcup_{B\in\mathcal{B}}^{}B$ 를 포함할 것이고, 그리하여 $\displaystyle \bigcup_{B\in\mathcal{B}}^{}B \subseteq \displaystyle \bigcup_{C\in\mathcal{C}}^{}C$ 이다.[각주:8] 즉 일단 $\displaystyle \bigcup_{C\in\mathcal{C}}^{}C$ 는 $\mathcal{B}$ 에 대한 $\mathcal{T}$ 에 속하는 하나의 상계이다. 그러면 최소상계의 정의를 상기할 때, $\displaystyle \bigcup_{B\in\mathcal{B}}^{}B$ 는 $\mathcal{B}$ 에 대한 (포함관계를 순서로 볼 때) 최소상계(상한)가 된다. $\displaystyle \bigcup_{B\in\mathcal{B}}^{}B\in \mathcal{T}$ 가 $\mathcal{B}$ 의 최소상계라는 것은 모든 $B\in\mathcal{B}$ 에 대하여 $B\subseteq \displaystyle \bigcup_{B\in\mathcal{B}}^{}B$ 임과 필요충분조건인데 그러하기 때문이다.
고로, $\displaystyle \bigcup_{B\in\mathcal{B}}^{}B\in\mathcal{T}$ 이며 이것은 최소상계이다. 보조정리($S.T$) 5.1) 의 가정에서 부분순서집합으로 $(\mathcal{T},\leq=\subseteq)$ 를 생각하면, 이것의 임의의 사슬 $\mathcal{B}$ 의 최소상계 $\displaystyle \bigcup_{B\in\mathcal{B}}^{}B$ 는 $\mathcal{T}$ 에 속한다. 그러므로 보조정리의 가정은 모두 만족되었다. 따라서 보조정리에 의하여 $f(T)=T$ 가 되게 하는 어떤 사슬 $T\in\mathcal{T}$ 가 존재한다.
그런데, 맨 처음 함수의 정의에 의하여 $f(T)=g(T^*)$ 로 정의하였다. $T^*$ 는 정의에 의해 $T\subset T'$ 인 $T'$ 으로 이루어진 집합이니 $T \subset g(T^*)\in \displaystyle \bigcup_{T\in\mathcal{T}}^{}T^*$ 이고, 고로 $T\subseteq f(T)$ 이다. 따라서 윗 문단에서 보조정리를 사용한 결과 $f(T)=T$ 는 이러한 함수 $f$ 가 존재한다는 것에 모순이다. $_\blacksquare$
왜냐하면 $\mathcal{T}$ 에 극대원소가 없다고 가정했기 때문이다. 극대원소가 없다면 임의의 원소에 대해 그보다 더 상위의 포함집합이 반드시 존재한다는 논리이다. [본문으로]
예컨대 위의 사진에서 파란색 부분의 사슬을 잡았다고 해보자. 다만 주의할 것이 위의 사진 상황은 하나의 예시이며, 이 증명에서는 가장 처음에 우리가 $\mathcal{T}$ 에 극대원소가 없다고 잡았으니 실제로 사진의 윗 부분에 계속해서 집합이 존재하는 꼴이여야 함을 참고. [본문으로]
댓글