2장에서 유한집합과 무한집합을 원소의 개수에 따라 직관적으로 구분하였고, 4장에서는 두 집합 사이의 일대일대응과 대등을 정의하였다. 이 장에서는 이러한 개념을 바탕으로 무한집합의 크기를 비교하고, 가산무한집합과 비가산집합을 구별한다. 특히 서로 다른 크기의 무한집합이 존재함을 살펴본다.
1. 유한집합과 무한집합의 정의
집합 \(A\)가 유한집합(finite set)이라는 것은 \(A=\varnothing\)이거나, 어떤 양의 정수 \(k\)와 서로 다른 원소 \(a_1,\,a_2,\,\ldots,\,a_k\)가 존재하여 \[A=\{a_1,\,a_2,\,\ldots,\,a_k\}\] 로 쓸 수 있다는 뜻이다. 이때 \(k\)를 집합 \(A\)의 원소의 개수 또는 크기라고 하고 \(|A|=k\) 또는 \(n(A)=k\)로 나타낸다. 특히 \(|\varnothing|=0\)으로 둔다.
집합 \(A\)가 유한집합이 아닐 때 \(A\)를 무한집합(infinite set)이라고 부른다. 무한집합의 원소는 유한한 목록을 사용하여 모두 나열할 수 없다. 그러나 뒤에서 볼 가산무한집합처럼 무한한 수열 \[a_0,\,a_1,\,a_2,\,\ldots\] 의 형태로 빠짐없이 나열할 수 있는 무한집합도 있다.
예를 들어 자연수 집합 \(\mathbb{N}=\{0,\,1,\,2,\,3,\,\ldots\}\)과 그 진부분집합인 짝수 자연수의 집합 \(\{0,\,2,\,4,\,6,\,\ldots\}\) 사이에는 \(n\mapsto 2n\)이라는 일대일대응이 존재한다. 이처럼 어떤 무한집합은 자기 진부분집합과 대등하다. 모든 무한집합에 대하여 같은 주장이 성립하는지는 이 장 뒤에서 다시 살펴본다.
2. 일대일 대응과 집합의 크기
4장에서 정의한 것처럼 두 집합 \(A\)와 \(B\) 사이에 일대일대응이 존재할 때 \(A\)와 \(B\)가 대등하다고 한다. 이 장에서는 이를 \[A\sim B\] 로 나타낸다. 문제 4.16에서 보았듯이 대등은 반사적, 대칭적, 추이적이다.
두 집합의 크기를 비교하기 위하여 다음 표기도 사용한다. \(A\)에서 \(B\)로 가는 일대일함수가 존재할 때 \[A\preccurlyeq B\] 로 나타낸다. 또한 \(A\preccurlyeq B\)이지만 \(A\not\sim B\)이면 \(A\prec B\)로 나타낸다. 이 표기는 7장에서 기수를 정의한 뒤 기수의 대소관계와 연결된다.
문제 5.1. 집합 \[A=\{1,2,3\},\quad B=\{a,b,c,d\},\quad C=\{0,2,4\}\] 를 생각하자. 다음 물음에 답하시오.
- \(A\)에서 \(B\)로 가는 일대일함수 하나를 구하시오.
- \(A\)에서 \(C\)로 가는 일대일대응 하나를 구하시오.
- \(A\preccurlyeq B\), \(A\prec B\), \(A\sim C\) 중 참인 것을 모두 찾고 그 이유를 설명하시오.
- \(B\preccurlyeq A\)인지 판정하시오.
다음 결과를 칸토어-베른슈타인 정리(Cantor--Bernstein theorem)라고 부른다.
정리 5.1. (칸토어-베른슈타인 정리)
집합 \(A\), \(B\)에 대하여 \(A\preccurlyeq B\)이고 \(B\preccurlyeq A\)이면 \(A\sim B\)이다.
문제 5.2. 다음 과정을 통해 정리 5.1을 증명하시오.
일대일함수 \(f\colon A\to B\), \(g\colon B\to A\)가 주어졌다고 하고 \[A_0=A\setminus g(B),\quad A_{n+1}=g(f(A_n)),\quad C=\bigcup_{n\in\mathbb{N}}A_n\] 으로 둔다. \(a\in C\)이면 \(h(a)=f(a)\)로 두고, \(a\notin C\)이면 \(g(b)=a\)인 유일한 \(b\in B\)에 대하여 \(h(a)=b\)로 두었을 때 \(h\colon A\to B\)가 일대일대응임을 보인다.
3. 가산무한집합
자연수 집합 \(\mathbb{N}\)과 대등한 무한집합을 가산무한집합(countably infinite set) 또는 가부번집합이라고 부른다. 유한집합과 가산무한집합을 통틀어 가산집합(countable set)이라고 부른다.
가산무한집합의 원소는 \(a_0,\,a_1,\,a_2,\,a_3,\,\ldots\)와 같이 자연수로 번호를 매겨 빠짐없이 나열할 수 있다.
이제 정수 집합 \(\mathbb{Z}\)와 유리수 집합 \(\mathbb{Q}\)가 가산무한집합임을 보이자.
우선 정수 집합 \(\mathbb{Z}\)를 살펴보자. 다음 함수를 생각하자. \[f\colon\mathbb{N}\to\mathbb{Z},\quad f(n)= \begin{cases} \dfrac{n}{2} & (n\text{이 짝수일 때}),\\[10pt] -\dfrac{n+1}{2} & (n\text{이 홀수일 때}). \end{cases}\] 이 함수는 \(\mathbb{N}\)의 원소를 \(0,\,-1,\,1,\,-2,\,2,\,-3,\,3,\,\ldots\) 순서로 \(\mathbb{Z}\)의 원소와 대응시키는 일대일대응이다. 그러므로 \(\mathbb{Z}\)는 가산무한집합이다.
문제 5.3. 위의 함수 \(f\colon\mathbb{N}\to\mathbb{Z}\)에 대하여 다음 물음에 답하시오.
- \(f(0),f(1),\ldots,f(7)\)을 차례로 구하시오.
- 각 \(z\in\mathbb{Z}\)에 대하여 \(f(n)=z\)를 만족시키는 \(n\in\mathbb{N}\)을 \(z\)를 사용하여 나타내시오.
- 함수 \(g\colon\mathbb{Z}\to\mathbb{N}\)을 (2)의 식과 같이 정의하고, \(g\circ f=\operatorname{id}_{\mathbb{N}}\) 및 \(f\circ g=\operatorname{id}_{\mathbb{Z}}\)임을 확인하시오.
다음으로 유리수 집합 \(\mathbb{Q}\)를 살펴보자. \(0\)을 제외한 모든 유리수는 \[\frac{p}{q}\quad(p\in\mathbb{Z}\setminus\{0\},\ q\in\mathbb{N}\setminus\{0\},\ \gcd(|p|,q)=1)\] 의 꼴로 유일하게 나타낼 수 있다. \(0=0/1\)을 먼저 놓고, 나머지 기약분수들을 \(|p|+q\)가 작은 것부터 나열하면 다음과 같은 순서를 얻는다. \[ \begin{aligned} &\frac{0}{1},\\ &\frac{-1}{1},\ \frac{1}{1},\\ &\frac{-1}{2},\ \frac{1}{2},\ \frac{-2}{1},\ \frac{2}{1},\\ &\frac{-1}{3},\ \frac{1}{3},\ \frac{-3}{1},\ \frac{3}{1},\\ &\frac{-1}{4},\ \frac{1}{4},\ \frac{-2}{3},\ \frac{2}{3},\ \frac{-3}{2},\ \frac{3}{2},\ \frac{-4}{1},\ \frac{4}{1},\ \ldots \end{aligned} \] 각 양의 정수 \(m\)에 대하여 \(|p|+q=m\)을 만족시키는 기약분수는 유한 개뿐이고, 모든 유리수는 정확히 한 층에 나타난다. 따라서 각 층을 차례로 이어 붙이면 모든 유리수를 자연수로 번호 매겨 나열할 수 있다. 그러므로 \(\mathbb{Q}\)는 가산무한집합이다.
문제 5.4. 양의 정수 \(k\)를 고정시키고 \[A_k=\mathbb{N}\times\{0,1,\ldots,k-1\}\] 로 두자. 함수 \[\varphi\colon A_k\to\mathbb{N},\quad \varphi(n,r)=kn+r\] 이 일대일대응임을 보이시오. 이를 이용하여 \(A_k\)가 가산무한집합임을 설명하시오.
문제 5.5. 다음 집합이 가산집합임을 보이시오.
- 모든 짝수 정수의 집합
- 모든 홀수 정수의 집합
- \(\mathbb{N}\times\mathbb{N}\)
- 유한 개의 가산집합의 합집합
문제 5.6. 다음을 증명하시오.
- \(A\subseteq\mathbb{N}\)이 무한집합이면 \(A\)는 가산무한집합이다.
- \(B\)가 가산무한집합이면, \(B\)의 진부분집합 중에서 \(B\)와 대등한 것이 존재한다.
- \(C\)가 유한집합이면, \(C\)의 진부분집합 중에서 \(C\)와 대등한 것이 존재하지 않는다.
4. 비가산집합
자연수 집합과 대등하지 않은 무한집합을 비가산집합(uncountable set) 또는 비가부번 무한집합이라고 부른다.
실수 집합이 비가산집합임을 보이기 위하여 먼저 열린구간 \((0,1)\)이 비가산집합임을 보이자. 귀류법을 사용하여 \((0,1)\)이 가산무한집합이라고 가정하면, 이 구간의 모든 실수를 \[r_1,\,r_2,\,r_3,\,r_4,\,\ldots\] 와 같이 빠짐없이 나열할 수 있다.
각 \(r_i\)의 십진법 소수 전개는 끝에서부터 \(9\)가 무한히 반복되지 않는 표현을 택한다. 예를 들어 \(0.5\)는 \(0.5000\cdots\)로 나타내고 \(0.4999\cdots\)로 나타내지 않는다. 이 약속 아래 소수 전개는 유일하다. 다음과 같이 쓰자. \[ \begin{aligned} r_1&=0.d_{11}d_{12}d_{13}d_{14}\cdots,\\ r_2&=0.d_{21}d_{22}d_{23}d_{24}\cdots,\\ r_3&=0.d_{31}d_{32}d_{33}d_{34}\cdots,\\ r_4&=0.d_{41}d_{42}d_{43}d_{44}\cdots,\\ &\ \vdots \end{aligned} \] 여기서 \(d_{ij}\)는 \(r_i\)의 소수점 아래 \(j\)째 자리의 숫자이다.
이제 \[s=0.s_1s_2s_3s_4\cdots\] 를 다음과 같이 정의한다. \[s_i= \begin{cases} 5 & (d_{ii}\ne 5),\\[5pt] 6 & (d_{ii}=5). \end{cases}\] 그러면 \(s\in(0,1)\)이고, 모든 \(i\)에 대하여 \(s\)의 소수점 아래 \(i\)째 자리와 \(r_i\)의 소수점 아래 \(i\)째 자리가 다르다. 선택한 소수 전개의 유일성에 따라 \(s\ne r_i\)이다. 따라서 \(s\)는 위 목록에 들어 있지 않으며, 이는 모든 원소를 나열하였다는 가정과 모순이다. 그러므로 \((0,1)\)은 비가산집합이다. 이 논증을 칸토어의 대각선 논법(Cantor's diagonal argument)이라고 부른다.
문제 5.7. \((0,1)\)의 원소를 나열하려고 했더니 처음 네 항이 다음과 같았다고 하자. \[ r_1=0.5142\cdots,\quad r_2=0.2351\cdots,\quad r_3=0.7754\cdots,\quad r_4=0.1032\cdots. \] 본문의 규칙 \[s_i=5\quad(d_{ii}\ne5),\quad s_i=6\quad(d_{ii}=5)\] 을 사용하여 대각선 논법으로 만드는 수 \(s\)의 소수점 아래 처음 네 자리 \(s_1,s_2,s_3,s_4\)를 구하시오. 또한 뒤의 자릿값이 어떻게 정해지든 이 \(s\)가 \(r_1,r_2,r_3,r_4\)와 각각 다른 이유를 설명하시오.
한편 \[f\colon(0,1)\to\mathbb{R},\quad f(x)=\tan\left(\pi x-\frac{\pi}{2}\right)\] 는 일대일대응이다. 따라서 \(\mathbb{R}\sim(0,1)\)이고, \(\mathbb{R}\)도 비가산집합이다.
문제 5.8. 집합 \(A\)가 비가산집합이고 집합 \(B\)가 \(A\)와 대등할 때, 집합 \(B\)도 비가산집합임을 증명하시오.
자주 사용하는 집합들의 크기를 더 살펴보자.
정리 5.2. (연속체와 대등한 집합들)
임의의 양의 정수 \(n\)에 대하여 \[[0,1]\sim(0,1)\sim\mathbb{R}\sim\mathbb{R}^n\] 이다.
증명 포함함수 \((0,1)\to[0,1]\)은 일대일함수이고, \(x\mapsto (x+1)/3\)은 \([0,1]\)에서 \((0,1)\)로 가는 일대일함수이다. 따라서 칸토어-베른슈타인 정리에 의해 \([0,1]\sim(0,1)\)이다. 위의 탄젠트 함수로부터 \((0,1)\sim\mathbb{R}\)도 얻는다. 또한 포함함수 \([0,1)\to[0,1]\)과 일대일함수 \(x\mapsto x/2\)를 이용하여 다시 칸토어-베른슈타인 정리를 적용하면 \([0,1]\sim[0,1)\)이다.
이제 \([0,1]^2\sim[0,1]\)임을 보이자. 먼저 \([0,1]\sim[0,1)\)이므로 \([0,1]^2\sim[0,1)^2\)이다. \(x,y\in[0,1)\)의 십진 전개를 끝에서부터 \(9\)가 무한히 반복되지 않도록 \[x=0.x_1x_2\cdots,\quad y=0.y_1y_2\cdots\] 로 택하고 \(c_k=10x_k+y_k\in\{0,1,\ldots,99\}\)로 둔다. 다음 함수를 생각하자. \[G(x,y)=\sum_{k=1}^{\infty}\frac{c_k}{100^k}.\] 수열 \((c_k)\)는 끝에서부터 \(99\)가 무한히 반복되지 않으므로 위 식은 \([0,1)\)의 표준적인 \(100\)진 전개를 정한다. 따라서 \(G(x,y)=G(x',y')\)이면 모든 \(k\)에 대하여 \(c_k=c'_k\)이고, 따라서 \(x_k=x'_k\), \(y_k=y'_k\)이다. 즉 \(G\)는 일대일함수이다. 반대로 \(t\mapsto(t,0)\)은 \([0,1)\)에서 \([0,1)^2\)로 가는 일대일함수이므로 칸토어-베른슈타인 정리에 의해 \([0,1)^2\sim[0,1)\)이다. 따라서 \(\mathbb{R}^2\sim\mathbb{R}\)이다.
마지막으로 \(\mathbb{R}^2\sim\mathbb{R}\)을 반복하여 적용하면 수학적 귀납법에 의하여 모든 양의 정수 \(n\)에 대하여 \(\mathbb{R}^n\sim\mathbb{R}\)을 얻는다.
특히 \([0,1]\), 실수 직선 \(\mathbb{R}\), 평면 \(\mathbb{R}^2\), 그리고 임의의 유한차원 유클리드 공간 \(\mathbb{R}^n\)은 모두 대등하다. 3차원 공간의 반직선도 매개변수 \(t\in[0,\infty)\)를 사용하면 \(\mathbb{R}\)과 대등함을 알 수 있다.
문제 5.9. 도형을 점의 집합으로 간주하였을 때, 양의 길이를 갖는 두 선분이 서로 대등함을 보이시오. 또한 양의 길이를 갖는 선분과 실수 직선이 대등함을 보이시오.
복소수 집합 \(\mathbb{C}\)도 실수 집합 \(\mathbb{R}\)과 대등하다. 실제로 \[\mathbb{C}=\{a+bi\mid a,b\in\mathbb{R}\}\] 이고, \((a,b)\mapsto a+bi\)는 \(\mathbb{R}^2\)에서 \(\mathbb{C}\)로 가는 자연스러운 일대일대응이다. 정리 5.2에 의해 \(\mathbb{R}^2\sim\mathbb{R}\)이므로 \(\mathbb{C}\sim\mathbb{R}\)이다.
5. 데데킨트 무한집합
집합 \(A\)가 자기 자신의 어떤 진부분집합과 대등할 때 \(A\)를 데데킨트 무한집합(Dedekind-infinite set)이라고 부른다. 가산무한집합은 모두 데데킨트 무한집합이다. 또한 데데킨트 무한집합은 반드시 무한집합이다.
반대로 모든 무한집합이 데데킨트 무한집합이라는 명제는 ZF 공리계만으로는 증명되지 않는다. 선택공리를 가정하면 모든 무한집합이 데데킨트 무한집합임을 증명할 수 있다. [ZF와 ZFC 공리계 및 선택공리는 뒤의 공리적 집합론 부분에서 다룬다.] 따라서 이 장의 처음에 본 자연수 집합의 성질을 아무 가정 없이 모든 무한집합에 적용해서는 안 된다.
문제 5.10. 다음의 일대일대응을 직접 확인하여 주어진 집합이 데데킨트 무한집합임을 보이시오.
- \(f\colon\mathbb{N}\to\mathbb{N}\setminus\{0\}\), \(f(n)=n+1\)
- \(g\colon\mathbb{Z}\to\mathbb{Z}\setminus\{0\}\), \[ g(n)= \begin{cases} n & (n<0),\\[5pt] n+1 & (n\ge0). \end{cases} \]
각 경우에 공역이 원래 집합의 진부분집합임도 확인하시오.
문제 5.11. 집합 \(A\)에 대하여 다음 두 조건이 동치임을 증명하시오.
- \(A\)는 데데킨트 무한집합이다.
- \(A\)는 \(\mathbb{N}\)과 대등한 부분집합을 갖는다.
이를 이용하여 모든 가산무한집합이 데데킨트 무한집합임을 다시 확인하시오.
6. 칸토어의 정리
지금까지 살펴본 비가산집합은 모두 \(\mathbb{R}\)과 대등한 것이었다. 그렇다면 모든 비가산집합이 \(\mathbb{R}\)과 대등할까? 그렇지 않다.
정리 5.3. (칸토어의 정리)
임의의 집합 \(A\)에 대하여 \[A\prec\mathcal{P}(A)\] 이다. 특히 \(A\)와 그 멱집합 \(\mathcal{P}(A)\) 사이에는 일대일대응이 존재하지 않는다.
증명 함수 \(a\mapsto\{a\}\)는 \(A\)에서 \(\mathcal{P}(A)\)로 가는 일대일함수이므로 \(A\preccurlyeq\mathcal{P}(A)\)이다.
이제 임의의 함수 \(f\colon A\to\mathcal{P}(A)\)를 생각하고 \[B=\{x\in A\mid x\notin f(x)\}\] 로 둔다. 만약 \(f\)가 위로의 함수라면 어떤 \(a\in A\)가 존재하여 \(f(a)=B\)이어야 한다. 그런데 \(B\)의 정의에서 \[a\in B\quad\Longleftrightarrow\quad a\notin f(a)=B\] 를 얻어 모순이다. 따라서 \(A\)에서 \(\mathcal{P}(A)\)로 가는 위로의 함수는 존재하지 않으며, 특히 일대일대응도 존재하지 않는다. 그러므로 \(A\prec\mathcal{P}(A)\)이다.
문제 5.12. 집합 \(A=\{1,2,3,4\}\)와 함수 \(f\colon A\to\mathcal{P}(A)\)가 \[ f(1)=\{1,2\},\quad f(2)=\{1\},\quad f(3)=\{3\},\quad f(4)=\varnothing \] 이라고 주어져 있다고 하자. 다음 물음에 답하시오.
- \(B=\{x\in A\mid x\notin f(x)\}\)를 구하시오.
- 각 \(i\in A\)에 대하여 \(B\)와 \(f(i)\)가 원소 \(i\)의 소속 여부에서 서로 다름을 확인하시오.
- \(B\)가 \(f\)의 치역에 속하지 않음을 설명하시오.
칸토어의 정리를 반복하여 적용하면 \[\mathbb{N}\prec\mathcal{P}(\mathbb{N})\prec\mathcal{P}(\mathcal{P}(\mathbb{N}))\prec\cdots\] 을 얻는다. 따라서 무한집합에도 서로 다른 여러 크기가 존재한다.
문제 5.13. 다음을 증명하시오.
- 가산무한집합 \(A\)와 유한집합 \(B\)에 대하여 \(A\cup B\sim A\)이다.
- 구간 \((0,1)\)과 \((0,\infty)\)는 대등하다.
- 무리수 집합은 비가산집합이다.
- 정수계수인 영이 아닌 다항식의 근이 되는 복소수를 대수적 수(algebraic number)라고 한다. 대수적 수의 집합은 가산집합임을 보이시오.
문제 5.14. 실수 집합 \(\mathbb{R}\)과 자연수 집합의 멱집합 \(\mathcal{P}(\mathbb{N})\)이 대등함을 보이시오. 다음 두 일대일함수와 칸토어-베른슈타인 정리를 이용할 수 있다.
- \(S\subseteq\mathbb{N}\)에 대하여 \(S\mapsto\displaystyle\sum_{n\in S}\frac{2}{3^{n+1}}\)로 두면 \(\mathcal{P}(\mathbb{N})\)에서 \([0,1]\)로 가는 일대일함수를 얻는다.
- \([0,1]\)을 \((0,1)\) 안으로 일대일로 옮긴 뒤, 각 실수의 이진 전개를 끝에서부터 \(1\)이 무한히 반복되지 않도록 택하여 숫자 \(1\)이 나타나는 자리들의 집합을 대응시키면 \([0,1]\)에서 \(\mathcal{P}(\mathbb{N})\)으로 가는 일대일함수를 얻는다.
문제 5.15. 다음 집합이 유한집합, 가산무한집합, 비가산집합 중 어디에 속하는지 판정하고 그 이유를 설명하시오.
- \(\{3n+1\mid n\in\mathbb{N}\}\)
- \(\mathbb{Z}\times\{0,1,2\}\)
- \(\mathbb{Q}\cap(0,1)\)
- \(\mathbb{R}\setminus\mathbb{Q}\)
- \(\mathcal{P}(\mathbb{N})\)
7. 연속체 가설
칸토어는 다음과 같은 질문을 제기했다.
“\(\mathbb{N}\prec A\prec\mathbb{R}\)을 만족시키는 집합 \(A\)가 존재하는가?”
이 질문에 대한 부정적 답변, 즉 그러한 집합은 존재하지 않는다는 주장을 연속체 가설(Continuum Hypothesis, CH)이라고 부른다.
괴델은 ZFC가 모순이 없다면 ZFC에 연속체 가설을 추가해도 모순이 생기지 않음을 보였고, 코언은 ZFC가 모순이 없다면 연속체 가설의 부정을 추가해도 모순이 생기지 않음을 보였다. 따라서 ZFC가 모순이 없다고 가정하면 연속체 가설은 ZFC에서 증명할 수도 반증할 수도 없는 독립적인 명제이다.