집합의 크기

개요 — 동기·문제의식

"두 집합의 크기가 같다"는 말을 유한집합에서는 그냥 원소 개수를 세서 비교하면 된다. 그런데 무한집합은 셀 수가 없다 — $\mathbb{N}$ 에는 "마지막 원소"가 없는데 어떻게 그 "개수"를 $\mathbb{Z}$ 나 $\mathbb{R}$ 의 "개수"와 비교한단 말인가? 19세기까지 대부분의 수학자(심지어 가우스조차)는 "무한은 그냥 무한이고, 크기 비교는 무의미하다"고 여겼다.

칸토어의 혁명적 통찰은 셈하지 않고 비교하는 법이었다 — 일대일 대응. 두 집합 사이에 전단사가 있으면 "같은 크기"라고 정의하면, 셈이 불가능한 무한집합끼리도 의미 있게 비교할 수 있다. 이 단순한 정의가 폭발적인 결과를 낳는다: $\mathbb{N}$ 과 $\mathbb{Z}$ 와 $\mathbb{Q}$ 는 모두 같은 크기이지만, $\mathbb{R}$ 은 진짜로 더 크다(칸토어의 대각선 논법). "무한에도 서로 다른 크기들이 있다"는 이 발견이 집합론 전체의 출발점이자, 연속체가설이라는 20세기의 가장 깊은 미해결 문제(엄밀히는 독립성이 증명된 문제)로 이어진다.

직관

농도를 비교하는 칸토어의 방법은 마치 콘서트장에서 좌석 수와 관객 수를 일일이 세지 않고도 비교하는 것과 같다 — 모든 관객이 자리에 앉고 빈 좌석이 없다면("전단사"), 좌석 수와 관객 수는 같다. 이 방법의 강점은 무한히 많은 좌석에도 그대로 적용된다는 점이다.

대각선 논법의 직관은 "어떤 목록도 모든 것을 담을 수 없다"는 것이다. $[0,1]$ 의 모든 실수를 무한 목록으로 나열했다고 가정하자. 그 목록의 $n$ 번째 수의 소수점 $n$ 번째 자리를 일부러 다르게 바꿔가며 새로운 수를 하나 만들면, 이 새 수는 목록의 어느 항과도 적어도 한 자리가 다르므로 목록에 없다 — 그런데 그 새 수도 $[0,1]$ 의 원소다. 모순. 이 트릭의 핵심은 "목록 자체를 입력으로 받아 그 목록에 없는 원소를 만들어내는" 대각선화 메커니즘이며, 같은 발상이 괴델의 불완전성 정리, 정지 문제의 결정불가능성에도 그대로 재등장한다.

정의

• 같은 농도(equinumerous) $A\approx B$: $A$ 와 $B$ 사이에 전단사(일대일대응)가 존재.¹ 칸토어의 핵심 통찰은 무한 비교의 올바른 도구가 셈이 아니라 일대일 대응이라는 것.²
• 농도 비교 $|A|\le|B|$: $A$ 에서 $B$ 로의 단사함수가 존재. $|A|<|B|$: $|A|\le|B|$ 이고 $|A|\ne|B|$.
• 가산(countable): $A\approx\mathbb{N}$(가산무한, countably infinite)이거나 유한. 비가산(uncountable): 무한이면서 가산이 아님.
• $\aleph_0=|\mathbb{N}|$: 가장 작은 무한 농도. 연속체 $\mathfrak{c}=|\mathbb{R}|=2^{\aleph_0}$.
• 농도와 기수의 관계: 엄밀히 "$|A|$"는 (선택공리 하에서) $A$ 와 같은 농도인 유일한 초기 순서수(기수)로 정의된다. 이 페이지는 AC를 가정하지 않고도 성립하는 농도의 기본 성질(특히 Cantor–Schröder–Bernstein)에 초점을 둔다.

주요 정리

정리 (Cantor–Schröder–Bernstein, CSB). $|A|\le|B|$ 이고 $|B|\le|A|$ 이면 $|A|=|B|$.³ (AC 없이 ZF만으로 성립 — 양방향 단사 두 개로부터 전단사를 구성할 수 있다는 점이 중요.)

