집합의 크기(Cardinality) — 무한의 크기를 비교하다

유한한 집합의 크기는 원소를 세면 알 수 있다. 그렇다면 무한한 집합의 크기는 어떻게 비교할까? 자연수는 무한하고, 실수도 무한하다. 이 둘의 크기는 같을까? 이 글에서는 집합의 크기(Cardinality) 개념을 정의하고, 무한집합들의 크기를 체계적으로 비교해본다.

“무한”이라는 단어는 흔히 “끝이 없다”는 의미로 쓰인다. 그런데 수학에서는 무한에도 크기의 차이가 있다. 자연수의 무한과 실수의 무한은 본질적으로 다르다. 19세기 수학자 게오르크 칸토어(Georg Cantor)는 이를 엄밀하게 증명하며 현대 집합론의 기초를 세웠다. 처음에는 너무 급진적이라는 이유로 동시대 수학자들에게 거센 비판을 받았지만, 지금은 수학의 근간이 된 이론이다.

이 글은 암호학과 계산 복잡도 이론(Complexity Theory)의 수학적 기반이 되는 Cardinality 개념을 정리한다. 특히 ‘셀 수 있는 무한(가산 무한)‘과 ‘셀 수 없는 무한(불가산 무한)‘의 차이, 그리고 칸토어의 대각선 논법을 단계적으로 살펴본다.

---

집합	원소 예시	크기	가산 여부
자연수 ℕ	0, 1, 2, 3, …	ℵ₀	가산 무한
정수 ℤ	…, -2, -1, 0, 1, 2, …	ℵ₀	가산 무한
양의 유리수 ℚ⁺	1/1, 1/2, 2/1, …	ℵ₀	가산 무한
실수 ℝ	π, √2, 0.1010…	ℵ₁	불가산 무한

---

집합의 크기란?

두 집합 $A$, $B$의 모든 원소가 일대일 대응(bijection) 된다면, 두 집합의 크기는 같다고 정의한다.

$|A| = |B| \iff \exists f: A \to B \text{ (전단사 함수)}$

유한 집합의 경우 이는 직관적이다. $A = \{1, 2, 3\}$이면 $|A| = 3$이다. 그런데 무한 집합에서는 이 정의가 예상치 못한 결과를 만들어낸다.

---

유한 집합

유한 집합 $X$에 대하여, 크기는 자연수로 나타낼 수 있다.

$|X| = k \quad (k \in \mathbb{N})$

---

자연수 집합: $|\mathbb{N}|$

자연수 집합은 무한하지만 셀 수 있다(countable). 집합의 모든 원소에 자연수 번호를 붙일 수 있다면 셀 수 있다고 한다.

$X = \{0\} \cup \mathbb{N} = \{0, 1, 2, \ldots\}$라고 할 때, $X$의 각 원소에 자연수를 순서대로 대응시킬 수 있으므로 $|X| = |\mathbb{N}|$이다. 원소 하나가 더 있어도 무한집합의 크기는 변하지 않는다.

---

정수 집합: $|\mathbb{Z}|$

정수 집합도 자연수 집합과 크기가 같다. 다음과 같이 양수·음수 쌍으로 묶어 자연수를 대응시킬 수 있기 때문이다.

$\mathbb{Z} = \{(0)_0,\ (1,\ {-1})_1,\ (2,\ {-2})_2,\ \ldots\}$

밑첨자는 대응되는 자연수를 나타낸다. 이 방식으로 정수 집합의 모든 원소에 번호를 매길 수 있으므로,

$|\mathbb{Z}| = |\mathbb{N}|$

---

양의 유리수 집합: $|\mathbb{Q}^+|$

모든 양의 유리수는 기약분수 $\frac{p}{q}$ 형태, 즉 두 자연수의 쌍으로 나타낼 수 있다. 분자와 분모의 합이 같은 것들을 묶어 순서를 매기면 된다.

$\mathbb{Q}^+ = \left\{\left(\frac{1}{1}\right)_1,\ \left(\frac{1}{2},\ \frac{2}{1}\right)_2,\ \left(\frac{1}{3},\ \frac{2}{2},\ \frac{3}{1}\right)_3,\ \ldots\right\}$

이 방식으로 모든 양의 유리수에 자연수 번호를 매길 수 있으므로,

$|\mathbb{Q}^+| = |\mathbb{N}|$

---

실수 집합: $|\mathbb{R}|$

결론부터 말하면, 실수 집합의 크기는 자연수 집합보다 크다.

$|\mathbb{N}| \ne |\mathbb{R}|$

이를 칸토어의 대각선 논법(Cantor Diagonalization) 으로 증명한다.

증명 아이디어 (4단계)

1. 가정: 모든 실수를 자연수에 대응한 무한 목록이 존재한다고 가정한다.
2. 선택: 각 $a_n$의 소수점 $n$번째 자리 $d_{nn}$을 대각선 방향으로 선택한다.
3. 변환: 각 $d_{nn}$을 바꿔 새로운 수 $X$를 만든다.
4. 모순: $X$는 목록의 어떤 $a_n$과도 $n$번째 자리에서 반드시 다르므로 목록에 없다. → 가정 모순.

형식 증명

$\mathbb{R}_{01} = \{x \mid 0 \le x < 1\}$과 $\mathbb{N}$이 일대일 대응이 가능하다고 가정하자 (귀류법).

