9장에서 ZF에 선택공리를 더한 체계를 ZFC라고 정의하였다. 선택공리는 유한한 선택에서는 드러나지 않지만, 서로 아무 관련이 없고 무한히 많으며 공집합이 아닌 집합에서 원소를 하나씩 동시에 골라야 할 때 핵심적인 역할을 한다. 이 장에서는 공리 9.12의 여러 동치형태와 대표적인 응용을 살펴보고, 선택공리보다 약한 선택원리도 구분한다.
괴델은 ZF가 무모순이라면 ZFC도 무모순임을 보였고, 코언은 ZF가 무모순이라면 \(\mathrm{ZF}+\neg\mathrm{AC}\)도 무모순임을 보였다. 따라서 ZF의 무모순성을 전제로 하면 선택공리는 ZF로부터 증명할 수도 반증할 수도 없다.
1. 선택 공리의 의미
공리 9.12에서 정의한 선택함수를 다시 살펴보자. 공집합을 원소로 갖지 않는 집합족 \(\mathcal F\)에 대하여 함수 \[f\colon\mathcal F\to\bigcup\mathcal F\] 가 모든 \(A\in\mathcal F\)에 대해 \(f(A)\in A\)를 만족시키면 \(f\)를 \(\mathcal F\)의 선택함수라고 한다.
직관적으로 선택함수는 각 집합에서 원소를 하나씩 선택하는 함수이다. 예를 들어 \[\mathcal F=\{\{1,2\},\{3,4,5\},\{6\}\}\] 에 대해서는 선택함수가 \(2\cdot3\cdot1=6\)개 존재한다.
공집합이 아닌 집합이 유한 개뿐이면 선택함수의 존재는 ZF에서 수학적 귀납법을 사용하여 증명할 수 있다. 선택공리가 필요한 지점은 임의의 크기를 갖는 집합족에 대해 이러한 선택을 한꺼번에 수행할 때이다.
선택공리는 다음 두 형태로도 나타낼 수 있다.
- 공집합을 원소로 갖지 않는 임의의 집합족 \(\mathcal F\)에는 선택함수가 존재한다.
- 각 \(i\in I\)에 대하여 \(A_i\ne\varnothing\)인 집합족 \(\{A_i\}_{i\in I}\)에 대하여 \[\prod_{i\in I}A_i\ne\varnothing\] 이다.
둘째 표현에서 곱집합의 원소는 각 \(i\in I\)에 대하여 \(f(i)\in A_i\)를 만족시키는 함수이므로 두 표현은 같은 내용을 말한다.
문제 10.1. \(I=\{0,1,2\}\)이고 \[ A_0=\{0,1\},\quad A_1=\{a,b,c\},\quad A_2=\{\ast\} \] 라 하자.
- \(\displaystyle\prod_{i\in I}A_i\)의 원소를 모두 나열하시오.
- 이 집합족의 선택함수의 개수를 구하시오.
- 곱집합의 원소와 선택함수가 어떻게 대응하는지 설명하시오.
문제 10.2. 각 \(n\in\mathbb N\)에 대하여 \(A_n=\{n,n+1\}\)이라 하자.
- \(f(A_n)=n\)이라고 정의하면 \(\{A_n\}_{n\in\mathbb N}\)의 선택함수가 됨을 보이시오.
- 이 예에서 선택함수의 존재를 보이기 위하여 가산 선택 공리를 따로 사용할 필요가 없는 이유를 설명하시오.
2. 선택 공리와 동치인 명제들
ZF 하에서 선택공리와 동치인 명제는 매우 많다. 여기서는 정렬 정리, 초른의 보조정리, 하우스도르프의 극대 원리를 살펴본다.
집합 \(A\) 위에 어떤 정렬순서를 줄 수 있으면 \(A\)를 정렬 가능(well-orderable)하다고 한다. 정렬순서의 정의는 정의 8.1을 따른다.
부분순서집합 \((P,\leq)\)의 부분집합 \(C\subseteq P\)가 임의의 두 원소끼리 비교 가능하면 \(C\)를 사슬(chain)이라고 한다. 원소 \(m\in P\)에 대하여 \(m<x\)인 \(x\in P\)가 없으면 \(m\)을 극대원소(maximal element)라고 한다. 극대원소는 모든 원소보다 큰 최대원소와 구별해야 한다.
문제 10.3. \(P=\{\varnothing,\{1\},\{2\}\}\)에 포함관계로 부분순서를 주자.
- \(P\)의 원소 가운데 서로 비교 가능한 두 원소를 모두 찾으시오.
- \(P\)의 포함관계에 대하여 극대인 사슬을 모두 찾으시오.
- \(P\)의 극대원소를 모두 찾으시오. 최대원소도 존재하는가?
- \(P\)의 모든 사슬이 \(P\) 안에서 상계를 가짐을 확인하고, 초른의 보조정리의 결론과 비교하시오.
정리 10.1. (선택공리의 대표적인 동치형태)
ZF 위에서 다음 명제들은 서로 동치이다.
- 선택공리.
- 정렬 정리(Well-Ordering Theorem): 모든 집합은 정렬 가능하다.
- 초른의 보조정리(Zorn's Lemma): 공집합이 아닌 부분순서집합 \(P\)에서 모든 사슬이 \(P\) 안의 상계를 가지면 \(P\)에는 극대원소가 존재한다.
- 하우스도르프의 극대 원리(Hausdorff maximal principle): 모든 부분순서집합은 포함관계에 대하여 극대인 사슬을 가진다.
완전한 동치 증명은 초한재귀와 하르톡스 정리를 사용하는 표준적인 집합론 논증을 필요로 하므로 여기서는 증명 없이 사용한다. 다만 몇 방향은 쉽게 확인할 수 있다.
정렬 정리를 가정하면 \(\bigcup\mathcal F\)에 정렬순서를 하나 줄 수 있다. 공집합이 아닌 각 \(A\in\mathcal F\)에서 이 정렬순서에 대한 최소원소를 택하면 되므로 선택공리를 얻는다.
문제 10.4. 정렬 정리를 가정하고, 공집합을 원소로 갖지 않는 집합족 \(\mathcal F\)를 생각하자. \(\bigcup\mathcal F\)에 정렬순서 \(\preceq\)를 하나 주고 \[ f(A)=\text{\(A\)의 \(\preceq\)-최소원소}\quad(A\in\mathcal F) \] 로 정의하자.
- \(f\)가 잘 정의된 함수임을 보이시오.
- \(f\)가 \(\mathcal F\)의 선택함수임을 보이시오.
- 각 \(A\in\mathcal F\)를 따로 정렬할 필요 없이 \(\bigcup\mathcal F\) 하나만 정렬해도 충분한 이유를 설명하시오.
초른의 보조정리를 가정하자. 집합족 \(\mathcal F\)의 부분 선택함수들을 정의역의 포함과 함수의 확장관계로 순서화한다. 사슬에 속한 부분 선택함수들의 합집합은 다시 부분 선택함수이므로 사슬의 상계가 된다. 초른의 보조정리로 극대 부분 선택함수 \(g\)를 얻는다. 만약 \(\operatorname{dom}(g)\ne\mathcal F\)이면 \(A\in\mathcal F\setminus\operatorname{dom}(g)\)와 \(a\in A\)를 하나 택하여 \(g\)를 \(A\)까지 확장할 수 있으므로 극대성에 모순이다. 따라서 \(g\)는 \(\mathcal F\) 전체의 선택함수이다.
문제 10.5. 공집합을 원소로 갖지 않는 집합족 \(\mathcal F\)에 대하여 \(P\)를 \(\mathcal F\)의 모든 부분 선택함수의 집합이라 하자. 즉 \(g\in P\)이면 \(\operatorname{dom}(g)\subseteq\mathcal F\)이고 모든 \(A\in\operatorname{dom}(g)\)에 대하여 \(g(A)\in A\)이다. 함수의 확장관계로 \(P\)를 순서화한다.
- 공함수가 \(P\)에 속함을 보이시오.
- \(P\)의 사슬 \(\mathcal C\)에 대하여 \(h=\bigcup\mathcal C\)가 함수임을 보이시오.
- \(h\)가 다시 부분 선택함수이며 \(\mathcal C\)의 상계임을 보이시오.
- 초른의 보조정리로 얻은 극대 부분 선택함수의 정의역이 반드시 \(\mathcal F\) 전체임을 증명하시오.
하우스도르프의 극대 원리를 가정하고 초른의 보조정리의 가정을 만족시키는 부분순서집합 \(P\)를 생각하자. 극대 사슬 \(C\)를 택하고 그 상계를 \(u\in P\)라 하자. \(C\cup\{u\}\)도 사슬이므로 극대성에서 \(u\in C\)이다. 만약 \(u<v\)인 \(v\in P\)가 존재하면 \(C\cup\{v\}\)도 사슬이 되어 다시 모순이다. 따라서 \(u\)는 \(P\)의 극대원소이다.
문제 10.6. 하우스도르프의 극대 원리를 자신의 말로 서술하고, 위 논증을 완성하여 하우스도르프의 극대 원리로부터 초른의 보조정리가 따름을 증명하시오.
3. 무한기수 산술에의 적용
정렬 정리에 의해 선택공리 아래에서는 모든 집합을 어떤 초기서수와 대등하게 놓을 수 있다. 이를 이용하면 7장에서 증명 없이 사용한 정리 7.10을 증명할 수 있다.
먼저 모든 무한기수 \(\kappa\)에 대하여 \[\kappa\cdot\kappa=\kappa\] 임을 보이자. 선택공리에 의해 \(\kappa\)를 무한 초기서수와 동일시한다. 무한 초기서수에 대한 초한귀납법을 사용한다. \(\kappa\times\kappa\)에 다음 순서를 준다. 두 순서쌍 \((\alpha,\beta)\)와 \((\gamma,\delta)\)에 대하여 먼저 \[\max\{\alpha,\beta\}\quad\text{와}\quad\max\{\gamma,\delta\}\] 를 비교하고, 같으면 첫째 성분, 다시 같으면 둘째 성분을 비교한다. 이 순서는 \(\kappa\times\kappa\)의 정렬순서이다.
\((\alpha,\beta)\)보다 앞에 오는 순서쌍들은 \(\theta=\max\{\alpha,\beta\}\)라 할 때 \((\theta+1)\times(\theta+1)\) 안에 들어 있다. \(|\theta+1|<\kappa\)이고 귀납가정에 의해 이 집합의 기수도 \(\kappa\)보다 작다. 따라서 위 정렬순서의 모든 진절편의 기수는 \(\kappa\)보다 작다. 이 정렬집합의 순서유형을 \(\eta\)라 하면 \(\eta>\kappa\)일 경우 \(\kappa\)에서의 절편이 기수 \(\kappa\)를 가져 모순이므로 \(\eta\leq\kappa\)이다. 한편 \(\alpha\mapsto(\alpha,0)\)은 \(\kappa\to\kappa\times\kappa\)인 일대일함수이므로 칸토어-베른슈타인 정리에 의해 \(\kappa\cdot\kappa=\kappa\)이다.
문제 10.7. 본문에서 \(\kappa\times\kappa\)에 준 정렬순서를 \(\omega\times\omega\)에 적용하자. 즉 먼저 두 좌표의 최댓값을 비교하고, 같으면 첫째 좌표, 다시 같으면 둘째 좌표를 비교한다.
- 이 순서에서 처음 아홉 개의 원소를 차례로 쓰시오.
- \((m,n)\)보다 앞에 오는 원소가 유한 개뿐임을 보이시오.
- 이 정렬순서의 순서유형이 \(\omega\)임을 설명하고, 따라서 \(\omega\times\omega\sim\omega\)임을 다시 확인하시오.
이제 \(\kappa\), \(\lambda\)가 무한기수이고 \(\mu=\max\{\kappa,\lambda\}\)라 하자. 한쪽 기수가 \(\mu\)이므로 \[\mu\leq\kappa+\lambda\leq\mu+\mu\leq\mu\cdot\mu=\mu\] 이고, \[\mu\leq\kappa\cdot\lambda\leq\mu\cdot\mu=\mu\] 이다. 따라서 \[\kappa+\lambda=\kappa\cdot\lambda=\mu\] 를 얻는다.
정리 10.2. (타르스키의 기수제곱 정리)
ZF 하에서 다음 두 명제는 동치이다.
- 선택공리.
- 모든 무한집합 \(A\)에 대하여 \(A\times A\sim A\)이다.
정리 7.10에서 첫째 명제로부터 둘째 명제가 따르는 것은 이미 보았다. 역방향의 타르스키 정리는 이 책의 범위를 넘어가므로 증명 없이 사용한다. 따라서 문제 7.10의 명제를 모든 무한집합에 대하여 선택공리 없이 증명할 수는 없다.
4. 선택 공리를 사용하는 정리들
선택공리는 여러 분야의 존재정리를 초른의 보조정리나 정렬 정리의 형태로 증명할 때 자주 사용된다.
(1) 극대 아이디얼
정리 10.3. (극대 아이디얼의 존재)
영환이 아닌 단위원을 갖는 가환환은 극대 아이디얼을 가진다.
증명 환 \(R\)의 진아이디얼들의 집합을 포함관계로 순서화한다. 진아이디얼들의 사슬 \(\mathcal C\)에 대하여 \(\bigcup\mathcal C\)는 아이디얼이다. 만약 \(1\in\bigcup\mathcal C\)이면 어떤 \(I\in\mathcal C\)에 \(1\in I\)이므로 \(I=R\)가 되어 모순이다. 따라서 \(\bigcup\mathcal C\)도 진아이디얼이며 사슬의 상계이다. 초른의 보조정리에 의해 극대인 진아이디얼이 존재한다.
(2) 벡터공간의 기저
정리 10.4. (벡터공간의 기저)
모든 벡터공간은 기저를 가진다.
증명 벡터공간 \(V\)의 일차독립 부분집합들을 포함관계로 순서화한다. 사슬 \(\mathcal C\)의 합집합 \(L=\bigcup\mathcal C\)가 일차독립임을 보이자. \(L\)의 유한한 원소들이 선형관계를 만족시키면, 사슬의 성질 때문에 그 유한한 원소들을 모두 포함하는 하나의 \(C\in\mathcal C\)가 존재한다. \(C\)가 일차독립이므로 모든 계수가 \(0\)이다. 따라서 \(L\)은 사슬의 상계이다.
초른의 보조정리로 극대 일차독립 집합 \(B\)를 얻는다. 만약 \(\operatorname{span}(B)\ne V\)이면 \(v\in V\setminus\operatorname{span}(B)\)를 택할 수 있고 \(B\cup\{v\}\)도 일차독립이므로 극대성에 모순이다. 따라서 \(B\)는 \(V\)의 기저이다.
문제 10.8. \(V=\mathbb R^3\)이고 \[ L=\{(1,0,0),(1,1,0)\} \] 라 하자.
- \(L\)이 일차독립임을 확인하시오.
- \(v\in V\)를 하나 찾아 \(L\cup\{v\}\)가 \(V\)의 기저가 되게 하시오.
- 유한차원에서는 이러한 과정을 유한 번 반복하여 기저를 얻을 수 있음을 설명하시오.
- 본문의 일반적인 기저 존재 증명에서 초른의 보조정리가 필요한 지점이 무엇인지 설명하시오.
(3) 티호노프 정리
정리 10.5. (티호노프 정리)
컴팩트 공간들의 임의의 곱은 곱위상에서 컴팩트이다.
ZF 하에서 이 일반형의 티호노프 정리는 선택공리와 동치이다. 한 표준적인 증명은 필터를 극대필터로 확장한 뒤 각 좌표공간에서 수렴점을 얻고, 그 수렴점들을 좌표별로 선택하여 곱공간의 점을 구성한다. 이 과정의 상세한 위상수학적 증명은 이 책의 범위를 넘어가므로 생략한다. 컴팩트 하우스도르프 공간으로 제한한 티호노프 정리는 전체 선택공리보다 약한 불 소아이디얼 정리(Boolean prime ideal theorem)와 동치이므로 두 형태를 구별해야 한다.
5. 선택공리를 사용하여 얻는 비구성적 결과
선택공리는 매우 강한 존재정리를 제공하지만, 선택된 대상을 명시적으로 기술하는 방법을 주지는 않는다. 다음 두 결과가 대표적이다.
(1) 비가측 집합의 존재
정리 10.6. (비탈리 집합)
선택공리를 가정하면 \([0,1]\)의 르베그 비가측 부분집합이 존재한다.
증명 개요 \([0,1]\)에서 \[x\sim y\quad\Longleftrightarrow\quad x-y\in\mathbb Q\] 로 두면 동치관계가 된다. 선택공리를 사용하여 각 동치류에서 대표원소를 하나씩 택한 집합 \(V\subseteq[0,1]\)를 만든다. \(q\in\mathbb Q\cap[-1,1]\)에 대한 평행이동 \(V+q\)들은 서로소이고, \[[0,1]\subseteq\bigcup_{q\in\mathbb Q\cap[-1,1]}(V+q)\subseteq[-1,2]\] 이다.
\(V\)가 가측이라고 하자. 측도의 평행이동 불변성 때문에 모든 \(V+q\)는 같은 측도를 갖는다. 그 측도가 \(0\)이면 위 가산합집합도 측도 \(0\)이 되어 \([0,1]\)을 포함할 수 없다. 양수이면 서로소인 가산 개의 평행이동들의 합집합은 무한한 측도를 가져야 하지만 \([-1,2]\) 안에 들어 있어 모순이다. 따라서 \(V\)는 비가측이다.
문제 10.9. \([0,1]\)에서 \(x\sim y\Longleftrightarrow x-y\in\mathbb Q\)로 정의하자.
- \(\sim\)이 동치관계임을 증명하시오.
- 각 동치류에서 대표원소 하나씩을 택한 집합을 \(V\)라 하자. 서로 다른 \(q_1,q_2\in\mathbb Q\cap[-1,1]\)에 대하여 \((V+q_1)\cap(V+q_2)=\varnothing\)임을 증명하시오.
- 모든 \(x\in[0,1]\)이 어떤 \(q\in\mathbb Q\cap[-1,1]\)에 대하여 \(x\in V+q\)를 만족시킴을 보이시오.
(2) 바나흐-타르스키 정리
정리 10.7. (바나흐-타르스키 정리)
선택공리를 가정하면 \(\mathbb R^3\)의 단위구를 유한 개의 서로소인 부분집합으로 분할한 뒤, 각 조각을 회전과 평행이동하여 원래 단위구와 합동인 두 개의 구로 재조립할 수 있다.
증명의 핵심은 \(SO(3)\) 안의 두 회전이 생성하는 자유부분군의 역설적 분해이다. 이 자유군이 구면에 작용할 때 비자명한 안정자를 갖는 예외적인 점들을 먼저 제거하면 남은 각 궤도는 자유군 자체와 일대일로 대응한다. 선택공리를 사용하여 각 궤도에서 대표원소를 하나씩 선택하고, 자유군의 역설적 분해를 각 궤도에 동시에 옮긴다. 예외적인 가산집합을 다시 흡수하고 구면의 분해를 반지름 방향으로 연장하면 단위구의 분해를 얻는다. 세부 구성은 군론과 측도론을 필요로 하므로 여기서는 생략한다.
이 결과는 조각들이 보통의 부피를 갖는 가측집합일 수 없기 때문에 부피의 가산가법성과 모순되지 않는다.
6. 약한 선택원리
선택공리의 일부만을 요구하는 여러 약한 원리가 있다. 이들을 ZF에서 증명되는 사실과 구별해야 한다.
- 유한 선택: 공집합이 아닌 집합 유한 개가 주어졌을 때 선택함수가 존재한다. 이것은 ZF에서 수학적 귀납법을 사용하여 증명된다.
- 가산 선택 공리(Axiom of Countable Choice, \(\mathrm{AC}_\omega\)): 공집합이 아닌 집합들의 가산 집합족에는 선택함수가 존재한다. 이는 ZF에서는 일반적으로 증명되지 않으며 선택공리보다 약하다. 따라서 “공집합이 아닌 가산 개의 집합의 곱은 공집합이 아니다”라는 명제는 선택공리 없이 자동으로 사용할 수 없다.
- 종속 선택 공리(Axiom of Dependent Choice, DC): 공집합이 아닌 집합 \(X\)의 관계 \(R\)이 모든 \(x\in X\)에 대해 어떤 \(y\in X\)와 \(xRy\)를 만족시킨다고 하자. 그러면 임의의 \(x_0\in X\)에 대하여 \(x_nRx_{n+1}\)을 만족시키는 수열 \((x_n)_{n\in\mathbb N}\)이 존재한다. DC는 해석학에서 자주 충분한 선택원리이며 전체 선택공리보다 약하다.
- 유한집합 선택공리(Axiom of Choice for Finite Sets): 공집합이 아닌 유한집합들로 이루어진 임의의 집합족에 선택함수가 존재한다. 이것도 유한한 집합족에 대한 선택과는 다르며 ZF에서 일반적으로 증명되지 않는다.
예를 들어 유한차원 벡터공간에서 유한한 생성집합으로부터 기저를 추출하는 과정은 전체 선택공리를 필요로 하지 않는다. 반면 임의의 벡터공간의 기저 존재는 위에서 본 것처럼 초른의 보조정리를 사용하여 얻는다. 어떤 수학 정리에 어느 정도의 선택원리가 필요한지는 정리마다 별도로 확인해야 한다.
문제 10.10. 다음 상황에서 본문에 소개한 선택원리 가운데 직접 대응하는 것을 찾으시오. 선택공리가 전혀 필요하지 않는 경우에는 그렇게 밝히시오.
- 공집합이 아닌 집합 다섯 개에서 각각 원소 하나를 선택한다.
- 공집합이 아닌 집합들의 가산 집합족에서 각각 원소 하나를 선택한다.
- 공집합이 아닌 유한집합들로 이루어진 임의의 집합족에서 각각 원소 하나를 선택한다.
- 공집합이 아닌 집합 \(X\)의 관계 \(R\)이 모든 \(x\in X\)에 대해 어떤 \(y\in X\)와 \(xRy\)를 만족시킬 때, \(x_nRx_{n+1}\)인 수열을 만든다.
- 아무 제한이 없고 공집합이 아닌 집합들의 임의의 집합족에서 각각 원소 하나를 선택한다.