수학/집합론

[집합의 크기] ch3. 유리수 집합과 실수 집합의 크기

김한결 2022. 11. 23. 02:14

이전 읽을거리)

[집합론 기초] ch4. 논리 기호

[FTC의 엄밀한 증명] ch2. 완비성 공리

[FTC의 엄밀한 증명] ch4. 극한의 성질 1

ch2. 가산집합과 비가산집합

유리수 집합의 크기

※ 앞서 증명한 많은 정리를 활용하므로 이전 포스팅을 보고 오길 추천한다.

정리 2.6.으로부터 모든 유리수의 집합 $\mathbb{Q}$ 가 셀 수 있음을 어렵지 않게 알 수 있다. 지난 포스팅의 초반에 언급하였듯이 모든 정수의 집합 $\mathbb{Z}$ 는 셀 수 있다. 여기서부터 시작하자.

Theorem 3.1. $\mathbb{Q}$ 는 셀 수 있다.

Proof. 가산집합인 $\mathbb{Z}$ 에 대해 따름정리 2.3.에 따르면 $\mathbb{Z}\setminus\{0\}$ 도 셀 수 있으므로 정리 2.6.에 따라 집합 $(\mathbb{Z}\setminus\{0\})\times\mathbb{Z}$ 는 셀 수 있다. 그러므로 일대일대응 $\pi:\mathbb{N}\to(\mathbb{Z}\setminus\{0\})\times\mathbb{Z}$ 이 존재한다. 이제 다음과 같이 함수를 정의하자.

$$g:(\mathbb{Z}\setminus\{0\})\times\mathbb{Z}\to\mathbb{Q}\qquad g(n,m)=\frac{m}{n}$$

이는 자명하게 전사함수이므로 합성함수 $h\circ\pi:\mathbb{N}\to\mathbb{Q}$ 는 전사함수이다. 정리 2.1.에 따라 $\mathbb{Q}$ 는 셀 수 있다. $\square$

지금까지 알아본 바에 따르면 $\mathbb{N}$ 도 셀 수 있고, $\mathbb{Z}$ 도 셀 수 있고, $\mathbb{Q}$ 도 셀 수 있다. 그러나 $\mathbb{R}$ 은 셀 수 없다. 본 포스팅에서는 $\mathbb{R}$ 이 어느 집합과 같은 크기를 갖는지 알아볼 것이다. 그 전에 크기가 같다는 것이 무엇인지 정의해야 한다.

Definition. 전단사함수 $A\to B$ 가 존재하면 두 집합 $A$ 와 $B$ 의 크기가 같다고 하며 $A\sim B$ 라고 표기한다.

여기서 표기 "$\sim$" 가 동치관계임은 자명하다. 다시말해 집합 $A,B,C$ 에 대해 다음이 성립한다.

(1) $A\sim A$

(2) $A\sim B\iff B\sim A$

(3) $(A\sim B)\land(B\sim C)\implies A\sim C$

이 표현을 빌려 $\mathbb{N}\sim\mathbb{Z}\sim\mathbb{Q}$ 라고 할 수 있다.

칸토어-베른슈타인 정리

실수 집합의 크기를 알아보기 이전에 하나의 정리를 짚고 넘어가자. 이 정리의 결론은 이해하기 쉽지만, 그 증명은 그 만큼 쉽지는 않다. 먼저 다음의 도움정리부터 확인하자.

Lemma 3.2. 단사함수 $f:A\to B$ 와 $A$ 의 부분집합 $A_0,A_1$ 에 대해 다음이 성립한다.$$f(A_0\setminus A_1)=f(A_0)\setminus f(A_1)$$

Proof. $f(A_0\setminus A_1)$ 의 원소 $b$ 를 생각하자. 이때 $A_0\setminus A_1$ 의 어떤 원소 $a$ 에 대해 $f(a)=b$ 이다. 한편 $a\in A_0$ 이므로 $b\in f(a_0)$ 이다. 반면에 $a\notin A_1$ 이며, 만약 $b\in f(A_1)$ 이라면 어떤 $a_1\in A_1$ 에 대해 $f(a_1)=b$ 이어야 하지만 $a\neq a_1$ 이므로 $f$ 의 단사성에 의해 모순. 따라서 $b\notin f(A_1)$ 이므로 정리하면 다음을 얻는다.

$$f(A_0\setminus A_1)\subset f(A_0)\setminus f(A_1)$$

