집합의 크기(cardinality)

정의1 집합 $S$가 자연수의 일부분 $\{1,2,3,\cdots,n\}$과 사이에 전단사 함수(일대일 대응)가 존재하면 집합 $S$는 유한(finite) 집합이고 $n$이 집합의 크기(cardinality)이다. 기호로는 $|S|=n$ 또는 $n(S)=n$으로 적는다. 유한이 아니면 무한(infinite) 집합이다.

정의2 $|A|=|B|\iff \exists f:A\rightarrow B ;\;f$는 전단사 함수(일대일 대응)

정의3 어떤 집합 $S$와 $\mathbb{N}$ 사이에 전단사 함수(일대일 대응)이 존재한다면 번호를 매길 수 있는 (denumerable 또는 enumerable) 집합이라고 한다. 유한집합이거나 번호를 매길 수 있을 때 셀 수 있다(countable)고 하고 자연수와 사이에 전단사 함수(일대일 대응)가 존재하지 않는다면 셀 수 없다(uncountable)고 한다.

무한집합인 전체 자연수의 집합의 크기는 $|\mathbb{N}|=\aleph_0$로 적는다.

($\aleph$는 히브리말 알파벳 첫 번째 글자로 $\aleph_0$는 알레프 널(aleph null)이라고 읽는다.)

보기

1. 모든 양의 홀수의 집합 $S=\{y|y=2n-1,\;n \in \mathbb{N}\}$은 셀 수 있는 집합이다.
$f:\mathbb{N}\rightarrow S :\;\;f(n)=2n-1$이라고 하면
1) $\forall m,n \in S\;\;f(m)=f(n) \Rightarrow 2m-1=2n-1 \Rightarrow m=n$이므로 함수 $f$는 단사 함수(one-to-one)이다.
2) $\forall t\in S$에 대하여 $t=2k-1=f(k)$이므로 $f(\mathbb{N})=S$이다. 다시 말해 함수 $f$는 전사 함수(onto)이다.
1) 2)에 의해 함수 $f$는 전단사 함수(one-to-one correspondence)이다.
$\therefore\;\;|S|=\aleph_0$이다.

2. 모든 양의 유리수의 집합 $\mathbb{Q}^+$은 셀 수 있는 집합이다. 왼쪽 그림은 유리수를 배열하는 방법을 나타낸 것이다. 모든 유리수는 기약분수로 적을 수 있다.

먼저 분모가 $n$인 모든 기약분수를 $n$번 째 줄에 적는다.

동그라미 친 것은 이들 가운데 중복되는 것을 제외한 것이다.

화살표를 따라 다시 배열하면

$$\frac{1}{1} ,\frac{1}{2}, \frac{2}{1},\frac{3}{1},\frac{1}{3}, \frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1},\cdots$$

이다. 

$\displaystyle{\frac{b}{a}}$에서 분모와 분자의 합 $a+b$가 같은 것끼리 차례로 적은 수열로 볼 수 있다. 

그러므로 $|\mathbb{Q}^+|=\aleph_0$이다.

이 그림에서 아래 정리를 쉽게 이해할 수 있다.

정리 $A$와 $B$가 셀 수 있으면 $A\cup B$도 셀 수 있다. 셀 수 있는 집합 유한 개의 합집합은 셀 수 있는 집합이다.

정리 셀 수 있는 집합의 부분집합은 모두 셀 수 있는 집합이다.

3. 실수 전체의 집합 $\mathbb{R}$은 셀 수 없는 집합이다.

$S=\{x|0<x<1, x\in \mathbb{R}\}$이 셀 수 있는 집합이라고 하면 번호를 매길 수 있다.

소수 표현을 적고 번호를 매겼다고 하자. $a_{ij} \in\{1,2,3,\cdots,9\}\;\; (i,j\in\mathbb{N})$

$x_1=0.a_{11}a_{12}a_{13}a_{14}a_{15}\cdots$

$x_2=0.a_{21}a_{22}a_{23}a_{24}a_{25}\cdots$

$x_3=0.a_{31}a_{32}a_{33}a_{34}a_{35}\cdots$

