이번 글에서는 드디어 선택공리를 소개한다. 이후 이전 글에서 다뤘던 ordinal number들 사이의 순서관계를 정의한다.
선택공리와 그 동치들
The Axiom of Choice. 임의의 집합은 choice function을 갖는다.
여기에서 choice function이란 집합들의 모임 \(\mathcal{S}\) 위에서 정의된 함수로, \(f(X)\in X\)가 모든 \(X\in\mathcal{S}\)에 대해 성립한다. 즉, \(f\)는 각각의 집합 \(X\)마다 원소를 하나씩 뽑아오는 함수이다. 우리는 사실 알게 모르게 계속해서 이 공리를 써 왔는데, 임의의 집합에서 원소를 하나 뽑은 경우가 모두 그러하다.
이 다음에 우리는
임의의 well-ordered set은 어떠한 ordinal과 order isomorphic하다
는 것을 증명한다. §서수와 정렬집합, ⁋예시 3에서 보았듯 많은 ordered set은 well-ordered set이 아니므로 위의 명제의 조건이 매우 까다로운 것처럼 보이지만, 사실 선택공리를 잘 사용하면 다음의 정리를 보일 수 있다.
정리 1. (Zermelo) 임의의 집합 \(A\)에 well-ordering을 줄 수 있다.
이 정리가 뜻하는 바는 집합 \(A\)가 원래 순서가 부여되어 있던 ordered set이든, 혹은 아무런 정보도 없는 그냥 집합이든 간에 관계 없이, 새로운 order relation을 부여할 수 있다는 것이다. 예를 들어 \((\mathbb{R},\leq)\)는 well-ordered set이 아니지만, 그럼에도 불구하고 이 집합 \(\mathbb{R}\)을 well-ordered set으로 만드는 적당한 order relation \(\preceq\)을 정의할 수 있다.
보조정리 2 (Tarski-Bourbaki) \(A\)가 집합이고, \(\mathcal{S}\subset\mathcal{P}(A)\), \(p:\mathcal{S}\rightarrow A\)가 \(p(X)\not\in X\)를 만족한다고 하자. 그럼 well-ordered subset \((M,\leq)\)가 존재하여 다음의 조건들을 만족한다.
- 모든 \(x\in X\)에 대하여, \(S_x\in\mathcal{S}\)이고 \(p(S_x)=x\)이다.
- \(M\not\in\mathcal{S}\).
증명
\(\mathcal{M}\)을 다음의 조건을 만족하는 관계들 \(R\subseteq A\times A\)의 모임이라 하자.
- \(G\)는 \(R=\pr_1R\)에서의 well-ordering이다.
- 각각의 \(x\in U\)에 대하여, \(S_x\in\mathcal{S}\)이고 \(p(S_x)=x\)이다.
우리는 \(\mathcal{M}\)의 원소 \(G\)마다 정의된 \(U=\pr_1G\)가 §정렬집합의 성질들, ⁋명제 4의 조건을 만족함을 보일 것이다. 이를 위해 임의의 \(U\), \(U'\)에 대하여 \(U\)가 \(U'\)의 segment이거나 그 반대라는 것을 보이자.
\(G\), \(G'\in \mathcal{M}\)가 임의로 주어졌고 \(U\), \(U'\)가 그 정의역이라 하자. 이 때, (1) \(x\)를 끝점으로 갖는 segment가 \(U\)와 \(U'\)에서 동일한 집합을 나타내고, (2) 그 segment 위에서의 order가 \(G\)와 동일하도록 하는, \(x\in U\cap U'\)들을 모아 그 집합을 \(V\)라 하자. 만일 \(x\in V\)이고 \(y\in U\)가 \(y\leq x\)를 만족한다면, \(U\)와 \(U'\) 모두에서 \(y\in S_x\)이다. 또, \(U\)에서 \(y\)보다 작은 원소는 \(U'\)에서도 \(y\)보다 작다. 따라서 \(y\in V\)이고, \(V\)는 \(U\)의 segment이다.
이제 \(U\)와 \(U'\)가 원하는 조건을 만족하기 위해서는, \(U=V\)이거나 반대로 \(U'=V\)임만 보이면 충분하다. \(V\neq U\)이고 \(V\neq U'\)라 가정하자. 그럼 \(U\setminus V\)와 \(U'\setminus V\)의 least element \(x\)와 \(x'\)에 대하여, \(V=S_x=S_{x'}\)가 \(U\)와 \(U'\) 각각에서 성립한다. 그런데 두 번째 조건에 의하여 \(V\in\mathcal{S}\)이므로 \(x=p(S_x)=p(V)=p(S_{x'})=x'\)이고, 따라서 \(x\in V\)이다.
이제 §정렬집합의 성질들, ⁋명제 4를 활용하여 well-ordered set \(M=\bigcup_{G\in\mathcal{M}}\pr_1G\)를 얻는다. 자명하게 \(M\in\mathcal{M}\)이므로 \(M\)은 명제의 성질 1을 만족한다. 만일 \(M\in\mathcal{S}\)라면 \(\mathcal{S}\)의 조건에서 \(p(M)\not\in M\)이 된다. 이제 \(M\)에 greatest element \(a=p(M)\)를 추가하면, 우리는 또 다른 well-ordered set \(M'=M\cup\{a\}\) (\(S_a=M\))를 얻는다. \(S_a=M\in\mathcal{S}\)이고 \(p(S_a)=a\)이므로, \(M'\)은 \(\mathcal{M}\)의 원소가 되어 \(M\)의 최대성에 모순이다. 따라서 명제의 성질 2도 성립한다.
정리 1의 증명
\(\mathcal{S}=\mathcal{P}(A)\setminus\{A\}\)라 하자. 또, 함수 \(p:\mathcal{S}\rightarrow A\)의 값 \(P(X)\)를 \(A\setminus X\)의 어떤 원소로 정의하자. (즉, \(P\)는 choice function이다.) 그럼 \(P(X)\not\in X\)이다. 이제 앞선 보조정리에 의해 어떤 well-ordered subset \(M\subseteq A\)가 존재하여 위 보조정리의 1과 2를 만족한다. 특히, \(M\not\in\mathcal{S}\)인데, 이를 만족할 수 있는 유일한 \(M\)은 \(A\) 뿐이다.
이제 가장 범용적으로 쓰이는 선택공리의 동치인 Zorn’s lemma를 소개할 차례다. 우선 다음을 정의하자.
정의 3 Ordered set \(A\)가 inductive하다는 것은 임의의 totally ordered subset이 upper bound를 갖는 것이다.
Inductive set은 저자에 따라 전혀 다른 개념을 뜻하기도 하므로 주의가 필요하다. Totally ordered subset은 chain이라 부르기도 한다.
정리 4 (Zorn’s lemma) 임의의 inductive set은 maximal element를 갖는다.
모든 well-ordered set은 totally ordered set이기도 하므로, 만일 우리가 다음의 정리를 증명할 수 있다면 위의 정리는 자명하다.
명제 5 모든 well-ordered subset이 bounded above인 ordered set \(A\)는 maximal element를 갖는다.
증명
만약 \(v\)가 \(X\subseteq A\)의 upper bound이고 \(v\not\in X\)라면 \(v\in A\)를 \(X\)의 strict upper bound라 부르자.
이제 \(\mathcal{S}\)를 \(A\)의 부분집합 중 strict upper bound를 갖는 것들만 모아둔 집합이라 하고, \(p:\mathcal{S}\rightarrow A\)가 strict upper bound를 뽑아오는 함수라고 하자. 즉 모든 \(S\)에 대하여 \(p(S)\)는 \(S\)의 strict upper bound이다. \(p(S)\not\in S\)이므로, 우리는 §정렬집합의 성질들, ⁋보조정리 5에 의해 well-ordered subset \(M\)을 얻는다. 또, 이 well-ordering은 \(A\)의 order relation를 \(M\) 위로 제한한 것과 같다. 만일 \(x<y\)가 \(M\) 안에서 성립한다고 하면 이는 \(x\in S_y\)와 동치인데 (\(S_y\)는 \(M\)에서의 segment), \(p(S_y)=y\)이면 \(y\)가 \(S_y\)의 strict upper bound가 된다. (여기서의 \(S_y\)는 \(M\)의 부분집합이므로, segment가 아니지만 그냥 부분집합으로서 strict upper bound \(y\)를 갖는다.) 특히 \(x\in S_y\)로부터, \(x<y\)가 \(A\)에서도 성립한다. \(M\)은 이제 well-ordered이므로, 가정에 의해 \(M\)은 upper bound \(m\)을 갖는다. 그런데 정의에 의해 \(M\)은 strict upper bound를 갖지 못하므로, \(m\in M\)이고, 만일 어떤 \(m'\)이 \(m\leq m'\)을 만족한다면 \(m=m'\)이 된다. 그렇지 않다면 \(m'\)이 \(M\)의 strict upper bound가 되므로.
완결성을 위해 간단하게 세 가지 명제, 그러니까 선택공리, Zermelo’s theorem, Zorn’s lemma가 동치임을 보이자. 우리는 Zermelo’s theorem과 Zorn’s lemma를 보일 때 선택공리를 썼으므로, 이제 Zermelo’s theorem과 Zorn’s lemma 각각을 이용해서 choice function을 만들어내면 된다.
우선 Zermelo’s theorem을 가정한다면 모든 집합은 well-ordered될 수 있으므로, 어떠한 \(S\in\mathcal{P}(A)\setminus \{\emptyset\}\)에 대해서도 least element가 존재한다. 이제 \(p(S)\)를 \(S\)의 least element로 정의하면 \(p\)가 원하는 choice function이다.
이제 Zorn’s lemma를 가정하고, 집합 \(A\)의 choice function을 만들자. 우선 \(A\)의 어떤 부분집합 \(X\) 위에 정의된 choice function들을 모아 이를 \(\mathcal{F}\)라 하자. 최소한 \(X=\{a\}\) 위에서는 choice function이 존재하므로 \(\mathcal{F}\)는 공집합이 아니다. 이제 \(\mathcal{C}\)의 각 원소들은 집합이므로, \(\subseteq\)에 의해 순서가 주어진다.
이제 \(\mathcal{F}\)의 totally ordered subset \(\mathcal{C}\)가 주어졌다 하자. 그럼 \(\bigcup_{X\in\mathcal{C}} F_X\)는 정의역 \(\mathcal{P}(\bigcup_{X\in\mathcal{C}} X)\)를 갖는 함수이므로, 이 함수들의 모임의 upper bound가 된다. 따라서 Zorn’s lemma에 의해 어떤 maximal element가 존재한다. 이를 \(F\)라 하고 \(\mathcal{P}(B)\)를 정의역이라 하자. 만일 \(x\in A\setminus B\)라면, \(B\)에 \(x\)를 추가하고 \(\tilde{f}\)를
\[\tilde{f}(X)=\begin{cases}f(X)&\text{if }x\not\in X\\ x&\text{if }x\in X\end{cases}\]로 정의함으로써 \(F\)를 확장하는 choice function \(\tilde{f}\)를 얻는다. 이는 \(F\)의 maximality에 모순이므로 \(A\setminus B=\emptyset\), 즉 \(F\)는 \(A\)의 choice function이다.
참고문헌
[HJJ] K. Hrbacek, T.J. Jeck, and T. Jech. Introduction to Set Theory. Lecture Notes in Pure and Applied Mathematics. M. Dekker, 1978.
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.
댓글남기기