$f(A_0)\setminus f(A_1)$ 의 원소 $b$ 를 생각하자. 이때 $b\in f(A_0)$ 이므로 어떤 $a\in A_0$ 에 대해 $f(a)=b$ 이다. 한편 $b\notin f(A_1)$ 이므로 모든 $a_1\in A_1$ 에 대해 $f(a_1)=b$ 이며, 따라서 $a\neq A_1$ 을 얻는다. 그러므로 $a\in A_0\setminus A_1$ 이며, $b\in f(A_0\setminus A_1)$ 이므로 정리하면 다음을 얻는다.

$$f(A_0\setminus A_1)\supset f(A_0)\setminus f(A_1)$$

두 결론의 식을 종합하면 원하는 결과를 얻는다. $\square$

Lemma 3.3. $A$ 의 부분집합 $B$ 에 대해 단사함수 $A\to B$ 가 존재하면 $A\sim B$ 이다.

Proof. 먼저 각 자연수 $n$ 에 대해 다음과 같이 정의하자.

$$A_1=A\qquad B_1=B$$

$$A_{n+1}=f(A_n)\qquad B_{n+1}=f(B_n)$$

Step 1. 다음이 성립함을 보이자.

$$A_1\supset B_1\supset A_2\supset B_2\supset\cdots$$

이는 모든 $n\in\mathbb{N}$ 에 대해 $B_n\subset A_n$ , $A_{n+1}\subset B_n$ 이 성립하는 것과 같다. 귀납법으로 증명하자. $n=1$ 의 경우 $B_1\subset A_1$ 은 자명하게 성립하고, $A_2=f(A)$ 이며 $f(A)$ 는 $f$ 의 치역 $B$ 의 부분집합이므로 $A_2\subset B_1$ 도 성립한다. $n-1$ 에 대해 성립한다고 가정하고 $n$ 에 대하여도 성립함을 보이자. 귀납법 가정에 따라 $B_{n-1}\subset A_{n-1}$ 와 $A_n\subset B_{n-1}$ 이므로 $f(B_{n-1})\subset f(A_{n-1})$ 와 $f(A_n)\subset f(B_{n-1})$ 가 성립하며 정의에 따라 $B_n\subset A_n$ 과 $A_{n+1}\subset B_n$ 이다. 귀납법에 따라 원하는 결과를 얻는다.

Step 2. 다음의 집합을 정의하자.

$$C=\{x:\exists n\in\mathbb{N},\;x\in A_n\setminus B_n\}$$

$C$ 는 $A$ 의 부분집합이다. 이제 다음의 함수 $h:A\to B$ 를 정의하자.

$$h(x)=\begin{cases}f(x)&\text{for }x\in C\\x&\text{for }x\in A\setminus C\end{cases}$$

