바나흐-타르스키 역설 - 2. 자유군

$\mathfrak{F}(x,\,y)$를 생성원(generator) $x$, $y$에 의해 생성된 자유군(free group)이라 하자. 자유군 $\mathfrak{F}(x,\,y)$은 아래의 조건을 만족하는 문자 $x$, $y$, $x'$, $y'$의 나열들로 구성되어 있다.

\[ xx' = x'x = yy' = y'y = e. \]

이 때, $e$는 $\mathfrak{F}(x,\,y)$의 항등원(unit element)이다. 또한 이 자유군의 연산은 단순히 두 원소의 나열로 정의하자. 예를 들어 $\mathfrak{u} = yyx'yx$ 이고 $\mathfrak{v} = x'yxy$라 하면, $\mathfrak{u} \cdot \mathfrak{v}$는 아래와 같이 계산한다.

\[ \mathfrak{u} \cdot \mathfrak{v} = (yyx'yx)(x'yxy) = yyx'y(xx')yxy = yyx'y(1)yxy = yyx'yyxy. \]

우선 아래의 정리를 먼저 살펴보자.

정리 2.1 

자유군 $\mathfrak{F}(x,\,y)$는 가산(countable)이다.

증명. $\mathfrak{F}_n$을 $\mathfrak{F}(x,\,y)$의 원소 중에서 길이가 $n$인 원소들만을 모아 놓은 $\mathfrak{F}(x,\,y)$의 부분집합이라 하자. 예를 들어

\[ \mathfrak{F}_0 = \{e\}, \qquad \mathfrak{F}_1 = \{ x,\, x',\, y,\, y' \} \]

\[ \mathfrak{F}_2 = \{ xx,\, xy,\, xy', x'x',\, x'y,\, x'y',\, yx,\, yx',\, yy,\, y'x,\, y'x',\, y'y' \} \]

와 같은 식이다. 그러면 자연스럽게 다음을 얻는다.

\[ \mathfrak{F}(x,\,y) = \bigcup_{n=0}^\infty \mathfrak{F}_n. \]

각각의 $\mathfrak{F}_n$의 원소의 개수는 많아야 $4^n$개이다. 따라서 $\mathfrak{F}(x,\,y)$은 유한집합(finite set)의 가산합집합(countable union)이므로 가산집합(countable set)이다. ■

이제 $\mathfrak{F}(x,\,y)$의 원소 중 $x$로 시작하는 모든 원소만을 모아 $\mathfrak{F}(x,\,y)$의 부분집합 $\mathfrak{M}(x)$을 정의한다. 같은 방법으로 $\mathfrak{M}(x')$, $\mathfrak{M}(y)$, $\mathfrak{M}(y')$ 또한 정의한다. 그러면, (항등원 $e$를 제외한) $\mathfrak{F}(x,\,y)$의 모든 원소들은 (항등원인 $e$를 제외하면 모든 원소들은 $x$, $x'$, $y$, 또는 $y'$ 중 하나로 시작해야 하므로) 네개의 부분집합 중 하나에 속해야 하고, 또한 이 부분집합들 사이에는 공통 원소가 절대 존재 할 수 없다는 사실을 알 수 있다. 따라서 자유군 $\mathfrak{F}(x,\,y)$는 아래의 성질을 만족한다.

\[ \mathfrak{F}(x,\,y) = \{e\} \uplus \mathfrak{M}(x) \uplus \mathfrak{M}(x') \uplus \mathfrak{M}(y) \uplus \mathfrak{M}(y'). \tag{1} \]

여기서 $\uplus$는 서로소합집합(disjoint union)을 의미한다. 이제 아래와 같은 집합을 생각하자.

\[ x'\mathfrak{M}(x) := \set{x'\mathfrak{u} \in \mathfrak{F}(x,\,y)}{\mathfrak{u} \in \mathfrak{M}(x)}. \]

$\mathfrak{M}(x)$에 있는 모든 원소들은 $x$로 시작하므로 앞에 $x'$을 붙이게 되면, 원소의 앞 부분이 $x'x$가 되어 상쇄되어 사라진다. 이제 $x'\mathfrak{M}(x)$의 모든 원소들은 반드시 $x$, $y$, 또는 $y'$로 시작해야 함을 증명해보자.

정리 2.2

집합 $x'\mathfrak{M}(x)$에 대하여 아래의 식이 성립한다.

\[ x'\mathfrak{M}(x) = \{e\} \uplus \mathfrak{M}(x) \uplus \mathfrak{M}(y) \uplus \mathfrak{M}(y'). \tag{2}\]

