$\R^m$에서 $\R^n$으로의 전단사함수

이번 글의 목적은 ${\mathbb{R}}^m$에서 ${\mathbb{R}}^n$으로의 전단사함수(bijection)를 정의하는 것이다. 그러면 이 사실로부터 ${\mathbb{R}}^m$과 ${\mathbb{R}}^n$의 기수(cardinality)가 같음을 알 수 있다. [사실 이는 $\mathbb{R}\simeq 2^{\mathbb{N}}$이고 $\mathbb{N}\times \mathbb{N}\simeq \mathbb{N}$이라는 사실로부터

$${\mathbb{R}}^m\simeq (2^{\mathbb{N}}{)}^m\simeq 2^{{\mathbb{N}}^m}\simeq 2^{\mathbb{N}}\simeq 2^{{\mathbb{N}}^n}\simeq (2^{\mathbb{N}}{)}^n\simeq {\mathbb{R}}^n$$

와 같이 간단하게 유도할 수 있다.]

먼저 $f:{\mathbb{R}}^2\to \mathbb{R}$이 ${\mathbb{R}}^2$에서 $\mathbb{R}$로의 전단사함수라 가정해보자. 그러면 $g(x,y,z):=f(f(x,y),z)$와 같이 정의된 함수는 자명하게 ${\mathbb{R}}^3$에서 $\mathbb{R}$로 가는 전단사함수가 되고, 이를 이용하여 ${\mathbb{R}}^m$에서 $\mathbb{R}$로 가는 전단사함수를 정의할 수 있다. 한편 $f^{-1}$는 $\mathbb{R}$에서 ${\mathbb{R}}^2$로 가는 전단사함수이므로, 이를 이용하여 $\mathbb{R}$에서 ${\mathbb{R}}^n$으로 가는 전단사함수 또한 정의할 수 있다. 이제 이 함수를 앞서 살펴본 함수와 합성하면 우리가 원하는 ${\mathbb{R}}^m$에서 ${\mathbb{R}}^n$으로의 전단사함수가 된다.

또한 $[0,1]$에서 $\mathbb{R}$로의 전단사함수가 존재한다는 사실을 이용하면 (마지막 절 참고), 결국 우리가 원하는 전단수 함수는 단위정사각형(unit square) $[0,1{]}^2$에서 단위구간(unit interval) $[0,1]$로의 전단사함수를 찾는 문제로 귀결된다는 사실을 알 수 있다. 마지막으로 $[0,1]$이나 $(0,1]$, $(0,1)$으로부터 다른 단위구간으로의 전단사함수가 각각 존재하기 때문에 (마지막 절 참고), 단위구간의 양 끝이 닫혀있는가 열려있는가 여부는 상관이 없다는 사실을 참고하자.

결과적으로 단위정사각형 $(0,1{]}^2$에서 단위구간 $(0,1]$로의 전단사함수만 찾을 수 있다면, 이 함수와 부록 항목에 있는 다른 함수들을 적당히 합성하여 ${\mathbb{R}}^m$에서 $R^n$의로의 전단사함수를 찾을 수 있게 된다.

단위정사각형에서 단위구간으로의 전단사함수

이제 단위정사각형 $(0,1{]}^2$에서 단위구간 $(0,1]$로의 전단사함수를 생각해보자. 물론 이러한 전단사함수는 여러가지가 존재할 수 있지만, 이 글에서 생각해 볼 방법은 "교차배치(interleaving)"을 이용한 방법이다. 우선 단위 정사각형의 모든 원소들은

$$(0.a_1{a}_2{a}_3\cdots ,0.b_1{b}_2{b}_3\cdots )$$

와 같은 형식으로 적을 수 있다. 이제 위 원소의 각각의 자릿수들을 교차배치하여

$$0.a_1{b}_2{a}_2{b}_2{a}_3{b}_3\cdots$$

를 얻는 관계(relation)를 생각해보자. 이는 자연스럽게 $(0,1{]}^2$의 원소로부터 $(0,1]$의 원소를 생성하는 관계 중 하나이다. 하지만 이렇게 정의된 관계는 몇 가지 문제가 있는데 이는 소수의 표현 방법이 유일하지 않다는 사실로부터 발생한다. 임의의 유리수, 예를 들어 $\frac{1}{2}$와 같은 수는 언제나 $0.5000\cdots$ 또는 $0.4999\cdots$와 같이 두가지 표현을 가진다.

물론 이 두가지 표현을 동시에 사용할 수는 없다: 왜냐하면 이 경우, $(\frac{1}{2},0)$는 동시에 $\frac{1}{2}=0.5000\cdots$와 $\frac{9}{22}=0.40909\cdots$를 값으로 가져 위 관계는 함수조차 되지 않기 때문이다. 그러면 위 두가지 소수표현 방법 중 한가지만을 사용하기로 약속하면 이 문제를 해결할 수 있을까? 만약 첫번째 표현만을 사용한다고 하면 $(0,1{]}^2$의 어떤 원소도 $\frac{9}{22}$를 값으로 가질 수 없고, 반대로 두번째 표현만을 사용한다고 하면 $(0,1{]}^2$의 어떤 원소도 $\frac{1}{2}$를 값으로 가질 수 없게 된다.

이 문제는 아래와 같은 방법으로 해결 될 수 있다.

