본문 바로가기

Mathematics

Bijection from $2^\mathbb{N}$ to $\mathbb{R}$

이 글에서는 $2^\mathbb{N}$과 $\mathbb{R}$의 크기가 같음을 Cantor-Bernstein 정리 없이 bijection을 직접 construct 하여 보인다.

 

1) 먼저, $f_1 : 2^\mathbb{N} \to \{0, 1\}^\mathbb{N}$은 다음과 같이 자연스럽게 잡아줄 수 있다:

  • $S \subset \mathbb{N}$에 대해 $f(S)$는 $S$의 원소 번째 인덱스는 $1$, 나머지 인덱스는 $0$인 binary sequence

2) 이후, $f_2 : \{0, 1\} ^ \mathbb{N} \to [0, 1)$을 구성한다.

 

먼저, $\{0, 1\} ^ \mathbb{N}$을 다음의 세 집합으로 분할할 수 있습니다.

  • $A_0$: 포함하는 $0$의 개수가 유한한 binary sequence들의 집합
  • $A_1$: 포함하는 $1$의 개수가 유한한 binary sequence들의 집합
  • $B$: $A_0$와 $A_1$에 속하지 않는 binary sequence들의 집합

그러면, $A_0$와 $A_1$은 countable 하므로, bijection $a : \mathbb{N} \to A_0$와 $b : \mathbb{N} \to A_1$을 잡아줄 수 있다. (굳이 construction을 적지는 않는다.)

 

이제, bijection $p : \{0, 1\}^\mathbb{N} \to A_1 \cup B$를 다음과 같이 잡아주자:

$$ p(x) = \begin{cases} b_{2k} & x = a_k \\ b_{2k+1} x = b_k \\ x & x \in B \end{cases}$$

앞서 보인 사실로 부터 $p$가 bijection임은 쉽게 체크할 수 있다.

 

그런데, $[0, 1)$의 각 원소에 대한 "무한히 많은 0을 포함하는 이진 전개"는 유일하다. 이를 통해 무한히 많은 0을 포함하는 binary sequence 들의 집합 $A_1 \cup B$에서 $[0, 1)$로 가는 bijection $q$를 잡아주자. 그러고, $f_2 = q \circ p$로 정의해주면, $f_2$는 binary sequence들의 집합에서 $[0, 1)$로 가는 bijection이 된다.

 

사실, $f_2$를 구성할 때 단순히 실수의 이진전개로 잡는다는 생각을 할 수도 있겠으나, 실수의 이진전개 자체는 유일하지 않으므로 그러면 안된다. ($0.1_{(2)} = 0.01111\dots_{(2)}$를 생각하라)

 

3) $f_3 : [0, 1) \to (0, 1)$을 $f_3(x) = \begin{cases} {n+1 \over n+2} & x = {n \over n+1}, n \text{ is a non-negative integer} \\ x & \text{otherwise} \end{cases}$로 잡아주자.

 

4) $f_4 : (0, 1) \to \mathbb{R}$을 $f_4(x) = \tan((x - 1/2) \pi)$로 잡아주자.

 

1) ~ 4)에서 잡아준 $f_1, f_2, f_3, f_4$에 대해 $f_4 \circ f_3 \circ f_2 \circ f_1$이 우리가 원하는 bijection이 된다.