정리 (칸토어 정리, Cantor's Theorem). 모든 집합 $A$ 에 대해 $|A|<|\mathcal{P}(A)|$.⁴

따름정리 (실수의 비가산성). $|\mathbb{R}|=2^{\aleph_0}=|\mathcal{P}(\mathbb{N})|>\aleph_0=|\mathbb{N}|$ — $\mathbb{R}$ 은 비가산이다. 칸토어 정리를 반복 적용하면 $\aleph_0<2^{\aleph_0}<2^{2^{\aleph_0}}<\cdots$ 라는 무한히 많은 서로 다른 무한 농도의 위계가 끝없이 이어진다는 것까지 알 수 있다 — "무한은 다 똑같다"는 직관이 완전히 무너지는 지점.

정리 (가산집합의 성질). 가산집합의 부분집합은 가산이다(전사·단사의 합성으로 직접 확인). 두 가산집합의 합집합·곱은 가산이다(가산 AC 또는 명시적 짝지음 함수로). 가산개의 가산집합의 합집합도 가산이다(가산 AC 필요).

정리 (무한집합은 가산 부분집합을 가진다). $A$ 가 무한이면 $A$ 는 $\mathbb{N}$ 과 농도가 같은 부분집합을 가진다(즉 $\aleph_0\le|A|$).⁵

정리 (유한집합과 무한집합의 본질적 구분, Dedekind-무한). $A$ 가 무한일 필요충분조건은 $A$ 가 자기 자신의 진부분집합과 같은 농도를 가지는 것이다(Dedekind의 무한 정의).⁶ 예를 들어 $\mathbb{N}\approx\{2,4,6,\dots\}$($n\mapsto 2n$)이지만 $\{2,4,\dots\}\subsetneq\mathbb{N}$ — 유한집합에서는 결코 일어날 수 없는 현상("부분이 전체와 같은 크기")이 무한집합의 본질적 특징이다.

예제

예제 1 (가산: $\mathbb{Z}$, $\mathbb{Q}$). $\mathbb{Z}$: $0,1,-1,2,-2,\dots$ 순서로 $\mathbb{N}$ 과 대응시키면(명시적 식 $f(n)=(-1)^n\lceil n/2\rceil$) 전단사 → 가산. $\mathbb{Q}$: 분수 $p/q$ 를 격자점 $(p,q)$ 와 대응시키고 대각선 순서로 나열(중복 제거)하면 가산.

예제 2 ($\mathbb{R}$ 비가산, 대각선 직접 실행). $[0,1]$ 의 모든 수를 $r_1,r_2,r_3,\dots$ 로 나열했다 가정하고, 각 $r_n$ 의 소수전개 $n$ 번째 자리를 보자. 새로운 수 $x$ 를 $x$ 의 $n$ 번째 자리가 $r_n$ 의 $n$ 번째 자리와 다르도록(예: $5$ 면 $4$, 아니면 $5$) 정의하면, $x$ 는 어떤 $r_n$ 과도 $n$ 번째 자리에서 다르므로 목록에 없다 — 그런데 $x\in[0,1]$. 모순. (소수전개 중복 표현 — $0.4999\dots=0.5000\dots$ — 문제는 자리 선택을 $\{4,5\}$ 처럼 $0,9$ 를 피해 잡으면 회피 가능.)

예제 3 (의외로 같은 농도). $|(0,1)|=|\mathbb{R}|$($\tan(\pi(x-\tfrac12))$ 같은 전단사로). 놀랍게도 $|\mathbb{R}|=|\mathbb{R}^2|$ — 두 좌표의 소수전개를 한 자리씩 번갈아 엮으면 단사를 양방향 만들 수 있고 CSB로 전단사 존재가 보장된다(차원이 "농도"라는 척도에서는 무의미해지는 지점). $|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|=2^{\aleph_0}$(이진전개로 부분집합 ↔ 0/1 수열 ↔ 실수).

예제 4 (CSB의 위력 — $[0,1]\approx(0,1)$). $(0,1)\hookrightarrow[0,1]$ 은 자명한 포함. 반대 방향 $[0,1]\hookrightarrow(0,1)$ 은 $x\mapsto(x+1)/3$ 으로 단사(상이 $[1/3,2/3]\subset(0,1)$). 양방향 단사가 있으니 CSB로 $|[0,1]|=|(0,1)|$ — 직접 전단사를 구성하지 않고도 농도가 같음을 증명한 전형적 예.

예제 5 (대수적 수는 가산, 따라서 초월수가 압도적으로 많다). 정수계수 다항식 전체는 가산(차수·계수의 유한 튜플의 가산합집합)이고, 각 다항식의 근은 유한 개이므로 대수적 수 전체는 가산집합들의 가산합집합 → 가산. $\mathbb{R}$ 은 비가산이므로 $\mathbb{R}\setminus(\text{대수적 수})$(초월수)는 반드시 비가산 — 사실상 "거의 모든" 실수가 초월수라는, 직접 구성 없이 농도 비교만으로 얻는 강력한 존재 증명.

예제 6 (무한 수열 공간). $\mathbb{N}^{\mathbb{N}}$(자연수의 무한 수열 전체)는 비가산이다 — $2^{\mathbb{N}}\subseteq\mathbb{N}^{\mathbb{N}}$ 이므로 $|2^{\mathbb{N}}|\le|\mathbb{N}^{\mathbb{N}}|$ 이고, 또 $\mathbb{N}^{\mathbb{N}}\hookrightarrow\mathcal{P}(\mathbb{N}\times\mathbb{N})$(그래프로) 단사이므로 $|\mathbb{N}^{\mathbb{N}}|\le 2^{\aleph_0}$ — CSB로 $|\mathbb{N}^{\mathbb{N}}|=2^{\aleph_0}=\mathfrak{c}$.

예제 7 (Dedekind-무한 직접 확인 — 힐베르트 호텔). "객실이 $\mathbb{N}$ 으로 번호 매겨진 호텔이 만실이어도 새 손님을 받을 수 있다"는 힐베르트 호텔 이야기는 정확히 $\mathbb{N}\approx\mathbb{N}\cup\{*\}$(새 손님 $*$ 를 $0$ 번 방에, 기존 $n$ 번 손님을 $n+1$ 번 방으로 이동)를 말로 푼 것 — Dedekind-무한성의 가장 유명한 대중적 표현.

예제 8 (가산집합의 유한 곱은 가산, 그러나 가산 곱은 비가산일 수 있음의 대조). $\mathbb{N}^k$($k$ 고정 유한)는 칸토어 짝지음을 반복해서 가산임을 보일 수 있지만, $\mathbb{N}^{\mathbb{N}}$(가산 개의 곱)은 예제 6처럼 비가산이다 — "유한 번 곱은 가산성을 보존하지만 가산 무한 번 곱은 보존하지 않는다"는 경계가 정확히 $\aleph_0$ 과 $2^{\aleph_0}$ 사이의 전환점.

흔한 오해와 함정

• "무한은 다 똑같은 크기다" — 칸토어 정리가 정확히 이 직관을 반박한다. $|A|<|\mathcal{P}(A)|$ 가 모든 집합(유한이든 무한이든)에 성립하므로, 무한 농도조차 끝없는 위계를 이룬다.
• "$\mathbb{R}^2$ 이 $\mathbb{R}$ 보다 크다" — 직관적으로 "2차원이 1차원보다 크다"고 느끼기 쉽지만 농도(집합으로서의 크기)는 차원과 무관하다. $|\mathbb{R}|=|\mathbb{R}^2|=|\mathbb{R}^n|=|\mathbb{R}^{\mathbb{N}}|$ 까지도 모두 같다(단, $\mathbb{R}^{\mathbb{N}}$ 의 경우 약간의 계산이 더 필요하지만 결과는 $2^{\aleph_0}$).
• "단사가 있으면 전사도 있어야 농도가 같다고 말할 수 있다" — CSB 정리의 핵심은 정확히 그 반대다: 양방향 단사(전단사 아님)만 있으면 충분하고, 거기서 전단사의 존재를 증명해낸다(CSB의 증명 자체가 그 구성법).
• "대각선 논법은 $\mathbb{R}$ 에만 적용된다" — 같은 논법이 칸토어 정리 일반(임의의 $A$ 에 대해 $|A|<|\mathcal{P}(A)|$), 괴델 불완전성 정리(자기 자신을 서술하는 명제), 정지 문제(자기 자신의 정지 여부를 묻는 프로그램)에서도 동일한 구조로 재등장한다 — "목록/함수 자체를 입력으로 받아 그것에서 벗어나는 대상을 만든다"는 패턴.
• "비가산이면 곧 연속체 농도다" — 아니다. 칸토어 정리에 의해 $2^{\aleph_0}<2^{2^{\aleph_0}}<\cdots$ 등 더 큰 비가산 농도도 있고, 또 $\aleph_0$ 과 $2^{\aleph_0}$ 사이에 다른 농도가 있는지는 연속체가설의 내용으로 ZFC와 독립이다.

큰 그림 / 연결

농도는 전단사를 통해 정의되는, 집합론에서 가장 먼저 마주치는 비자명한 무한 개념이다. 기수는 이 직관적인 "농도" 개념을 (AC 하에서) 정렬가능성을 이용해 정확한 집합론적 대상(초기 순서수)으로 형식화한다. 칸토어 정리가 보장하는 끝없는 위계는 기수 산술에서 $2^\kappa$ 라는 지수 연산이 왜 그렇게 까다로운지(König 정리, 공종도 제약)의 출발점이고, $\aleph_0$ 과 $2^{\aleph_0}$ 사이의 빈틈에 다른 농도가 있는지를 묻는 것이 연속체가설이다. 더 멀리는 누적 위계 $V_\alpha$ 의 각 단계가 멱집합을 취하면서 농도가 폭발적으로 커지는 것도 칸토어 정리의 직접적 귀결이다.

다른 분야와의 연결: analysis 위키의 countability는 정확히 같은 개념(가산성)을 해석학적 맥락(르베그 측도 0인 집합, Baire 범주 등)에서 다룬다 — 두 위키가 같은 정리를 공유하는 대표 사례다. 위상수학에서 가산 기저를 갖는 공간(제2가산 공간)의 이론, 컴퓨터과학에서 "셀 수 있는 만큼만 계산 가능한 함수가 있다"는 계산가능성 이론의 기초 논증도 모두 이 페이지의 대각선 논법에 뿌리를 둔다.

연습문제

1. $\mathbb{N}\times\mathbb{N}$ 이 가산임을 보여라(Cantor 짝지음 $\langle m,n\rangle$).
2. 대각선 논법으로 $\mathcal{P}(\mathbb{N})$ 이 비가산임을 보여라.
3. $|(0,1)|=|[0,1]|$ 을 CSB 또는 직접 보여라.
4. 대수적 수 전체가 가산임을 보여라(따라서 초월수가 비가산 존재).
5. $|\mathbb{R}|=|\mathbb{R}^2|$ 의 아이디어를 설명하라(소수전개 엮기).
6. CSB 정리를 사용해 $|[0,1]\times[0,1]|=|[0,1]|$ 을 보여라(단사 두 개 구성).
7. $A$ 가 무한집합이면 $|A|=|A\times\{0,1\}|$(AC를 가정하지 않고 $A$ 가 가산일 때 직접, 일반적인 경우는 cardinal arithmetic 예고)임을 가산집합에 대해 확인하라.
8. 칸토어 정리의 증명에서 대각선 집합 $D=\{x\in A:x\notin f(x)\}$ 가 왜 "$f$ 의 어떤 값도 될 수 없는" 집합인지 한 문장으로 설명하라.
9. 힐베르트 호텔에서 "무한 명의 새 손님"($\mathbb{N}$ 명)이 와도 자리를 만들 수 있음을 보여라(기존 $n$ 번 손님을 $2n$ 번 방으로 옮기는 식).
10. Dedekind-무한의 정의("자기 자신의 진부분집합과 같은 농도")를 이용해 유한집합은 결코 자신의 진부분집합과 같은 농도를 가질 수 없음을 (직관적으로) 논하라 — 왜 이것이 "유한"의 본질적 특징인가?

관련 개념

• relations and functions — 전단사로 농도 정의
• sets and classes — 멱집합·집합 연산이 농도 비교의 토대
• cardinals — 농도를 기수로 형식화
• continuum hypothesis — $2^{\aleph_0}$ 은 어디?
• cardinal arithmetic — $2^{\aleph_0}$ 등 기수 지수
• axiom of choice — 가산 AC로 가산합집합의 가산성
• analysis 위키 countability — 동일 개념(해석학의 가산성), 온톨로지 same-concept