$\frac{1}{2}$와 같이 두가지 소수표현을 갖는 유리수의 경우, 언제나 끊임없이 이어지는 $9$를 가지는 두번째 표현만을 사용하기로 하자. 따라서 $\frac{1}{2}$는 $0.4999\cdots$의 소수표현을 갖는다.

이제 이 수를 각각의 자릿수 단위로 끊는 것이 아니라 특정한 규칙을 따르는 덩어리들로 끊는다. 이 때, 각각의 덩어리의 마지막 자릿수는 언제나 $0$이 아니고, 마지막 자릿수를 제외한 모든 자릿수는 $0$이 되게끔 한다. 이 규칙을 이해하기 위해 예를 들어 생각해 보자. 예를 들어 다음과 같은 수

$$0.010023405999\cdots$$

는 아래와 같은 덩어리들로 끊을 수 있다.

$$010023405999\cdots$$

앞서 유리수의 유리수의 소수표현을 제한함으로써 끊임 없이 $0$을 가지는 표현을 제외하였으므로, 이렇게 덩어리를 짓는 작업은 잘 정의됨을 알 수 있다.

이제 각각의 자릿수들를 교차배치 하는 것이 아니라, 각각의 덩어리들을 교차배치 하는 것으로 관계를 다시 정의하자. 따라서

$$(0.4999\cdots ,0.010023405999\cdots )$$

는 각각 $4$ $9$ $9$ $9\cdots$와 $01$ $002$ $3$ $4$ $05$ $9$ $9$ $9\cdots$의 덩어리들을 교차배치하여

$$0.40190029394905999\cdots$$

를 얻게 된다. 이 관계는 간단히 함수가 됨을 알 수 있고 나아가 전단사함수임 또한 어렵지 않게 보일 수 있다.

또한 이렇게 덩어리들을 교차배치하는 관계는 앞서 살펴보았던 각각의 자릿수를 교차배치하는 관계에서 발생했던 문제점들도 모두 해결한다. 예를 들어 $\frac{1}{2}=0.4999\cdots$를 얻기 위해서는 $[0,1{]}^2$의 원소 $(0.4999\cdots ,0.9999\cdots )$의 상(image)을 생각하면 되고, $\frac{9}{22}=0.40909\cdots$를 얻기 위해서는 $[0,1{]}^2$의 원소 $(0.40909\cdots ,0.0909\cdots )$의 상을 생각하면 된다.

칸토더-슈뢰더-베른슈타인 정리

집합론에서 유명한 정리 중 하나인 칸토어-슈뢰더-베른슈타인 정리(Cantor-Schröder-Bernstein Theorem)은 다음과 같다.

칸토더-슈뢰더-베른슈타인 정리

두 집합 $A$와 $B$에 대하여, 만약 $f:A\to B$와 $g:\to A$로 가는 단사함수(injective function)이 각각 존재하면, $A$와 $B$ 사이의 전단사함수가 존재한다.

따라서 만약 두 단사함수 $f:(0,1{]}^2\to (0,1]$와 $g:(0,1]\to (0,1{]}^2$를 찾을 수 있다면, 위 정리를 이용하여 $(0,1{]}^2$와 $(0,1]$ 사이의 전단사함수가 존재함을 증명할 수 있다. [하지만 위 정리는 전단사함수의 존재성(existence)만 알려줄 뿐 실제로 어떻게 이 함수를 구성하는지는 보여주지는 않는다.]

우선 $g:(0,1]\to (0,1{]}^2$는 $x\stackrel{g}{\mapsto }(x,0)$으로 정의하면 간단히 단사함수임을 보일 수 있다. 단사함수 $f:(0,1{]}^2\to (0,1]$에 대해서는 우선 유리수의 소수표현을 끊임없이 이어지는 $9$를 가지는 표현을 사용하기로 제한하고, 앞에서 살펴본 자릿수들을 교차배치하는 관계를 다시 택하면, 간단히 이 관계가 단사함수임을 보일 수 있다. (물론 앞서 살펴 보았듯이 이 관계는 전사(surjective) 함수가 아니다.)

따라서 칸토어-슈뢰더-베른슈타인 정리를 적용하면 $(0,1{]}^2$와 $(0,1]$ 사이의 전단사함수가 존재함을 보일 수 있다.

몇 가지 전단사함수들

아래는 예시는 몇몇 집합들 사이의 전단사함수를 보여준다.

• $(-\mathrm{\infty },\mathrm{\infty })$와 $(0,\mathrm{\infty })$ 사이의 전단사함수: $x\mapsto e^x$로 정의한다.
• $(0,\mathrm{\infty })$와 $(0,1)$ 사이의 전단사함수: $x\mapsto 2\pi {\tan }^{-1}x$ 또는 $x\mapsto \frac{x}{x+1}$로 정의한다.
• $[0,1]$와 $(0,1]$ 사이의 전단사함수: $[0,1]$의 부분집합 $\{0,\frac{1}{2},\frac{2}{3},\frac{3}{4},\dots \}$에 대하여 우선 $0\mapsto \frac{1}{2}$, $\frac{1}{2}\mapsto \frac{2}{3}$, $\frac{2}{3}\mapsto \frac{3}{4}$ 등으로 정의한다. 또한 $[0,1]$의 나머지 원소에 대해서는 간단히 $x\mapsto x$로 정의한다.
  비슷한 방법으로 $(0,1]$와 $(0,1)$ 사이의 전단사함수 또한 정의할 수 있다.