무한집합과 기수

무한집합의 ‘크기’를 어떻게 비교할까? 칸토어는 일대일대응을 기준으로 삼았고, 놀랍게도 무한에도 크기가 다른 것들이 있음을 보였다. 자연수와 유리수는 같은 크기이지만, 실수는 그보다 크다.

핵심 개념

  • $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)|$
알림: 보호된 콘텐츠입니다.