집합의 크기(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). 집합의 모든 원소에 자연수 번호를 붙일 수 있다면 셀 수 있다고 한다.

이 글에서 $\mathbb{N} = \{0, 1, 2, \ldots\}$로 둔다.

원소를 하나 덧붙여도 크기가 그대로임을 보자. $\mathbb{N}$에 없는 기호 $\star$를 가져와 $X = \{\star\} \cup \mathbb{N}$이라 하면, 다음 함수가 $X$에서 $\mathbb{N}$으로 가는 일대일 대응이다.

$$f(\star) = 0, \qquad f(n) = n + 1$$

$\star$가 맨 앞자리를 가져가고 나머지가 한 칸씩 밀린다. 원소 하나가 더 있어도 무한집합의 크기는 변하지 않는다.

---

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

정수 집합도 자연수 집합과 크기가 같다. 자연수 하나에 정수 하나를 짝지어 주는 함수를 직접 적을 수 있다.

$$f(0) = 0, \qquad f(2n-1) = n, \qquad f(2n) = -n \quad (n \ge 1)$$

홀수 번호는 양의 정수로, 짝수 번호는 음의 정수로 보낸다. 번호 순서대로 늘어놓으면 이렇게 된다.

$$0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ \ldots$$

양의 정수 $n$은 번호 $2n-1$에서, 음의 정수 $-n$은 번호 $2n$에서 딱 한 번씩 나오고 $0$은 번호 $0$에서 나온다. 빠지는 정수도, 두 번 나오는 정수도 없으므로 $f$는 일대일 대응이다. 따라서

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

---

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

모든 양의 유리수는 기약분수 $\frac{p}{q}$로 꼭 한 가지 꼴로 적힌다. 그러니 $\gcd(p, q) = 1$인 자연수 쌍만 세면 된다.

분자와 분모의 합 $p + q$가 같은 것끼리 묶고, 묶음 안에서는 분자가 작은 것부터 놓는다. 합이 정해지면 쌍의 개수가 유한하므로 한 묶음을 끝내고 다음으로 넘어갈 수 있다.

$$\mathbb{Q}^+ = \left\{\ \frac{1}{1}\ \middle|\ \frac{1}{2},\ \frac{2}{1}\ \middle|\ \frac{1}{3},\ \frac{3}{1}\ \middle|\ \frac{1}{4},\ \frac{2}{3},\ \frac{3}{2},\ \frac{4}{1}\ \middle|\ \ldots\right\}$$

세로줄이 $p + q = 2, 3, 4, 5$ 묶음의 경계다. $p + q = 4$ 묶음에 $\frac{2}{2}$가 없는 이유는 기약분수가 아니기 때문이다. 그 값은 이미 $\frac{1}{1}$로 세었다.

모든 양의 유리수가 정확히 한 번씩 나온다. 어떤 양의 유리수를 기약분수로 적으면 $p$와 $q$가 하나로 정해지고, 따라서 $p + q$가 정해져 속할 묶음이 하나로 정해지며, 그 묶음 안에서는 분자 $p$가 자리를 하나로 정하기 때문이다.

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

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

그림의 $\mathbb{Q}^+$ 열거 순서는 본문처럼 분자와 분모의 합으로 묶은 순서와 조금 다르지만, 중복을 제외하며 모든 양의 유리수를 셀 수 있음을 보인다는 핵심은 같다.

---

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

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

여기서 $\mathfrak{c}=2^{\aleph_0}=|\mathbb{R}|$는 연속체의 크기이며, $\mathfrak{c}=\aleph_1$이라고 가정하지 않는다.

$$|\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)	$\mathfrak{c}$

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

---

Power Set: $2^X$

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

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

모든 집합 $X$에 대해 $|X| < |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$가 존재할 수 없으므로, 일대일 대응이 성립하지 않는다. 더 정확히 말하면 $X$에서 $2^X$로 가는 전사 함수가 없다. 어떤 $f$를 가져와도 $P$가 상에서 빠지기 때문이다.

여기까지로는 $|X| \ne |2^X|$까지만 얻는다. 어느 쪽이 큰지는 아직 말하지 않았으므로 한쪽을 마저 보인다. 원소 하나를 그것만 담은 집합으로 보내는 함수

$$x \mapsto \{x\}$$

는 $X$에서 $2^X$로 가는 단사 함수이므로 $|X| \le |2^X|$다. 크기가 같지 않다는 앞의 결과와 합치면

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