증명. 먼저 $\mathfrak{u} \in \mathfrak{M}(x)$이라 가정하자. $\mathfrak{u}$는 $xx'$로 시작할 수 없기 때문에 ($xx'$는 상쇄되어 사라지므로), $x'\mathfrak{u} \in x'\mathfrak{M}(x)$는 $x'$로 시작 할 수 없고 따라서 $x'\mathfrak{u} \notin \mathfrak{M}(x')$을 얻는다. 그러므로 $x'\mathfrak{u} \in \{e\} \uplus \mathfrak{M}(x) \uplus \mathfrak{M}(y) \uplus \mathfrak{M}(y')$가 성립한다. 따라서

\[ x'\mathfrak{M}(x) \subseteq \{e\} \uplus \mathfrak{M}(x) \uplus \mathfrak{M}(y) \uplus \mathfrak{M}(y') \]

를 얻는다.

이제 반대 방향의 포함관계를 증명하기 위하여 먼저 $\mathfrak{u} \in \mathfrak{M}(y)$라 가정하자. 그러면 $\mathfrak{u}$는 $y$로 시작하기 때문에 앞부분에 $x$를 붙여도 상쇄되는게 없고, 따라서 $x\mathfrak{u} \in \mathfrak{M}(x)$가 성립한다. 하지만 이는 $\mathfrak{u} = x'x\mathfrak{u} \in x'\mathfrak{M}(x)$를 함의한다. 그러므로, $\mathfrak{M}(y) \subseteq x'\mathfrak{M}(x)$가 성립한다. 같은 방법으로 $\{e\} \subseteq x'\mathfrak{M}(x)$, $\mathfrak{M}(x) \subseteq x'\mathfrak{M}(x)$, $\mathfrak{M}(y') \subseteq x'\mathfrak{M}(x)$ 또한 얻을 수 있고

\[ \{e\} \uplus \mathfrak{M}(x) \uplus \mathfrak{M}(y) \uplus \mathfrak{M}(y') \subseteq  x'\mathfrak{M}(x) \]

를 얻는다. ■

위 정리는 $\mathfrak{M}(x)$에서 $x$를 $x'$이나 $y$, $y'$로 바꾸어도 유사한 정리가 성립한다. 특히 다음이 성립한다.

\[ y'\mathfrak{M}(y) = \{e\} \uplus \mathfrak{M}(x) \uplus \mathfrak{M}(x') \uplus \mathfrak{M}(y). \tag{2'}\]

여기서 세 식 (1)과 (2), (2')를 합치면, 바나흐-타르스키 역설의 증명에서 가장 중요한 중추석을 담당하는 다음의 따름 정리를 얻을 수 있다.

따름정리 2.3

자유군 $\mathfrak{F}(x,\,y)$에 대하여 아래의 식이 성립한다.

\[ \mathfrak{F}(x,\,y) = x'\mathfrak{M}(x) \uplus \mathfrak{M}(x') = y'\mathfrak{M}(y) \uplus \mathfrak{M}(y') \]

위 따름정리를 예를 들어 설명하면 다음과 같다: 무한한 크기의 격자무늬 평면이 있고 어떤 격자점 위에 (이 점을 원점(origin)이라 하자) 한 사람이 서 있다고 하자. 

<위와 같은 상황을 상상하면 된다>

이 사람은 오직 격자의 상하좌우로만 움직일 수 있다. 여기서 오른쪽으로 움직이는 것을 $x$, 왼쪽으로 움직이는 것을 $x'$, 위쪽으로 움직이는 것을 $y$, 마지막으로 아래쪽으로 움직이는 것을 $y'$으로 생각하면, 자유군 $\mathfrak{F}(x,\,y)$은 원점 위에 서 있는 사람이 격자 위에서 (오른쪽으로 갔다가 바로 왼쪽으로 돌아오는 경우 같은 의미 없는 움직임을 제외한) 움직일 수 있는 모든 경우를 포함한다. 이제 $\mathfrak{M}(x)$을 이 사람의 모든 가능한 움직임 중에서 마지막에 오른쪽으로 움직이고 끝난 경우를 모두 모아 놓은 집합이라 생각하자. 나머지도 비슷한 방법으로 정의한다.

그러면 이 사람이 원점에서 시작하여 움직일 수 있는 모든 경우의 수 $\mathfrak{F}(x,\,y)$는, 마지막을 왼쪽으로 움직이고 끝난 모든 이동의 경우의 수 $\mathfrak{M}(x^{-1})$와 마지막을 오른쪽으로 움직여서 이동을 끝내고 거기서 왼쪽으로 한번 돌아오는 모든 이동의 경우의 수 $x^{-1}\mathfrak{M}(x)$의 합과 같다는게 위 따름정리에 의해 성립한다.