집합은 원소의 개수에 따라 유한집합과 무한집합으로 나뉜다. 무한집합은 다시 가산무한집합과 비가산무한집합으로 분류된다. 이 장에서는 무한의 개념을 엄밀하게 다루고, 서로 다른 크기의 무한이 존재함을 살펴본다.
1. 유한집합과 무한집합의 정의
집합 \(A\)가 유한집합(finite set)이라는 것은 \(A\)가 공집합이거나, 또는 어떤 자연수 \(k\)에 대하여 \(A\)의 원소를 \(a_1,\, a_2,\, \ldots,\, a_k\)와 같이 나열할 수 있다는 의미이다. 이때 \(k\)를 집합 \(A\)의 원소의 개수 또는 크기라고 하고 \(|A| = k\) 또는 \(n(A) = k\)로 나타낸다. 단, 공집합의 경우 \(|\varnothing | = 0\)인 것으로 약속한다.
집합 \(A\)가 유한집합이 아닐 때 \(A\)를 무한집합(infinite set)이라고 부른다. 무한집합의 원소는 끝없이 많으므로 모두 나열할 수 없다.
무한집합의 특징 중 하나는 자기 자신과 일대일로 대응하는 진부분집합이 존재한다는 것이다. 예를 들어, 자연수 집합 \(\mathbb{N} = \{0,\, 1,\, 2,\, 3,\, \ldots\}\)과 그 진부분집합인 짝수 집합 \(\{0,\, 2,\, 4,\, 6,\, \ldots\}\) 사이에는 \(n \mapsto 2n\)이라는 일대일대응이 존재한다. [\(n\mapsto 2n\)은 \(n\)을 \(2n\)에 대응시키는 함수라는 뜻이다.]
2. 일대일 대응과 집합의 크기
두 집합 \(A\)와 \(B\) 사이에 일대일대응 \(f: A \to B\)가 존재할 때, \(A\)와 \(B\)는 대등(equipotent)하다고 하며 \(A \sim B\)로 나타낸다. 대등 관계는 다음 성질을 만족한다.
- 반사적 성질: \(A \sim A\)
- 대칭적 성질: \(A \sim B\)이면 \(B \sim A\)이다.
- 추이적 성질: \(A \sim B\)이고 \(B \sim C\)이면 \(A \sim C\)이다.
유한집합의 경우, 두 집합이 대등할 필요충분조건은 원소의 개수가 같은 것이다. 무한집합의 경우에는 대등 관계를 통해 집합의 크기를 비교한다.
문제 5.1. 슈뢰더-베른슈타인 정리(Schröder–Bernstein theorem)를 조사해 보자.
3. 가산무한집합
자연수 집합 \(\mathbb{N}\)과 대등한 무한집합을 가산무한집합(countably infinite set) 또는 가부번집합이라고 부른다. 유한집합과 가산무한집합을 통틀어 가산집합(countable set)이라고 부른다.
가산무한집합의 원소는 \(a_0,\, a_1,\, a_2,\, a_3,\, \ldots\)와 같이 자연수로 번호를 매겨 빠짐 없이 나열할 수 있다.
이제 정수 집합 \(\mathbb{Z}\)와 유리수 집합 \(\mathbb{Q}\)가 가산집합임을 보이자.
우선 정수 집합 \(\mathbb{Z}\)를 살펴보자. 다음과 같은 대응을 생각하자. \[f: \mathbb{N} \to \mathbb{Z}, \quad f(n) = \begin{cases} \frac{n}{2} & (n\text{이 짝수일 때}) \\[6pt] -\frac{n+1}{2} & (n\text{이 홀수일 때}) \end{cases}\] 이 함수는 \(\mathbb{N}\)의 원소를 \(0,\, -1,\, 1,\, -2,\, 2,\, -3,\, 3,\, \ldots\) 순서로 \(\mathbb{Z}\)의 원소와 대응시키는 일대일대응이다. 그러므로 \(\mathbb{Z}\)는 가산집합이다.
다음으로 유리수 집합 \(\mathbb{Q}\)를 살펴보자. 모든 유리수를 두 정수의 비 \(\frac{p}{q}\) 형태로 나타낼 수 있다는 성질을 바탕으로 유리수 집합이 가산임을 보일 수 있다. (단, \(p \in \mathbb{Z}\), \(q \in \mathbb{N} \setminus \{0\}\), \(\gcd(p,\,q) = 1\).)
유리수를 다음과 같이 나열하자. \[\begin{aligned} &\frac{0}{1}, \\[6pt] &\frac{-1}{1},\,\, \frac{1}{1}, \\[6pt] &\frac{-1}{2},\,\, \frac{1}{2},\,\, \frac{-2}{1},\,\, \frac{2}{1}, \\[6pt] &\frac{-1}{3},\,\, \frac{1}{3},\,\, \frac{-3}{1},\,\, \frac{3}{1}, \\[6pt] &\frac{-1}{4},\,\, \frac{1}{4},\,\, \frac{-2}{3},\,\, \frac{2}{3},\,\, \frac{-3}{2},\,\, \frac{3}{2},\,\, \frac{-4}{1},\,\, \frac{4}{1}, \\[6pt] &\frac{-1}{5},\,\, \frac{1}{5},\,\, \frac{-5}{1},\,\, \frac{5}{1}, \\[6pt] & \,\, \vdots \end{aligned}\] 즉 \(k\)번째 줄에 \(|p| + q = k\)인 기약분수들을 나열한 것이다. 각 줄은 유한개의 원소를 가지므로, 이 방법으로 모든 유리수를 나열할 수 있다. 모든 유리수를 자연수처럼 나열하였으므로, 유리수 집합 \(\mathbb{Q}\)는 가산집합이다.
문제 5.2. 다음 집합이 가산집합임을 보이시오.
- 모든 짝수의 집합
- 모든 홀수 정수의 집합
- \(\mathbb{N} \times \mathbb{N}\)
- 유한 개의 가산집합의 합집합
문제 5.3. 다음을 증명하시오.
- \(A\)가 무한집합이면, \(A\)의 부분집합 중에서 \(\mathbb{N}\)과 대등한 것이 존재한다.
- \(B\)가 무한집합이면, \(B\)의 진부분집합 중에서 \(B\)와 대등한 것이 존재한다.
- \(C\)가 유한집합이면, \(C\)의 진부분집합 중에서 \(C\)와 대등한 것이 존재하지 않는다.
4. 비가산집합
자연수 집합과 대등하지 않은 무한집합을 비가산집합(uncountable set) 또는 비가부번 무한집합이라고 부른다.
실수 집합이 비가산집합임을 살펴보자. 열린구간 \((0,\,1)\)이 비가산집합임을 보이면 충분하다.
귀류법을 사용하자. 열린구간 \((0,\,1)\)이 가산무한이라고 가정하면, 이 구간의 모든 실수를 다음과 같이 자연수처럼 한 줄로, 빠짐없이 나열할 수 있다. \[r_1,\, r_2,\, r_3,\, r_4,\, \ldots .\] 각 실수를 십진법 소수 전개로 다음과 같이 나타내었다고 하자. \[\begin{aligned} r_1 &= 0.d_{11}\,d_{12}\,d_{13}\,d_{14}\cdots \\[6pt] r_2 &= 0.d_{21}\,d_{22}\,d_{23}\,d_{24}\cdots \\[6pt] r_3 &= 0.d_{31}\,d_{32}\,d_{33}\,d_{34}\cdots \\[6pt] r_4 &= 0.d_{41}\,d_{42}\,d_{43}\,d_{44}\cdots \\[6pt] &\vdots \end{aligned}\] 즉, \(d_{ij}\)는 실수 \(r_i\)의 소수점 아래 \(j\)째 자리의 숫자이다. [만약 \(r_i\)가 유한소수로 표현된다면, 마지막 자리의 숫자에서 \(1\)을 빼고 그 뒤에 \(9\)를 연달아 붙임으로써 \(d_{ij}\)를 유일하게 정의한다.]
이제 다음과 같은 실수 \(s\)를 구성한다. \[s = 0.s_1\,s_2\,s_3\,s_4\cdots\] 여기서 \(s_i\)는 \(d_{ii} \neq 5\)이면 \(s_i = 5\), \(d_{ii} = 5\)이면 \(s_i = 6\)으로 정의한다.
그러면 \(s \in (0,\, 1)\)이지만, 모든 \(i\)에 대해 \(s \neq r_i\)이다. 왜냐하면 소수점 아래 \(i\)째 자리 숫자가 다르기 때문이다. 이것은 모순이다. 그러므로 열린구간 \((0,\,1)\)은 비가산집합이다.[이와 같은 방법으로 \(\mathbb{R}\)이 비가산임을 보이는 방법을 '칸토어의 대각선 논법'이라고 부른다.]
한편 다음과 같이 정의된 함수 \(f\)는 \((0,\, 1)\)로부터 \(\mathbb{R}\) 위로의 일대일대응이다. \[f(x) = \tan\left(\pi x - \frac{\pi}{2}\right)\] 그러므로 \(\mathbb{R}\)도 비가산집합이다.
문제 5.4. 집합 \(A\)가 비가산집합이고 집합 \(B\)가 \(A\)와 대등할 때, 집합 \(B\)도 비가산집합임을 증명하시오.
자주 사용하는 집합의 크기를 더 살펴보자. 놀랍게도 다음 집합들은 모두 대등하다.
- 구간 \([0,\, 1]\)
- 실수 직선 \(\mathbb{R}\)
- 평면 \(\mathbb{R}^2\)
- 3차원 공간에 놓인 반직선
- \(n\)차원 공간 \(\mathbb{R}^n\) (단, \(n\ge 1\))
문제 5.5. 도형을 점의 집합으로 간주하였을 때, 길이가 다른 두 선분이 서로 대등함을 보이시오. 또한 길이가 유한인 선분과 길이가 무한인 직선이 대등함을 보이시오.
구간 \([0,\, 1]\)과 \([0,\, 1]^2\) 사이의 일대일대응은 다음과 같이 구성할 수 있다. 점 \((x,\, y) \in [0,\, 1]^2\)에 대해 \(x\)와 \(y\)를 소수 전개하여 \[\begin{aligned} x &= 0.x_1\,x_2\,x_3\cdots \\[6pt] y &= 0.y_1\,y_2\,y_3\cdots \end{aligned}\] 라고 하면, 소수점 아래 숫자를 \[z = 0.x_1\,y_1\,x_2\,y_2\,x_3\,y_3\cdots\] 와 같이 조합하여 \([0,\, 1]\)의 원소를 만들 수 있다. [실제 증명에서는 소수 전개의 유일성 문제를 처리해야 한다.]
이와 같은 성질을 사용하면, 자연스럽게 복소수 집합 \(\mathbb{C}\)가 실수 집합 \(\mathbb{R}\)과 대등함을 보일 수 있다. 즉 \(\mathbb{C} = \{a + bi \mid a,\,b \in \mathbb{R}\}\)이므로 \(\mathbb{C}\)와 \(\mathbb{R}^2\) 사이에 자연스러운 일대일 대응 \((a,\, b) \mapsto a + bi\)가 존재한다. 그런데 \(\mathbb{R}^2 \sim \mathbb{R}\)이므로, \(\mathbb{C} \sim \mathbb{R}\)이다. 이 과정을 반복하면, 임의의 양의 정수 \(n\)에 대하여 \(\mathbb{R} \sim \mathbb{R}^n\)임을 알 수 있다.
펜으로 종이에 선을 하나 그으면, 그 선 위에 있는 점의 개수와 우리의 몸을 이루고 있는 점의 개수는 같다.
문제 5.6. 데데킨트가 무한집합을 정의한 방법을 조사하고, 데데킨트가 정의한 무한집합이 이 장에서 정의한 무한집합의 정의와 동치임을 밝히시오. [엄밀히 말하면, ZF 공리계에서는 동치가 아니며, ZFC 공리계에서는 동치이다.]
5. 칸토어의 정리
지금까지 살펴본 비가산집합은 모두 \(\mathbb{R}\)과 대등한 것이었다. 그렇다면 모든 비가산집합이 \(\mathbb{R}\)과 대등할까? 그렇지 않다.
정리 5.1. (칸토어의 정리)
임의의 집합 \(A\)에 대하여, \(A\)와 그 멱집합 \(\mathcal{P}(A)\) 사이에는 일대일대응이 존재하지 않는다. 즉, \(|\mathcal{P}(A)| > |A|\)이다.
증명
\(f: A \to \mathcal{P}(A)\)가 임의의 함수라고 하자. 다음 집합을 정의한다. \[B = \{x \in A \mid x \notin f(x)\}\] 그러면 \(B \in \mathcal{P}(A)\)이지만, 모든 \(a \in A\)에 대해 \(B \neq f(a)\)이다. 그 이유는 다음과 같다.
- 만약 \(a \in B\)이면 정의에 의해 \(a \notin f(a)\)이므로 \(B \neq f(a)\)이다.
- 만약 \(a \notin B\)이면 정의에 의해 \(a \in f(a)\)이므로 \(B \neq f(a)\)이다.
따라서 \(f\)는 위로의 함수가 아니고, 일대일대응도 아니다.
칸토어의 정리는 다음과 같이 무한집합 또한 다양한 종류가 있음을 보여준다. \[|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots\]
문제 5.7. 다음을 증명하시오.
- 무한집합 \(A\)와 유한집합 \(B\)에 대하여 \(A \cup B \sim A\)이다.
- 구간 \((0,\, 1)\)과 \((0,\ \infty)\)는 대등하다.
- 무리수 집합은 비가산집합이다.
- 대수적 수의 집합은 가산집합이다.
문제 5.8. 실수 집합 \(\mathbb{R}\)과 자연수 집합의 멱집합 \(\mathcal{P}(\mathbb{N})\)이 대등함을 보이시오.
6. 연속체 가설
칸토어는 다음과 같은 질문을 제기했다.
"\(|\mathbb{N}| < |A| < |\mathbb{R}|\)을 만족시키는 집합 \(A\)가 존재하는가?"
이 질문에 대한 부정적 답변, 즉 "그러한 집합은 존재하지 않는다"라는 주장을 연속체 가설(Continuum Hypothesis, CH)이라고 부른다.
괴델과 코언의 연구에 의해, 연속체 가설은 ZFC 공리계에서 증명할 수도 없고 반증할 수도 없다는 것이 밝혀졌다. 즉, 연속체 가설은 ZFC와 독립적이다.