두 집합이 유한집합일 때에는 각각의 원소의 개수를 세어 어느 것이 더 많은 원소를 가지고 있는지 비교할 수 있다. 그러나 무한집합의 경우에는 원소의 개수를 직접 세는 방법으로 크기를 비교할 수 없다. 대신 두 집합 사이에 원소를 하나씩 대응시켜 어느 쪽이 더 많은지 비교할 수 있다.
유한집합과 무한집합
두 집합 \(A,\) \(B\)에 대하여 일대일 대응 \(f : A \to B\)가 존재할 때 '\(A\)와 \(B\)는 대등하다(equi-numerous)'라고 말하고 이것을 기호로 \(A\approx B\)로 나타낸다. 대등하다는 것을 '크기가 같다' 또는 '농도가 같다'라고 표현하기도 한다. ['일대일 대응'을 '전단사 함수'라고 부르기도 한다.]
일대일 대응의 성질에 의하여 대등 관계는 다음을 만족시킨다.
- 임의의 집합 \(A\)에 대하여 \(A\approx A\)이다.
- 집합 \(A, \) \(B\)에 대하여 \(A\approx B\)이면 \(B\approx A\)이다.
- 집합 \(A, \) \(B, \) \(C\)에 대하여 \(A \approx B\)이고 \(B \approx C\)이면 \(A \approx C\)이다.
이러한 관점에서 대등관계는 임의의 집합족 위에서 동치관계이다.
\(E\)가 집합이라고 하자. 만약 \(0\) 이상의 정수 \(n\)이 존재하여 \[E\approx \left\{0,~1,~2,~\cdots,~n\right\}\] 을 만족시키거나 \(E = \varnothing\)이면 \(E\)를 '유한집합'이라고 부른다. 이것은 기호 \(\omega\)와 \(\omega _n\)을 이용하면 더 편리하게 나타낼 수 있다. \[ \begin{eqnarray} \omega &:=& \left\{ k \in \mathbb{Z} ~|~ k \ge 0 \right\} ,\\[7pt] \omega _n &:=& \left\{ k \in \mathbb{Z} ~|~ 0 \le k < n \right\} \end{eqnarray} \] 이라고 하자. 그러면 \(E\)가 유한집합이라는 것은 \[\exists n \in \omega ~:~ E \approx \omega _n \] 인 것과 동치이다. 한편 유한집합이 아닌 집합을 '무한집합'이라고 부른다.
가산집합
\(\mathbb{N}\)이 자연수 전체 집합이고 \(E\)가 무한집합이라고 하자. \(E\)는 공집합이 아니므로 \(x_1 \in E\)가 존재한다. \(E \backslash \left\{ x_1 \right\}\)은 공집합이 아니므로 \(x_2 \in E \backslash \left\{ x_1 \right\}\)이 존재한다. \(E\backslash \left\{x_1 ,~x_2 \right\}\)는 공집합이 아니므로 \(x_3 \in \left\{ x_1 ,~ x_2 \right\} \)가 존재한다. 일반적으로 \(x_1 ,\) \(x_2 ,\) \(\cdots , \) \(x_n \)이 \(E\)의 서로 다른 원소일 때 \[x_{n+1} \in E \backslash \left\{x_1 ,~ x_2 ,~ \cdots ,~ x_n \right\}\] 이 존재한다. 이와 같은 방법으로 구성한 집합 \(\left\{ x_i ~|~ i\in \mathbb{N}\right\}\)은 명백히 \(\mathbb{N}\)과 대등한 집합이다. 즉 임의의 무한집합은 자연수 집합과 대등한 부분집합을 가진다.
자연수 집합과 대등한 집합을 '가부번집합(enumerable set)'이라고 부른다. 가부번집합은 무한집합 중에서 가장 작은 집합이다. 즉 임의의 무한집합은 자연수 집합과 대등한 부분집합을 가진다. 유한집합과 가부번집합을 통틀어 '가산집합(countable set)'이라고 부른다.
집합의 크기와 관련하여 자주 사용되는 몇 가지 성질들은 다음과 같은 것들이 있다. (이 정리들의 증명은 어렵지 않으므로 연습 삼아 직접 해 보기 바란다.)
- \(E\)가 무한집합일 필요충분조건은 가부번인 부분집합을 갖는 것이다.
- \(E\)가 무한집합이고 \(F\)가 유한집합이면 \(E \approx E\backslash F \)이다.
- \(E\)가 무한집합이고 \(E \subseteq D\)이면 \(D\)도 무한집합이다.
- \(A\)와 \(B\)가 유한집합이면 \(A \times B\)도 유한집합이다.
- \(A\)와 \(B\)가 가산집합이면 \(A \times B\)도 가산집합이다.
- \(A\)가 유한집합이면 \(A\)의 모든 부분집합들의 모임인 \(\mathcal{P} (A)\)도 유한집합이다.
- 임의의 집합 \(A\)에 대하여 \(2^A \approx \mathcal{P} (A) \)이다.
(\(2^A\)는 정의역이 \(A\)이고 공역이 \(\left\{ 0,~1 \right\} \)인 함수들의 모임이다.) - 집합족 \(\left\{ A_i ~|~ i \in \mathbb{N} \right\}\)의 모든 원소 \(A_i \)가 가산집합이면 \(\bigcup _ { i \in \mathbb{N}} A_i \)도 가산집합이다.
비가산집합
정수 전체 집합 \(\mathbb{Z}\)는 가산집합이다. 왜냐하면 \(\mathbb{Z}\)의 모든 원소를 \[ 0 ,~ -1 ,~ 1 ,~ -2 ,~ 2 ,~ -3 ,~ 3 ,~ -4 ,~ 4 , ~ \cdots \] 와 같이 빠짐 없이 한 줄로 나열할 수 있기 때문이다. 한 줄로 나열할 수 있다는 것은 순서대로 자연수를 하나씩 대응시킬 수 있다는 것을 의미한다. 따라서 \(\mathbb{Z}\)와 \(\mathbb{N}\)은 대등하다. 마찬가지로 유리수 전체 집합 \(\mathbb{Q}\)도 가산집합이다. 유리수를 기약분수로 나타내었을 때 분모와 분자의 절댓값의 합이 작은 것부터(만약 같다면 분자가 작은 것부터, 그리고 음수부터) 차례대로 쓰면 \[0 ,~ - \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} ,~ \cdots \] 와 같이 모든 유리수가 빠짐 없이 나열된다.
그러나 모든 무한집합이 가산집합인 것은 아니다. 대표적인 예로 실수 전체 집합 \(\mathbb{R}\)는 가산집합이 아니다.
만약 \(\mathbb{R}\)가 가산집합이라면 부분집합인 열린구간 \(I = (0,~1)\)도 가산집합이어야 한다. 그러면 \(I\)의 모든 원소를 \[x_1 ,~ x_2 ,~ x_3 ,~ x_4 ,~ \cdots \]와 같이 빠짐없이 나열할 수 있다. 각 \(x_n \)은 \(0\)보다 크고 \(1\)보다 작은 실수이므로 정수부분이 \(0\)인 소수로 나타낼 수 있다. 특히 \(x_n \)이 유한소수인 경우에는 \(0\)이 아닌 마지막 자리에서 \(1\)을 빼고 그 뒤에 \(9\)를 무한이 이어 써서 동일한 값의 수를 무한소수로 나타낼 수 있다. 이제 \(x_n \)의 소수점 아래 \(m\)번째 자리 수를 \(x_{nm} \)이라고 하자. [여기서 아래첨자 \(nm\)은 \(n\)과 \(m\)을 곱한다는 의미가 아니라 단지 두 수를 이어서 쓴 것이다.] 그러면 \(I\)의 원소 \(x_1 ,\) \(x_2 ,\) \(x_3 ,\) \(x_4 ,\) \(\cdots\)를 \[ \begin{eqnarray} x_1 &=& 0 \,.\, x_{11}\, x_{12}\, x_{13}\, x_{14} \cdots \\[7pt] x_2 &=& 0 \,.\, x_{21}\, x_{22\,} x_{23}\, x_{24} \cdots \\[7pt] x_3 &=& 0 \,.\, x_{31}\, x_{32}\, x_{33}\, x_{34} \cdots \\[7pt] x_4 &=& 0 \,.\, x_{41\,} x_{42}\, x_{43}\, x_{44} \cdots \\[7pt] & \vdots & \end{eqnarray} \] 와 같이 소수 전개로 표현하여 나열할 수 있다. 이때 각 자연수 \(i\)에 대하여 \(y_i\)를 \[ y_i := \begin{cases} 1 ~~& \mbox{if} ~~ x_{ii} \ne 1 \\[10pt] 2 ~~& \mbox{if} ~~ x_{ii} = 1 \end{cases} \] 이라고 정의하고 \(y\)를 \[y_i = 0\,. \,y_1 \,y_2 \,y_3 \,y_4 \cdots \] 와 같은 소수 전개를 갖는 수로 정의하자. 명백히 \(y\)는 \(0\)보다 크고 \(1\)보다 작은 수이므로 \(I\)의 원소이다. 그러나 임의의 자연수 \(i\)에 대하여 \(y_i \ne x_{ii}\)이므로 \(y \ne x_i \)이다. [\(y\)와 \(x_i\)가 소수점 아래 \(i\)번째 자리의 숫자가 같지 않으므로 두 수가 같지 않다는 뜻이다.] 즉 \(y\)는 어떠한 \(x_i \)와도 같지 않다. 이것은 \(I\)의 모든 원소를 \(x_i \) 꼴의 수로 나열했다는 것에 모순이다. 따라서 \(I\)는 가산집합이 아니다. [이러한 증명 방법을 칸토어의 대각법이라고 부른다.] \(I\)는 \(\mathbb{R}\)의 부분집합이므로 \(\mathbb{R}\)도 가산집합이 아니다.
이와 같이 가산집합이 아닌 집합을 '비가산집합(uncountable set)'이라고 부른다.
\(\mathbb{R}\)와 대등한 집합들
열린구간 \(I = (0,~1)\)은 \(\mathbb{R}\)와 대등하다. 왜냐하면 함수 \(f : I \to \mathbb{R} \)를 \[f(x) = \tan \pi \left( x - \frac{1}{2} \right)\] 또는 \[f(x) = \frac{1 - 2 x}{x (x-1)} \] 로 정의하면 \(f\)는 \(I\)로부터 \(\mathbb{R}\)로의 일대일 대응이 되기 때문이다.
두 집합이 대등한 경우 뿐만 아니라 한 집합이 다른 집합보다 더 큰 경우를 나타내는 용어가 있으면 편리할 것이다. 두 집합 \(A,\) \(B\)에 대하여 일대일 함수 \(f : A \to B\)가 존재할 때 '\(B\)가 \(A\)보다 크거나 \(B\)와 \(A\)가 대등하다'라고 말하고 \(A \preccurlyeq B\)로 나타낸다. 그리고 \( A \preccurlyeq B\)이면서 \(A \not\approx B\)인 것을 \( A \prec B\)로 나타낸다. ['일대일 함수'를 '단사 함수'라고 부르기도 한다.]
'칸토어-베른슈타인(Cantor-Bernstein) 정리'에 의하면 두 집합 \(A,\) \(B\)에 대하여 \(A \preccurlyeq B\)이면서 동시에 \(B \preccurlyeq A\)이면 \(A \approx B \)가 성립한다. [이 정리의 증명은 상당히 복잡하므로 여기서는 증명하지 않겠다.] 이러한 의미에서 \(\preccurlyeq\)는 임의이 집합족 위에서 순서관계이다.
이제 \(I = (0,~1)\)과 \(I^2 = (0,~1) \times (0,~1) \)이 대등함을 보이자. \(I^2 \)의 원소 \(w\)가 임의로 주어졌다고 하자. \(w\)의 \(x\)좌표와 \(y\)좌표를 각각 소수로 나타낸 순서쌍을 \[ w = ( 0 \,.\, x_1 \,x_2 \,x_3 \cdots ,~ 0\,.\, y_1 \,y_2 \,y_3 \cdots ) \] 이라고 하자. 그리고 \[z = 0 \,.\, x_1 \,y_1 \,x_2 \,y_2 \,x_3 \,y_3 \cdots \] 이라고 정의하자. 이때 \(w\)를 \(z\)에 대응시키는 함수 \(f : w \mapsto z \)는 \(I^2 \)으로부터 \(I\)로의 일대일 함수이다. 따라서 \(I^2 \preccurlyeq I \)이다. 한편 명백히 \(I \preccurlyeq I^2 \)이다. 그러므로 칸토어-베른슈타인 정리에 의하여 \( I \approx I^2 \)이 성립한다. [참고로 임의의 무한집합 \(E\)와 자연수 \(n\)에 대하여 \(E \approx E^n \)이 성립한다.]
끝으로 복소수 전체 집합 \(\mathbb{C}\)가 \(\mathbb{R}\)와 대등함을 보이자. 임의의 복소수 \(z\)에 대하여 \(z = a + b \mathbb{i} \)를 만족시키는 실수 \(a,\) \(b\)가 각각 유일하게 존재한다. 이때 \(a + b \mathbb{i} \)를 순서쌍 \( (a,~b) \)에 대응시키면 \(\mathbb{C}\)는 \(\mathbb{R} ^2 \)과 대등하다는 것을 알 수 있다. 한편 \(\mathbb{R}\)는 열린구간 \(I = (0,~1)\)과 대등하고 \(\mathbb{R}^2 \)은 \(I^2 \)과 대등하므로 \[\mathbb{R} \approx I \approx I^2 \approx \mathbb{R}^2 \approx \mathbb{C} \] 를 얻는다.
연속체 가설
지금까지 살펴본 바에 의하면 \[\mathbb{N} \approx \mathbb{Z} \approx \mathbb{Q} \prec \mathbb{R} \approx \mathbb{C} \] 이다. 그렇다면 \(\mathbb{R}\)보다 더 큰 집합이 존재할까?
'칸토어의 정리'에 의하면 임의의 집합 \(E\)에 대하여 거듭제곱집합 \(\mathcal{P} (E) \)는 \(E\)보다 크다. 이것의 증명은 어렵지 않다. 만약 \(E \approx \mathcal{P} (E) \)라면 일대일 대응 \(\phi : E \to \mathcal{P} (E) \)가 존재한다. \[B = \left\{ x \in E ~|~ x \notin \phi (x) \right\}\]라고 하면 \(B \subseteq E\)이다. 따라서 \(B = \phi (y) \)인 \(y \in E \)가 존재한다. \(y \in \phi (y) \)라고 가정하면 \(y \notin B \)이므로 \(y \notin \phi (y) \)가 되어 모순이다. \(y \notin \phi (y) \)라고 가정하면 \( y \in B \)이므로 \(y \in \phi (y) \)가 되어 모순이다. 어느 경우에나 모순이므로 일대일 대응 \( \phi : E \to \mathcal{P} (E) \)는 존재할 수 없다. 그러므로 \(E \prec \mathcal{P} (E) \)이다.
이제 칸토어의 정리에 의하여 다음을 얻는다. \[ \mathbb{R} \prec \mathcal{P}(\mathbb{R}) \prec \mathcal{P} ( \mathcal{P}(\mathbb{R})) \prec \mathcal{P} ( \mathcal{P} ( \mathcal{P}(\mathbb{R}))) \prec \cdots \] 즉 크기에 따른 무한집합의 종류 또한 무한히 많다. 한편 실수계의 완비성과 유리수의 조밀성, 그리고 연속함수의 성질을 이용하면 \(\mathbb{R} \approx \mathcal{P}(\mathbb{Q})\)라는 것이 증명된다. [이것의 증명은 해석학의 기술이 필요하므로 여기서는 증명하지 않겠다.] 이제 또 하나의 의문이 생긴다.
\(\mathbb{Q} \prec S \prec \mathbb{R}\)인 집합 \(S\)가 존재하는가?
일반화시켜 생각해보면
임의의 무한집합 \(E\)에 대하여 \(E \prec S \prec \mathcal{P} (E) \)인 집합 \(S\)가 존재하는가?
라는 의문이 생긴다. 20세기 초까지 많은 수학자들이 그러한 집합 \(S\)는 존재하지 않을 것이라고 추측하였는데, 이러한 추측을 '연속체 가설(continuum hypotheseis)'이라고 부른다. 1938년 괴델(Kurt Gödel)은 연속체 가설이 집합론의 기존 공리에 모순되지 않는다는 것을 증명하였으며, 1963년 코헨(Paul Cohen)은 연속체 가설이 집합론의 기존 공리와 독립적임을 증명하였다. 즉 연속체 가설은 선택 공리와 마찬가지로 그것을 참으로 받아들이든 그것을 부정하든 전혀 모순이 발생하지 않는다.