무한집합의 ‘크기’를 어떻게 비교할까? 칸토어는 일대일대응을 기준으로 삼았고, 놀랍게도 무한에도 크기가 다른 것들이 있음을 보였다. 자연수와 유리수는 같은 크기이지만, 실수는 그보다 크다.
핵심 개념
- $A$와 $B$ 사이에 전단사가 있으면 기수가 같다 $|A|=|B|$
- 가산집합: 자연수 전체와 기수가 같은(또는 유한한) 집합. 원소에 번호를 붙여 나열할 수 있다.
- 비가산집합: 가산이 아닌 무한집합
핵심 정리
- 정수 $\mathbb Z$와 유리수 $\mathbb Q$는 가산이다.
- 실수 $\mathbb R$은 비가산이다. (칸토어의 대각선 논법)
- 칸토어 정리: 어떤 집합 $A$도 멱집합 $\mathcal P(A)$와 기수가 같지 않다. 따라서 무한의 크기는 끝없이 커진다.
증명 보기
$\mathbb Z$. $0,1,-1,2,-2,\dots$로 번호를 붙인다.
$\mathbb Q$. 양의 유리수 $\frac pq$를 $p+q=2,3,4,\dots$ 순서로 나열하고(같은 합에서는 $p$가 작은 순), 이미 나온 값(예: $\frac24=\frac12$)은 건너뛴다. 모든 양의 유리수가 언젠가 나타나므로 번호를 붙일 수 있다. 음수와 $0$은 $\mathbb Z$처럼 끼워 넣는다.
$\mathbb R$은 비가산 (대각선 논법). $(0,1)$의 실수를 모두 나열할 수 있다고 가정하고 $x_1,x_2,\dots$의 소수 전개를 쓴다. 새로운 수 $y=0.d_1d_2\cdots$를 만들되, $d_n$은 $x_n$의 $n$번째 자리 숫자와 다르게(예: 그 숫자가 $5$가 아니면 $5$, $5$이면 $6$) 고른다. 그러면 $y$는 모든 $n$에 대해 $x_n$과 $n$번째 자리가 다르므로 목록의 어떤 수와도 같지 않다. 목록이 모든 실수를 담는다는 가정에 모순이다. ($0$과 $9$를 피하면 $0.4999\cdots=0.5$ 같은 두 가지 표현 문제도 생기지 않는다.)
칸토어 정리. 전사 $f:A\to\mathcal P(A)$가 있다고 하자. $B=\{a\in A: a\notin f(a)\}$를 생각하면 $B=f(b)$인 $b$가 있다. $b\in B$이면 정의에 의해 $b\notin f(b)=B$이고, $b\notin B$이면 $b\in f(b)=B$이다. 어느 쪽도 모순이므로 전사가 없다. $\blacksquare$
예제
- 힐베르트 호텔: 객실이 무한히 많고 꽉 찬 호텔에도, 모든 손님을 $n$호에서 $n+1$호로 옮기면 새 손님을 받을 수 있다. $|\mathbb N|=|\mathbb N\setminus\{1\}|$
- $(0,1)$과 $\mathbb R$은 기수가 같다: $\tan\left(\pi x-\frac\pi2\right)$
확인 문제
짝수 전체의 집합과 자연수 전체의 집합은 기수가 같은가?
풀이 보기
같다. $f(n)=2n$은 자연수에서 (양의) 짝수로 가는 전단사이다. 무한집합은 자기 자신의 진부분집합과 기수가 같을 수 있으며, 이것이 무한집합의 특징이다.
정리
- 기수가 같다 = 전단사가 있다
- $|\mathbb N|=|\mathbb Z|=|\mathbb Q|<|\mathbb R|$, 그리고 $|A|<|\mathcal P(A)|$