$\quad\vdots$

$x_n=0.a_{n1}a_{n2}a_{n3}a_{n4}a_{n5}cdots$

$\quad\vdots$

이제 새로운 소수표현을 생각하자.

$x=0.a_1 a_2 a_3 a_4\cdot$

$a_i=\cases{ 4\;\;a_{ii}\not=4 \\ 5\;\;a_{ii}=4}$

$x$는 $\forall n\in\mathbb{N},\;\;x\not= x_n$이다.($\because\;a_i \not=a_{ii}$)

모든 실수는 단 하나의 소수표현을 가지고 있으므로 $S$가 셀 수 있다는 가정이 거짓이다.

셀 수 없는 부분집합을 가지는 집합은 셀 수 없는 집합이므로 실수의 집합 $\mathbb{R}$은 셀 수 없는 집합이다.

연속체 가설(continuum hypothesis)

양의 정수의 집합 $\mathbb{Z}^+$의 멱집합과 실수의 집합 $\mathbb{R}$은 같은 크기를 갖는다. 위 증명을 참고하자. 양의 정수의 멱집합은 소수표현과 같은 크기이다. $|\mathcal{P}(\mathbb{Z}^+)|=|\mathbb{R}|=c$($c$는 실수 집합의 크기)

참고 멱집합(power set) 어떤 집합 $A$의 모든 집합을 원소로 가지는 집합을 집합 $A$의 멱집합이라고 하고 $\mathcal{P}(A)$로 적는다.

예 $A=\{1,2\}$라면 $\mathcal{P}(A)=\{\phi,\{1\},\{2\},\{1,2\}\}$이다. 한편 멱집합의 크기는 $\displaystyle{|\mathcal{P}(A)|=2^{|A|}}$이다.

여러 가지로 무한집합의 크기는 독특하다. 자연수 집합과 정수의 집합의 크기가 같다. 전체가 부분보다 크다는 공리가 성립하지 않는다. 오죽하면 칸토어마저 신의 영역을 침범한 것이 아닐까 걱정하였을까?

칸토어는 어떤 집합의 크기는 그 집합의 멱집합의 크기보다 항상 작음을 증명하였다.

$|\mathbb{Z}^+|<|\mathcal{P}(\mathbb{Z}^+)|$

다시 적으면

$\displaystyle{\aleph_0 <2^{\aleph_0}}$

$\aleph_0$과 $c$ 사이에 기수(집합의 크기)가 존재하지 않는다는 가설이 연속체 가설이다. 다시 말하면 $\aleph_0<|A|<c$인 집합 $A$가 존재하지 않는다는 가설이다.

무한 집합의 기수로 $\aleph_0 <\aleph_1 <\aleph_2 <\cdots$처럼 무한수열을 만들자. 연속체 가설이 참이라고 가정하면 $c=\aleph_1$이므로 $\displaystyle{2^{\aleph_0}=\aleph_1 =c}$이다.

칸토어가 1877년에 제시한 연속체 가설은 증명되지 않아 아직도 가설에 머물러 있다. 힐베르트가 제시한 "수학에서의 23개 난제" 가운데 첫 번째 문제이기도 하다. 그런데 이 문제는 현대 표준 집합 이론으로는 참인지 거짓인지 증명할 수 없다는 (Zermelo-Fraenkel 공리)가 알려져 있다. 이 공리는 러셀의 역설과 같은 순박한 집합론(naive set theory)의 자기모순을 피하기 위한 것이지만 이것들 역시 집합론에서 다른 공리들을 대체할 수 있는가에 대한 논의는 아직 숙제로 남아 있다.

자연수에 음의 정수를 합쳐도 정수에 분수까지 더한 유리수 집합도 여전히 셀 수 있다. 그런데 무리수를 더하는 순간 셀 수 없게 된다. 역시 무리수다. 유리수는 조밀하지만 틈이 있다. 이 틈을 꽉 채운 완비(complete)에 이르게 해주는 무리수만 완벽하게 파헤칠 수 있다면 실수체를 훤히 들여다 보고 많은 난제를 해결할 수 있을 것이다.