그러면 모든 실수를 자연수에 대응한 표를 다음과 같이 쓸 수 있다.

$a_1 = 0.d_{11}d_{12}d_{13}d_{14}\cdots$ $a_2 = 0.d_{21}d_{22}d_{23}d_{24}\cdots$ $a_3 = 0.d_{31}d_{32}d_{33}d_{34}\cdots$ $\vdots$

이제 다음 수 $X$를 정의한다.

$X = 0.D_1D_2D_3D_4\cdots, \quad D_i = \begin{cases} 4 & \text{if } d_{ii} = 5 \\ 5 & \text{if } d_{ii} \ne 5 \end{cases}$

$X$는 위 표의 어떤 $a_n$과도 다르다. $a_n$과 $X$는 소수점 $n$번째 자리($d_{nn}$과 $D_n$)에서 반드시 다르기 때문이다.

따라서 $X \in \mathbb{R}_{01}$이지만 표에 존재하지 않는다. 이는 일대일 대응이 가능하다는 가정에 모순이므로,

$|\mathbb{R}_{01}| > |\mathbb{N}|, \quad \therefore |\mathbb{R}| > |\mathbb{N}|$

---

중간 정리

집합	종류	크기
유한 집합 $B = \{0, 1, \ldots, n\}$	유한	$n$
$\mathbb{N},\ \mathbb{Z},\ \mathbb{Q}^+,\ \mathbb{Q},\ \mathbb{Q}^2,\ \ldots$	가산 무한(countably infinite)	$\aleph_0$
$\mathbb{R}$	불가산 무한(uncountably infinite)	$\aleph_1$

가산 무한 집합이란, 원소에 자연수 번호를 붙일 수 있는 집합이다.

---

Power Set: $2^X$

집합 $A$의 모든 부분집합의 집합을 Power Set $2^A$라 한다.

$A = \{1, 2, 3, \ldots, n\} \implies |2^A| = 2^n = 2^{|A|}$

모든 집합 $X$에 대해 $|X| \ne |2^X|$

유한 집합: $|X| = n$이면 $|2^X| = 2^n$이고, $n < 2^n$은 수학적 귀납법으로 쉽게 증명된다.

무한 집합: 귀류법으로 $X$와 $2^X$가 일대일 대응 $f$를 이룬다고 가정하자.

다음 집합 $P$를 정의한다.

$P = \{a \mid a \in X,\ a \notin f(a)\}$

$P$는 $X$의 부분집합이므로 $P \in 2^X$다. 따라서 $f(b) = P$를 만족하는 $b \in X$가 존재해야 한다.

그런데 $b$에 대해 다음 모순이 발생한다.

$b \in P \implies b \notin f(b) = P \implies b \notin P$ $b \notin P \implies b \in f(b) = P \implies b \in P$

$f(b) = P$를 만족하는 $b$가 존재할 수 없으므로, 일대일 대응이 성립하지 않는다.

$\therefore |X| \ne |2^X| \text{ (모든 집합 } X \text{에 대해)}$

이 결과와 앞서 $|\mathbb{R}| = |2^\mathbb{N}|$임을 결합하면, 실수 집합이 자연수 집합의 Power Set과 크기가 같음을 알 수 있다.

---

차원을 늘려도 크기는 같다

직관과 달리, 차원을 높여도 가산·불가산 집합의 크기는 변하지 않는다.

$|\mathbb{Z}| = |\mathbb{Z}^2|$: 2차원 정수 좌표계를 원점에서 나선형으로 돌며 번호를 붙이면 모든 정수 좌표에 자연수를 대응시킬 수 있다.

$|\mathbb{R}| = |\mathbb{R}^2|$: 임의의 실수 $x = 0.d_1d_2d_3d_4\ldots$에 대해, 홀수·짝수 자리를 분리해 두 실수를 만든다.

$p = 0.d_1d_3d_5\ldots, \quad q = 0.d_2d_4d_6\ldots$

이 방식으로 $\mathbb{R}$의 원소를 $\mathbb{R}^2$의 원소와 일대일 대응시킬 수 있다.

---

확률적 해석: 유리수를 뽑을 확률

$[0, 1)$에서 임의의 실수 $x$를 뽑을 때, $x$가 유리수일 확률은 0 이다.

유리수는 가산 무한, 실수는 불가산 무한이기 때문이다. 유리수 집합이 실수 집합에 비해 압도적으로 작아서, 확률 측도(measure)로 따지면 $0$이 된다. (만약 양수라면, 가산 무한 개의 유리수 각각에 같은 확률을 부여하면 전체 확률이 무한대가 되어 모순이 생긴다.)

Cantor Set

$[0, 1)$에서 중간 $\frac{1}{3}$ 구간을 계속 제거해나가는 Cantor Set을 생각해보자. 제거되는 구간의 길이의 합은 등비급수의 합으로,

$\frac{1/3}{1 - 2/3} = 1$

즉 길이(measure)가 $1$인 구간이 모두 제거되는데도, 제거되지 않는 점들이 여전히 존재한다. 이 점들은 3진수로 표현했을 때 $1$이 한 번도 등장하지 않는 수들이다.

이 살아남은 수들에서 모든 2를 1로 바꾸면 $[0,1)$의 2진수 표현 전체와 일대일 대응된다. 즉, Cantor Set의 크기는 $|\mathbb{R}|$과 같다 — 길이는 0이지만 원소의 개수는 실수 전체만큼 많다.

---