앞 장까지는 집합을 직관적으로 사용하면서 자연수, 기수, 서수를 구성하였다. 그러나 “어떤 조건을 만족시키는 대상들을 모두 모으면 집합이 된다”고 무제한으로 허용하면 러셀의 역설과 같은 모순이 생긴다. 공리적 집합론에서는 어떤 집합의 존재를 인정할 것인지 공리로 제한하여 이러한 문제를 피한다.
이 부에서는 현대 수학의 표준적인 기초 가운데 하나인 ZFC를 살펴본다. ZFC는 체르멜로-프렝켈 집합론(ZF)에 선택공리를 더한 체계이다. 특히 앞 장에서 사용한 자연수 집합의 존재, 초한재귀, 초기서수의 존재가 어떤 집합 존재 공리와 연결되는지 확인한다.
공리적 집합론(axiomatic set theory)에서는 집합의 존재와 성질을 몇 개의 기본 공리와 공리꼴로 규정한다. 이 장에서는 ZFC를 기준으로 설명한다.
1. 집합과 클래스
ZFC의 일계논리 언어에서 변수는 모두 집합을 나타내며, 기본적인 비논리 기호는 원소관계 \(\in\)이다. 따라서 ZFC 자체에는 “클래스”를 집합과 나란한 새로운 종류의 대상으로 두는 변수가 없다.
그럼에도 설명의 편의를 위하여 다음 용어를 사용한다.
정의 9.1. (클래스와 고유클래스)
논리식 \(\phi(x)\)를 만족시키는 모든 집합을 \[\{x\mid \phi(x)\}\] 와 같이 적고 클래스(class)라고 부른다. 이 표기는 새로운 집합의 존재를 주장하는 것이 아니라, “\(\phi(x)\)를 만족시키는 집합 \(x\)”라는 조건을 줄여 쓴 것이다. 이러한 클래스가 실제로 어떤 집합과 같은 경우에는 그 클래스를 집합이라고 부르고, 어떤 집합과도 같지 않은 경우에는 고유클래스(proper class)라고 부른다.
예를 들어 모든 집합의 클래스 \[V=\{x\mid x=x\}\] 는 고유클래스이다. 만약 \(V\)가 집합이라면 뒤에서 다룰 분리 공리꼴을 \(V\)에 적용하여 \(\{x\in V\mid x\notin x\}\)를 집합으로 만들 수 있고, 러셀의 역설이 생긴다. 모든 서수의 클래스도 8장에서 본 것처럼 고유클래스이다.
클래스를 실제 대상으로 다루는 NBG 같은 공리계도 있지만, 이 책에서는 ZFC를 사용하고 클래스 표기는 위와 같은 메타언어적 약속으로만 사용한다.
2. ZFC 공리계
정의 9.2. (ZFC)
체르멜로-프렝켈 집합론(Zermelo-Fraenkel set theory)에 선택공리(Axiom of Choice)를 추가한 체계를 ZFC라고 부른다.
아래의 식에서 \(\subseteq\), \(\varnothing\), 함수 등의 표기는 모두 \(\in\)과 \(=\)만을 사용하여 풀어 쓸 수 있는 약식 표기이다.
분리와 치환은 각각 하나의 공리가 아니라, 허용되는 논리식마다 하나의 공리를 갖는 공리꼴(axiom schema)이다. 또한 아래에서는 교육적 편의를 위하여 공집합의 존재를 별도로 적는다. 이것은 통상적인 ZF의 다른 공리들로부터도 유도할 수 있으므로 독립적인 공리로 반드시 넣어야 하는 것은 아니다.
공리 9.3. (외연 공리)
두 집합이 같은 원소를 가지면 두 집합은 같다. \[\forall A\,\forall B\, \bigl(\forall x\,(x\in A\leftrightarrow x\in B)\to A=B\bigr).\]
공리 9.4. (공집합의 존재)
원소를 하나도 갖지 않는 집합이 존재한다. \[\exists A\,\forall x\,(x\notin A).\] 외연 공리에 의해 이러한 집합은 유일하며 이를 \(\varnothing\)으로 나타낸다.
공리 9.5. (짝 공리)
임의의 두 집합 \(x\), \(y\)에 대하여 정확히 \(x\)와 \(y\)를 원소로 갖는 집합이 존재한다. \[\forall x\,\forall y\,\exists A\,\forall z\, \bigl(z\in A\leftrightarrow(z=x\vee z=y)\bigr).\] 이 집합을 \(\{x,y\}\)로 나타낸다. 특히 \(x=y\)이면 단원소 집합 \(\{x\}\)를 얻는다.
공리 9.6. (합집합 공리)
집합 \(A\)에 대하여 \(A\)의 원소들의 원소를 모두 모은 집합이 존재한다. \[\forall A\,\exists B\,\forall x\, \bigl(x\in B\leftrightarrow\exists y\,(y\in A\wedge x\in y)\bigr).\] 이 집합을 \(\bigcup A\)로 나타낸다.
공리 9.7. (멱집합 공리)
집합 \(A\)에 대하여 \(A\)의 모든 부분집합을 원소로 갖는 집합이 존재한다. \[\forall A\,\exists B\,\forall x\,(x\in B\leftrightarrow x\subseteq A).\] 이 집합은 앞에서 정의한 멱집합 \(\mathcal P(A)\)이다.
문제 9.1. 집합 \(A=\{0,1\}\)과 임의의 집합 \(B\)에 대하여 다음 물음에 답하시오.
- 짝 공리와 합집합 공리를 사용하여 \(A\cup B\)의 존재를 설명하시오.
- \(\mathcal P(A)\)를 구하시오.
- \(\bigcup\mathcal P(A)\)를 구하시오.
- \(\mathcal P(A\cup B)\)의 존재를 보장하기 위해 어떤 공리들을 차례로 사용할 수 있는지 설명하시오.
공리 9.8. (무한 공리)
귀납적 집합이 존재한다. 즉, \[\exists A\, \bigl(\varnothing\in A\wedge \forall x\in A\,(x\cup\{x\}\in A)\bigr).\]
공리 9.8은 6장에서 가정했던 귀납적 집합의 존재를 보장한다. 귀납적 집합 하나를 \(I\)라 하면 멱집합 공리와 아래의 분리 공리꼴을 이용하여 \(\mathcal P(I)\) 안의 귀납적 부분집합들을 모을 수 있고, 그들의 교집합으로 가장 작은 귀납적 집합 \(\omega=\mathbb N\)을 얻는다.
문제 9.2. \(I\)가 무한 공리에서 보장하는 귀납적 집합이라고 하자.
- \(0=\varnothing\in I\)임을 확인하시오.
- \(1=\{0\}\), \(2=\{0,1\}\), \(3=\{0,1,2\}\)가 차례로 \(I\)에 속함을 보이시오.
- 일반적으로 모든 자연수 \(n\)이 \(I\)에 속함을 보일 때 어떤 원리를 사용하는지 설명하시오.
공리 9.9. (분리 공리꼴)
집합 \(A\)와 논리식 \(\phi(x,\vec p)\)가 주어졌을 때, \(A\)의 원소 중 \(\phi\)를 만족시키는 것들로 이루어진 부분집합이 존재한다. 즉 각 논리식 \(\phi\)에 대하여 \[\forall A\,\exists B\,\forall x\, \bigl(x\in B\leftrightarrow(x\in A\wedge\phi(x,\vec p))\bigr)\] 라는 공리를 둔다. 여기서 \(\vec p\)는 매개변수들이며 \(B\)는 \(\phi\)에 자유변수로 나타나지 않는다고 가정한다.
분리 공리꼴의 핵심은 이미 존재하는 집합 \(A\) 안에서만 원소를 골라 낸다는 점이다. 따라서 “조건을 만족시키는 모든 대상의 집합”을 무제한으로 만드는 소박한 분류 원리를 허용하지 않는다.
문제 9.3. \(A=6=\{0,1,2,3,4,5\}\)라 하자. 분리 공리꼴을 사용하여 다음 집합이 존재함을 설명하고, 각 집합을 구하시오.
- \(B=\{x\in A\mid x\in3\}\)
- \(C=\{x\in A\mid3\in x\}\)
- \(D=\{x\in A\mid x=0\vee x=5\}\)
공리 9.10. (치환 공리꼴)
논리식 \(\psi(x,y,\vec p)\)가 집합 \(A\)의 각 \(x\)에 대하여 유일한 \(y\)를 정한다고 하자. 그러면 그 \(y\)들을 모두 모은 집합이 존재한다. 즉 각 논리식 \(\psi\)에 대하여 \[ \forall A\, \left( \forall x\in A\,\exists!y\,\psi(x,y,\vec p) \to \exists B\,\forall y\, \bigl(y\in B\leftrightarrow\exists x\in A\,\psi(x,y,\vec p)\bigr) \right). \]
치환 공리꼴은 이미 집합으로 주어진 함수의 치역만을 만들기 위해 필요한 것이 아니다. 집합을 정의 가능한 규칙에 따라 변환했을 때 그 값들의 모임이 다시 집합임을 보장하는 것이 핵심이다. 특히 8장의 초한재귀에서 단계별로 만들어지는 값들을 하나의 집합으로 모으는 데 중요한 역할을 한다.
공리 9.11. (정칙성 공리)
공집합이 아닌 모든 집합 \(A\)에는 \(A\)와 서로소인 원소가 존재한다. \[\forall A\, \bigl(A\ne\varnothing\to\exists x\in A\,(x\cap A=\varnothing)\bigr).\]
정칙성 공리로부터 \(x\in x\)인 집합은 존재하지 않으며, 집합으로 주어진 무한 하강열 \[x_0\ni x_1\ni x_2\ni\cdots\] 도 존재할 수 없다.
문제 9.4. 정칙성 공리에 관하여 다음 물음에 답하시오.
- \(A=\{0,1,2\}\)에서 \(x\cap A=\varnothing\)을 만족시키는 \(x\in A\)를 모두 구하시오.
- 두 집합 \(x\), \(y\)가 동시에 \(x\in y\)와 \(y\in x\)를 만족시킬 수 없음을 정칙성 공리로 증명하시오.
- 특히 \(x\in x\)인 집합이 존재할 수 없음을 설명하시오.
공리 9.12. (선택공리)
\(F\)가 공집합이 아닌 집합들로 이루어진 집합이라고 하자. 그러면 정의역이 \(F\)이고 각 \(A\in F\)에 대하여 \(f(A)\in A\)를 만족시키는 함수 \(f\)가 존재한다. 앞의 약식 표기를 사용하면 \[ \forall F\left( \forall A\in F\,(A\ne\varnothing) \to \exists f\bigl(\operatorname{dom}(f)=F\wedge \forall A\in F\,(f(A)\in A)\bigr) \right) \] 로 나타낼 수 있다.
이러한 \(f\)를 선택함수(choice function)라고 부른다. 선택공리는 ZF로부터 증명되지 않으며 그 부정도 ZF로부터 증명되지 않는다. 정확히 말하면 ZF가 무모순이라고 가정할 때 ZFC와 \(\mathrm{ZF}+\neg\mathrm{AC}\)도 각각 무모순이라는 상대적 무모순성 결과가 알려져 있다. 선택공리와 여러 동치명제는 다음 장에서 자세히 다룬다.
문제 9.5. \(F=\bigl\{\{0,1\},\{2,3,4\},\{\varnothing\}\bigr\}\)라고 하자.
- \(F\) 위의 선택함수 하나를 구체적으로 쓰시오.
- \(F\) 위의 선택함수는 모두 몇 개인지 구하시오.
- 이 예에서는 선택공리를 따로 가정하지 않아도 선택함수를 직접 만들 수 있는 이유를 설명하시오.
3. 집합 구성의 예
ZFC 공리를 사용하여 앞에서 직관적으로 사용해 온 대상들이 실제 집합으로 구성됨을 확인하자.
(1) 순서쌍의 구성
쿠라토프스키(Kuratowski) 정의에 따라 \[(a,b)=\{\{a\},\{a,b\}\}\] 로 둔다. 짝 공리를 두 번 사용하면 이 집합의 존재를 얻는다. 이 정의는 순서쌍의 기본 성질 \[(a,b)=(c,d)\quad\Longleftrightarrow\quad a=c\text{이고 }b=d\] 을 만족시킨다.
문제 9.6. \(0=\varnothing\), \(1=\{0\}\)이라 하자. 쿠라토프스키 정의를 사용하여 다음 순서쌍을 실제 집합으로 나타내시오.
- \((0,0)\)
- \((0,1)\)
- \((1,0)\)
또한 \((0,1)\ne(1,0)\)임을 직접 확인하시오.
문제 9.7. 순서쌍의 성질 \[(a,b)=(c,d)\quad\Longleftrightarrow\quad a=c\text{이고 }b=d\] 를 증명하시오.
문제 9.8. \(3\)-순서쌍을 \[(a,b,c)=((a,b),c)\] 로 정의하고, \[(a,b,c)=(a',b',c')\quad\Longleftrightarrow\quad a=a',\ b=b',\ c=c'\] 임을 증명하시오. 또한 같은 방법으로 유한 \(n\)-순서쌍을 재귀적으로 정의하는 방법을 설명하시오.
이 정의는 3장에서 사용한 \(n\)-순서쌍을 실제 집합으로 부호화하는 한 방법이다. 괄호를 치는 방식에 따라 얻는 집합 자체는 달라질 수 있지만, 성분을 보존하는 자연스러운 일대일대응이 있다.
(2) 데카르트 곱의 구성
\(a\in A\), \(b\in B\)이면 쿠라토프스키 순서쌍에 대하여 \[(a,b)\subseteq\mathcal P(A\cup B),\quad (a,b)\in\mathcal P(\mathcal P(A\cup B))\] 이다. 따라서 \[A\times B =\{p\in\mathcal P(\mathcal P(A\cup B))\mid \exists a\in A\,\exists b\in B\,(p=(a,b))\}\] 로 쓸 수 있다. \(A\cup B\)는 짝 공리와 합집합 공리로, 그 두 번의 멱집합은 멱집합 공리로 만들 수 있고, 마지막 부분집합은 분리 공리꼴로 얻는다. 따라서 \(A\times B\)는 집합이다.
(3) 관계와 함수의 구성
관계 \(R\)은 \(A\times B\)의 부분집합이므로 멱집합 공리에 의해 집합으로 존재한다. 함수의 그래프도 특별한 관계이므로 집합이다.
4장에서 이 책의 함수 \(f\colon A\to B\)는 정의역 \(A\), 공역 \(B\), 대응 관계를 함께 지정한 것으로 정의하였다. 이 세 자료 자체를 하나의 집합으로 부호화하고 싶다면 앞의 순서쌍 구성을 반복하여 예를 들어 \[(A,B,G_f)=((A,B),G_f)\] 와 같은 \(3\)-순서쌍으로 나타낼 수 있다. 여기서 \(G_f\subseteq A\times B\)는 \[\forall a\in A\,\exists!b\in B\,((a,b)\in G_f)\] 를 만족시키는 함수의 그래프이다.
(4) 초기서수의 존재
정리 9.13. (초기서수의 존재)
집합 \(A\)가 정렬 가능하면 \(A\)와 대등한 초기서수가 정확히 하나 존재한다.
증명 \(A\) 위의 모든 이항관계는 \(\mathcal P(A\times A)\)의 원소이므로, \(A\)를 정렬시키는 관계들의 모임 \[\mathcal W=\{R\in\mathcal P(A\times A)\mid R\text{는 }A\text{의 정렬순서}\}\] 은 분리 공리꼴에 의해 집합이다. \(A\)가 정렬 가능하므로 \(\mathcal W\ne\varnothing\)이다.
정리 8.6에 따라 각 \(R\in\mathcal W\)에는 \((A,R)\)과 순서동형인 유일한 서수 \(\alpha_R\)가 대응한다. 초한재귀와 치환 공리꼴을 이용하면 \[T=\{\alpha_R\mid R\in\mathcal W\}\] 도 집합이 된다. \(T\)는 공집합이 아닌 서수들의 집합이므로 최소원소 \(\kappa\)를 갖는다. 각 \(\alpha_R\)는 \(A\)와 대등하므로 \(\kappa\sim A\)이다. 만약 \(\beta<\kappa\)이고 \(\beta\sim A\)인 서수 \(\beta\)가 있다면, 일대일대응 \(A\to\beta\)를 이용하여 \(\beta\)의 순서를 \(A\)로 옮겨 \(A\) 위의 정렬순서 \(R\)을 만들 수 있다. 그러면 \(\alpha_R=\beta\)이므로 \(\beta\in T\)가 되어 \(\kappa\)의 최소성에 모순이다. 따라서 \(\kappa\)는 \(A\)와 대등한 초기서수이다. 초기서수의 최소성에서 유일성도 따른다.
따라서 8장에서 사용한 초기서수는 정렬 가능한 집합에 대해서 ZF 안에서 구성할 수 있다. 모든 집합이 정렬 가능하다는 정렬 정리는 선택공리와 동치이므로, 모든 기수를 초기서수로 대표하려면 선택공리가 필요하다.
또한 정리 8.12와 같은 초한재귀의 완전한 집합론적 증명에는 치환 공리꼴이 사용된다. 이 점은 자연수 위의 재귀가 무한 공리 위에서 이루어지는 것을 초한재귀를 사용하여 확장한 것으로 볼 수 있다.
4. 러셀의 역설
소박한 집합론에서 \[\mathcal R=\{x\mid x\notin x\}\] 를 집합이라고 허용하면 \[\mathcal R\in\mathcal R\quad\Longleftrightarrow\quad \mathcal R\notin\mathcal R\] 라는 모순이 생긴다.
ZFC의 분리 공리꼴은 이미 존재하는 집합 안에서만 부분집합을 만들게 하므로 이러한 \(\mathcal R\)의 존재를 허용하지 않는다. 클래스 표기법으로는 \(\mathcal R\)을 말할 수 있지만 이는 고유클래스이다. 더구나 정칙성 공리에 의해 모든 집합 \(x\)에 대하여 \(x\notin x\)이므로, 클래스 \(\mathcal R\)은 사실 모든 집합의 클래스 \(V\)와 같다.
문제 9.9. 집합 \(A\)에 대하여 분리 공리꼴로 \[R_A=\{x\in A\mid x\notin x\}\] 를 정의하자.
- \(R_A\)가 집합임을 설명하시오.
- \(R_A\in A\)라고 가정하면 모순이 생김을 보이시오.
- 따라서 임의의 집합 \(A\)에 대하여 \(R_A\notin A\)임을 보이고, 이것이 러셀의 역설과 모순되지 않는 이유를 설명하시오.
연습문제
문제 9.10. 다음 집합이나 함수를 구성할 때 핵심적으로 사용하는 ZFC의 공리 또는 공리꼴을 각각 말하시오. 필요한 경우 둘 이상의 공리를 적으시오.
- \(\{x,y\}\)
- \(A\cup B\)
- \(\mathcal P(A)\)
- \(\{x\in A\mid\phi(x)\}\)
- 집합 \(A\)의 각 \(x\)에 유일한 \(y\)를 대응시키는 정의 가능한 규칙의 값들을 모은 집합
- 공집합이 아닌 집합들로 이루어진 집합 \(F\)에서 각 원소 하나씩을 고르는 함수
문제 9.11. 외연 공리와 공집합의 존재를 사용하여 공집합이 유일함을 증명하시오.
문제 9.12. 짝 공리와 합집합 공리를 사용하여 세 집합 \(a\), \(b\), \(c\)에 대해 \(\{a,b,c\}\)가 존재함을 보이시오.
문제 9.13. 집합 \(A=\{0,1,2\}\)에 대하여 함수적 성질 \(\psi(x,y)\)를 “\(y=2x\)”라고 하자. 치환 공리꼴로 얻는 상의 집합을 구하시오.
문제 9.14. 집합 \(A\), \(B\)에 대하여 \[A\times B\subseteq\mathcal P(\mathcal P(A\cup B))\] 임을 확인하고, 짝 공리, 합집합 공리, 멱집합 공리, 분리 공리꼴을 사용하여 \(A\times B\)가 집합임을 증명하시오.
문제 9.15. 다음 클래스가 집합인지 고유클래스인지 판단하고 그 이유를 설명하시오.
- 모든 집합의 클래스
- 모든 단원소 집합의 클래스
- 모든 유한집합의 클래스
- 자기 자신을 원소로 갖는 모든 집합의 클래스
문제 9.16. ZFC 공리계에서 다음 집합이 존재함을 증명하시오.
- \(\{1,2,3\}\)
- \(\{\varnothing,\{\varnothing\},\{\{\varnothing\}\}\}\)
- 두 집합 \(A\), \(B\)의 교집합 \(A\cap B\)