$h$ 가 단사임을 보이자. $A$ 의 서로다른 원소 $a,a'$ 를 생각하자. 만약 둘 다 $C$ 의 원소이면 $f$ 가 단사이므로 $h(a)\neq h(a')$ 이고, 둘 다 $A\setminus C$ 의 원소이면 자명하게 $h(a)\neq h(a')$ 이다. $a\in C$ 이고 $a'\in A\setminus C$ 라고 하자. 어떤 자연수 $n$ 에 대해 $a\in A_n\setminus B_n$ 이다. 특히 $h(a)=f(a)$ 이며 도움정리 3.2.와 정의에 따라

$$f(A_n\setminus B_n)=f(A_n)\setminus f(B_n)=A_{n+1}\setminus B_{n+1}$$

이므로 $f(a)\in A_{n+1}\setminus B_{n+1}$ 이다. 집합 $C$ 의 정의에 따라 $f(a)\in C$ 이므로 $h(a)\in C$ 이다. 한편 $h(a')=a'\notin C$ 이므로 $h(a)\neq h(a')$ 이다. 따라서 $h$ 는 단사이다.

$h$ 가 전사임을 보이자. $B$ 의 임의의 원소 $b$ 를 생각하자. $b$ 는 $C$ 에 속하거나 속하지 않는다. 만약 $b\notin C$ 이면, $B$ 는 $A$ 의 부분집합이므로 $b\in A\setminus C$ 이며 $h(b)=b$ 이므로 $b$ 는 $h$ 의 치역에 속한다. 만약 $b\in C$ 이면 어떤 자연수 $n$ 에 대해 $b\in A_n\setminus B_n$ 이다. 이때 $b$ 는 $B$ 의 원소이기 때문에 $b\notin A\setminus B$ 이므로 $n$ 은 적어도 1이 아니다. 여기서 이미 살펴본 바와 같이 $A_n\setminus B_n=f(A_{n-1}\setminus B_{n-1})$ 이므로 $b\in f(A_{n-1}\setminus B_{n-1})$ 이다. 이는 어떤 $x\in A_{n-1}\setminus B_{n-1}$ 에 대해 $f(x)=b$ 인 것이며, 특히 $x\in C$ 이므로 $h(x)=b$ 이므로 $b$ 는 $h$ 의 치역에 속한다. 따라서 $h$ 는 전사이다. $\square$

이제 편리한 도구가 되어줄 정리를 증명하자.

칸토어-베른슈타인 정리 (Cantor-Bernstein theorem)
단사함수 $f:A\to C$ , $g:C\to A$ 가 존재하면 $A\sim C$ 이다.

Proof. $g$ 는 단사이므로 함수 $h:C\to g(C)$ , $h(c)=g(c)$ 는 전단사이다. 합성함수 $h\circ f$ 는 단사함수 $A\to g(C)$ 이며 $g(C)$ 는 $A$ 의 부분집합이므로 도움정리 3.2.에 따라 $A\sim C$ 를 얻는다. $\square$

실수 집합의 크기

지난 포스팅의 말미에 두 집합 $\mathcal{P}(\mathbb{N})$ 과 $\{0,1\}^\omega$ 는 셀 수 없는 집합임을 알아보았다. 특히 이 두 집합의 크기는 같으며, 쉽게 말하자면 동일한 정도로 셀 수 없이 무한하다는 것을 의미한다. 사실 이는 거의 자명한 성질이다.

Theorem 3.4. $\mathcal{P}(\mathbb{N})$ 와 $\{0,1\}^\omega$ 는 크기가 같다.

Proof. 함수 $f:\mathcal{P}(\mathbb{N})\to\{0,1\}^\omega$ 를 정의하자. 순서쌍의 함수 표기법을 이용하여 각 $f(A)$ 의 n번째 성분을 $f(A)(n)$ 이라고 쓰기로 하자. 다음과 같이 정의하자.

$$f(A)(n)=\begin{cases}1&\text{if }n\in A\\0&\text{if }n\notin A\end{cases}$$

$f$ 가 단사임을 보이자. $\mathbb{N}$ 의 서로다른 부분집합 $A,A'$ 에 대해 $A\setminus A'$ 와 $A'\setminus A$ 둘 중 하나는 공집합이 아니므로, $A\setminus A'$ 가 공집합이 아니라고 하자. 어떤 원소 $n\in A\setminus A'$ 를 생각하자. 함수의 정의에 따라 $f(A)(n)=1$ 이고 $f(A')(n)=0$ 이므로 $f(A)\neq f(A')$ 이다. 따라서 $f$ 는 단사이다.

$f$ 가 전사임을 보이자. 임의의 $\omega$-순서쌍 $\text{x}\in\{0,1\}^\omega$ 를 생각하자. $\text{x}$ 의 n번째 성분 $x_i$ 에 대해 집합 $B=\{n:x_n=1\}$ 를 정의하자. $B$ 는 $\mathbb{N}$ 의 부분집합이므로 $\mathcal{P}(\mathbb{N})$ 이며, 정의에 따라 $f(B)=\text{x}$ 이므로 $\text{x}$ 는 $f$ 의 치역에 속한다. 따라서 $f$ 는 전사이다. $\square$

Lemma 3.5. 단사함수 $\mathbb{R}\to\mathcal{P}(\mathbb{Q})$ 가 존재한다.

※ 아래의 증명에는 유리수의 조밀성이 사용된다. 이에 대해서는 링크의 정리 2.1-2 참고.

Proof. 함수 $f:\mathbb{R}\to\mathcal{P}(\mathbb{Q})$ 를 $f(r)=\{q:q<r\}$ 라고 정의하자. 서로다른 두 실수 $r<r'$ 에 대해 유리수의 조밀성에 따라 $r<q<r'$ 인 유리수 $q$ 가 존재한다. 이때 $q$ 는 $f(r)$ 에는 속하지 않고 $f(r')$ 에는 속하므로 $f(r)\neq f(r')$ 이다. 따라서 $f$ 는 단사이다. $\square$

Lemma 3.6. 단사함수 $\{0,1\}^\omega\to\mathbb{R}$ 이 존재한다.

※ 아래의 증명에는 수열의 극한에 대한 성질이 사용된다. 이에 대해서는 링크의 대수극한정리와 순서극한정리 참고.

Proof. $\{0,1\}^\omega$ 의 원소 $\text{x}$ 를 $(x_1,x_2,\ldots)$ 라고 표기하고 함수 $f$ 를 다음과 같이 정의하자.

$$f:\{0,1\}^\omega\to\mathbb{R}\qquad f(\text{x})=\sum_{k=1}^\infty\frac{x_k}{3^k}$$

$\{0,1\}$ 의 원소의 서로다른 두 $\omega$-순서쌍 $\text{x},\text{x}'$ 를 생각하자. 이때 어떤 자연수 $m$ 에 대해 $x_m\neq x_m'$ 이다. 이러한 원소 중 최소원소 $m$ 을 선택하자. (이러한 선택이 가능함은 정렬원리에 근거한다) 모순을 보이기 위해 $f(\text{x})=f(\text{x}')$ 라고 가정하자. 대수극한정리에 따라 다음이 성립한다.

$$\lim_{n\to\infty}\sum_{k=1}^n\frac{x_k-x_k'}{3^k}=0\quad\left(\because\lim_{n\to\infty}\sum_{k=1}^n\frac{x_k}{3^k}=\lim_{n\to\infty}\sum_{k=1}^n\frac{x_k'}{3^k}\right)$$

이때 $x_m-x_m'\neq 0$ 이고 $m$ 보다 작은 모든 자연수 $n$ 에 대해 $x_n-x_n'=0$ 이므로 급수의 유한합은 다음과 같다.

$$\sum_{k=1}^n\frac{x_k-x_k'}{3^k}=\frac{x_m-x_m'}{3^m}+\sum_{k=m+1}^n\frac{x_k-x_k'}{3^k}$$

각 자연수 $k$ 에 대해 $|x_k-x_k'|\le 1$ 이므로 삼각 부등식에 따 다음이 성립한다.

$$\left|\sum_{k=m+1}^n\frac{x_k-x_k'}{3^k}\right|\le\sum_{k=m+1}^n\left|\frac{x_k-x_k'}{3^k}\right|\le\sum_{k=m+1}^n\frac{1}{3^k}$$

다음과 같이 $n=m+1,m+2,\ldots$ 에 대한 급수의 유한합을 정의하자.

$$S_n=\sum_{k=m+1}^n\frac{1}{3^k}=\frac{1}{3^{m+1}}+\frac{1}{3^{m+2}}+\cdots+\frac{1}{3^n}$$

다음이 성립한다.

$$\frac{S_n}{3}=\frac{1}{3^{m+2}}+\cdots+\frac{1}{3^n}+\frac{1}{3^{n+1}}=S_n-\frac{1}{3^{m+1}}+\frac{1}{3^{n+1}}$$

$$\therefore S_n=\frac{1}{2\cdot 3^m}-\frac{1}{2\cdot 3^n}$$

따라서 다음을 얻는다.

$$\left|\sum_{k=m+1}^n\frac{x_k-x_k'}{3^k}\right|\le\frac{1}{2\cdot 3^m}-\frac{1}{2\cdot 3^n}\tag{1}$$

급수로 다시 돌아오면 다음이 성립해야 한다.

$$\begin{align}0&=\lim_{n\to\infty}\sum_{k=1}^n\frac{x_k-x_k'}{3^k}\\&=\lim_{n\to\infty}\left(\frac{x_m-x_m'}{3^m}+\sum_{k=m+1}^n\frac{x_k-x_k'}{3^k}\right)\\&=\frac{x_m-x_m'}{3^m}+\lim_{n\to\infty}\sum_{k=m+1}^n\frac{x_k-x_k'}{3^k}\end{align}$$

$$\iff \lim_{n\to\infty}\sum_{k=m+1}^n\frac{x_k-x_k'}{3^k}=\frac{x_m'-x_m}{3^m}$$

$$\implies \lim_{n\to\infty}\left|\sum_{k=m+1}^n\frac{x_k-x_k'}{3^k}\right|=\left|\frac{x_m'-x_m}{3^m}\right|\tag{2}$$

식 (2)의 좌변은 식 (1)과 순서극한정리에 따라 다음이 성립한다.

$$\lim_{n\to\infty}\left|\sum_{k=m+1}^n\frac{x_k-x_k'}{3^k}\right|\le\lim_{n\to\infty}\left(\frac{1}{2\cdot 3^m}-\frac{1}{2\cdot 3^n}\right)=\frac{1}{2\cdot 3^m}$$

식 (2)의 우변은 $|x_m'-x_m|=1$ 이므로 $\frac{1}{3^m}$ 이며, 이는 $\frac{1}{2\cdot 3^m}$ 보다 작을 수 없으므로 모순. 정리하면 $\{0,1\}^\omega$ 의 서로다른 두 원소 $\text{x},\text{x}'$ 에 대해 $f(\text{x})\neq f(\text{x}')$ 이므로 $f$ 는 단사이다. $\square$

본 포스팅의 목표가 되는 결론을 증명하자.

Theorem 3.7. $\mathcal{P}(\mathbb{N})$ 과 $\mathbb{R}$ 은 크기가 같다.

Proof. 정리 3.1.에 따라 $\mathbb{N}\sim\mathbb{Q}$ 이므로 전단사함수 $f:\mathbb{N}\to\mathbb{Q}$ 가 존재한다. 함수에 대한 집합의 상을 이용하여 함수 $F:\mathcal{P}(\mathbb{N})\to\mathcal{P}(\mathbb{Q})$ 를 $F(A)=f(A)$ 라고 정의하면 $F$ 는 전단사이므로 $\mathcal{P}(\mathbb{N})\sim\mathcal{P}(\mathbb{Q})$ 를 얻는다.

보조정리 3.5.에 따르면 단사함수 $\mathbb{R}\to\mathcal{P}(\mathbb{Q})$ 가 존재하며 $\mathcal{P}(\mathbb{Q})\sim\mathcal{P}(\mathbb{N})$ 이므로 단사함수 $\mathbb{R}\to\mathcal{P}(\mathbb{N})$ 이 존재한다. 비슷하게, 보조정리 3.6.에 따르면 단사함수 $\{0,1\}^\omega\to\mathbb{R}$ 가 존재하며 정리 3.4.에 따르면 $\mathcal{P}(\mathbb{N})\sim\{0,1\}^\omega$ 이므로 단사함수 $\mathcal{P}(\mathbb{N})\to\mathbb{R}$ 가 존재한다. 칸토어-베른슈타인 정리에 따라 $\mathcal{P}(\mathbb{N})\sim\mathbb{R}$ 을 얻는다. $\square$

이로써 집합론의 아름다운 공식, $\mathbb{N}\sim\mathbb{Z}\sim\mathbb{Q}$ 와 $\mathcal{P}(\mathbb{N})\sim\mathbb{R}$ 를 얻게 되었다. 자연수와 정수와 유리수의 집합이 모두 같은 크기인 것, 그러나 실수의 집합은 크기가 다르다는 것, 하지만 놀랍게도 자연수 집합의 멱집합과는 크기가 같다는 것 모두 아름다운 결과가 아닐 수 없다.

다음의 따름정리를 마지막으로 이 논의를 마무리하자.

Corollary 3.8. $\mathbb{R}$ 은 셀 수 없다.

Proof. 모순을 보이기 위해 $\mathbb{R}$ 가 셀 수 있다고 가정하자. 정리 2.1.에 따라 전사함수 $f:\mathbb{N}\to\mathbb{R}$ 이 존재한다. 이때 $\mathbb{R}\sim\mathcal{P}(\mathbb{N})$ 이므로 전단사함수 $g:\mathbb{R}\to\mathcal{P}(\mathbb{N})$ 가 존재하여 합성함수 $g\circ f:\mathbb{N}\to\mathcal{P}(\mathbb{N})$ 는 전사함수이다. 그러나 정리 2.8.에 따르면 전사함수 $\mathbb{N}\to\mathcal{P}(\mathbb{N})$ 는 존재할 수 없으므로 모순이다. 그러므로 $\mathbb{R}$ 은 셀 수 없다. $\square$

읽어주셔서 감사합니다.

References)

[1] James R. Munkres. (2000). Topology. Pearson College Div.

[2] StackExchange. https://math.stackexchange.com/questions/553526