이 결과와 뒤의 Cantor Set 절에서 볼 수 있듯 $|\mathbb{R}| = |2^\mathbb{N}|$라는 관점을 결합하면, 실수 집합이 자연수 집합의 Power Set과 크기가 같음을 알 수 있다.

---

차원을 늘려도 크기는 같다

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

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

$|\mathbb{R}| = |\mathbb{R}^2|$: 자릿수를 번갈아 끼우는 방법이 자주 쓰인다. 두 실수 $p = 0.p_1p_2p_3\ldots$와 $q = 0.q_1q_2q_3\ldots$를 한 실수로 엮는 것이다.

$$(p,\ q) \ \longmapsto\ 0.p_1q_1p_2q_2p_3q_3\ldots$$

그런데 이대로는 일대일 대응이 아니다. 소수 표현이 하나가 아니기 때문이다. $0.4999\ldots$와 $0.5000\ldots$은 같은 실수인데 어느 표현을 넣느냐에 따라 결과가 달라진다.

먼저 표현을 하나로 고정한다. $9$가 끝없이 이어지는 표현을 버리고 유한 자리로 끝나는 쪽만 쓰기로 하면 실수마다 표현이 하나로 정해지고, 이 사상은 단사가 된다. 다만 전사는 아니다. $0.191919\ldots$처럼 홀수 자리만 뽑으면 $9$가 무한히 이어지는 값은 결과로 나올 수 없어서다.

전사를 억지로 만들 필요는 없다. 반대 방향에도 단사가 있기 때문이다. $x \mapsto (x, 0)$이 $[0,1)$에서 $[0,1)^2$로 가는 단사다. 양쪽에 단사가 있으면 슈뢰더·베른슈타인 정리가 일대일 대응의 존재를 보장한다. $\mathbb{R}$과 $[0,1)$의 크기가 같다는 것도 같은 방식으로 얻으므로, 결론은 $|\mathbb{R}| = |\mathbb{R}^2|$이다.

---

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

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

먼저 「임의로 뽑는다」가 무슨 뜻인지 정해야 한다. 여기서는 $[0,1)$ 위의 균등분포, 곧 구간의 확률을 그 구간의 길이로 재는 르베그 측도를 쓴다.

이 약속이 없으면 확률을 말할 수 없다. 가산이라는 사실만으로는 확률이 $0$이 되지 않기 때문이다. 이를테면 $\frac{1}{2}$ 하나에 확률을 몰아주는 분포를 잡으면 유리수를 뽑을 확률은 $1$이다. 결론은 유리수 집합의 크기가 아니라 어떤 분포를 쓰느냐에서 나온다.

균등분포에서는 길이가 곧 확률이므로, 유리수 전체를 얼마나 작은 총 길이로 덮을 수 있는지 물으면 된다. 유리수가 가산이라는 사실은 여기서 쓰인다. 나열할 수 있어야 하나씩 덮을 수 있기 때문이다.

유리수를 $q_1, q_2, \ldots$로 나열한 뒤 각 $q_n$을 길이 $\varepsilon/2^n$인 구간으로 덮자. 전체 길이는

$$\sum_{n=1}^{\infty}\frac{\varepsilon}{2^n} = \varepsilon$$

이다. $\varepsilon$은 얼마든지 작게 잡을 수 있으므로 유리수 전체를 덮는 길이는 어떤 양수보다도 작다. 따라서 유리수를 뽑을 확률은 $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$만 쓰는 무한 수열이 된다. 이 바꿔치기는 수열끼리는 흠 없는 일대일 대응이다. 자리마다 $0 \leftrightarrow 0$, $2 \leftrightarrow 1$로 짝지어질 뿐이기 때문이다.

$$|\text{Cantor Set}| = |\{0,2\}^{\mathbb{N}}| = |\{0,1\}^{\mathbb{N}}| = |2^{\mathbb{N}}|$$

걸리는 곳은 수열을 실수로 읽는 마지막 단계뿐이다. $0.0111\ldots_2$과 $0.1000\ldots_2$처럼 서로 다른 수열이 같은 실수를 가리키는 경우가 있어 읽기는 일대일이 아니다. 그래도 결론은 흔들리지 않는다. 읽기는 전사이므로 $|2^{\mathbb{N}}| \ge |[0,1)|$이고, 실수를 표현 하나로 고정해 되돌리면 반대 방향 단사가 나오므로 슈뢰더·베른슈타인 정리가 $|2^{\mathbb{N}}| = |\mathbb{R}|$을 준다.

즉 Cantor Set의 크기는 $|\mathbb{R}|$과 같다 — 길이는 0이지만 원소의 개수는 실수 전체만큼 많다.

---