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

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

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

$ $

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

$ $

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

$ $

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

$ $

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

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

\[ (0.a_1a_2a_3 \cdots,\, 0.b_1b_2b_3 \cdots) \]

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

\[ 0.a_1b_2a_2b_2a_3b_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 \]

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

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

$ $

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

$ $

몇 가지 전단사함수들

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

  • $(-\infty,\, \infty)$와 $(0,\, \infty)$ 사이의 전단사함수: $x \mapsto e^x$로 정의한다.
  • $(0,\, \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},\, \ldots \}$에 대하여 우선 $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)$ 사이의 전단사함수 또한 정의할 수 있다.