수학의 본질은 그 자유로움에 있다.
- 게오르크 칸토어
가산과 비가산
가산(Countable)과 비가산(uncountable) 집합은 수학사에서 큰 논쟁거리였다. 가산과 비가산에 대한 이해는 무한의 개념과 무한을 다루는 방법, 더 나아가 수학의 본질에 다가서게 한다. 또한, 가산과 비가산 집합 개념에 기반하여 탄생한 가설인 연속체 가설과 그에 대한 결론은 수리논리, 그 중 불완전성 정리(Incompleteness Theorem)깊은 연관이 있다. 가산과 비가산 집합의 개념을 이해하면서 수학의 본질이 무엇인지 확인해보자.
본 포스트는 고등학교까지의 집합, 함수 개념을 바탕으로 가산과 비가산 개념을 이해하고자 하므로 대수 구조를 이용한 일반화된 서술이 아닌 표준 수 체계라는 보다 좁은 영역에 대해 서술됨.
가산 집합은 셀 수 있는 집합을, 비가산 집합은 셀 수 없는 집합을 의미한다. 가산과 비가산 집합의 차이를 이해하기 위해 자연수 집합, 정수 집합, 유리수 집합, 실수 집합이 각각 가산 집합인지 비가산 집합인지 확인해보자. 이를 위해선 보다 수학적으로 가산 집합을 정의할 필요가 있다. 우리는 무언가를 셀 때 세는 대상에 하나, 둘, 셋, 넷 등 자연수를 할당해 가면서 센다. 그러므로 집합을 구성하는 모든 원소에 자연수를 대응시킬 수 있으면 셀 수 있는 것이고, 대응시킬 수 없으면 셀 수 없는 것이다. 가산 집합을 자연수 집합을 치역으로 일대일 함수(단사, onto)가 정의될 수 있는 집합, 비가산 집합은 일대일 함수가 정의되지 않는 집합이라고 정의해보자. 이를 표현하면 다음과 같다.
\[S: \text{countable}\ \Leftrightarrow \ \exists\ f \ \ \text{s.t}\ \ f:S \to^{\text{onto}} \mathbb{N}\]$\mathbb{N}$ 은 자연수 집합을 가리키는 기호이다. 이와 같은 기호로 정수 집합 기호인 $\mathbb{Z}$ , 유리수 집합 기호인 $\mathbb{Q}$ , 실수 집합 기호인 $\mathbb{R}$ 이 있다. $\mathbb{N}$ 은 자연수의 영어 머릿글자 Natural Number에서 따왔고, $\mathbb{Z}$ 는 독일어 Zahlen에서 따왔으며, $\mathbb{Q}$ 는 몫을 의미하는 영단어 Quotient에서 따왔다. $\mathbb{R}$ 은 영어 Real Number에서 따왔다. $\exists$ 는 존재한다는 뜻이고, $\text{s.t.}$ 은 such that, 어떠한 이라는 의미다. 그리고 $\to^{\text{onto}}$ 는 단사함수라는 의미다.
이제 본격적으로 가산집합의 정의를 따라 여러 수 집합들이 가산 집합인지 비가산 집합인지 확인해보자. 우선 자연수 집합은 가산 집합임이 확실하다. 모든 자연수에 대해 자연수를 다음과 같이 대응할 수 있기 때문이다.
\[\begin{array}{ll} f_{\mathbb{N}}: \mathbb{N} \to \mathbb{N},\ f(n) = n\\ \therefore \ N: \text{countable} \\ &\blacksquare \end{array}\]정수
이제 정수가 가산집합인지 확인해보자. 얼핏 생각하기에 정수 집합은 자연수 집합을 포함하고 음수는 자연수 집합에 포함되지 않으므로 정수는 비가산 집합이라고 생각할 수 있다. 하지만 다음과 같이 정수 집합을 자연수 집합에 대응시킬 수 있는 함수가 존재한다.
\[\begin{aligned} f_{\mathbb{Z}} &= \begin{cases} 2 \lvert x \rvert + 1&\text{if}\ x > 0\\ 2 \lvert x \rvert&\text{if}\ x \leq 0 \end{cases}\\ \ \\ &= \begin{cases} 2 x + 1&\text{if}\ x > 0\\ - 2 x &\text{if}\ x \leq 0 \end{cases} \end{aligned}\]0 혹은 음수는 짝수에, 양수는 홀수에 대응시키면 $f: \mathbb{Z} \to \mathbb{N}$ 인 일대일 대응(전사 & 단사 $\Rightarrow$ 전단사)함수가 정의된다. 이게 과연 가능한지 의문이 들것이다. 이것이 가능한 이유는 이후에 자세히 설명할 것이다. 다만 자연수, 정수 등과 같은 무한의 대상을 다룰 때는 물리적 직관을 버리고 철저히 논리로만 접근해야 한다는 것만 알고있자.
\[\begin{array}{ll} \exists f_{\mathbb{Z}} \ \text{s.t.} f_{\mathbb{Z}}: \mathbb{Z} \to^{\text{onto}} \mathbb{N}\\ \therefore \mathbb{Z}: \text{countable}\\ & \blacksquare \end{array}\]정수 집합을 정의역, 자연수 집합을 치역으로 하는 함수 $f$ 가 정의되므로, 가산 집합의 정의에 따라 정수 집합은 가산 집합이다.
유리수
이제 유리수 집합을 살펴보자. 유리수 집합이야말로 자연수 집합보다 그 수가 훨씬 많으니 비가산 집합이 맞을 것이다. 그렇지 않다. 유리수 집합도 가산 집합이다. 왜 그런지 살펴보자. 유리수의 정의는 분모 분자가 정수인 분수로 표현할 수 있는 수이다. 따라서 모든 유리수는 다음과 같이 표현 가능하다.
\[a \in \mathbb{Q} \Leftrightarrow a = \frac{q}{p}\ (p,\ q \in \mathbb{Z},\ p \ne 0)\]그리고 이는 다음과 같이 다르게 표현할 수 있다.
\[a \in \mathbb{Q} \Leftrightarrow a = \frac{q}{p}\ (p,\ q \in \mathbb{N},\ p \ne 0)\ \lor \ a = - \frac{q}{p}\ (p,\ q \in \mathbb{N},\ p \ne 0)\]$\lor$ 기호는 OR, '혹은', '또는'을 의미한다. 이제 이렇게 일반화된 형태의 유리수를 한번 먼저 정수에 대응시켜 보자. 우선 양수인 유리수를 양수인 정수(자연수)에 대응시키는 경우에 대해 살펴보자. $a \in \mathbb{Q},\ a > 0$ 에 대해,
\[f_{\mathbb{Z},\ {\mathbb{Q}^+}} = n\]꼴로 만드는 것이 우리의 목표이다. 어떻게 해야 할까? 우리는 앞서 $a$ 를 $(p, q)$ 에 대응시킬 수 있음을 확인했다. $a (a > 0)$ 를 일사분면 위 정수 격자점 상의 임의의 점으로 대응시킬 수 있다는 뜻이다. 임의의 정수 격자점에 대해 (1, 1)은 1, (1, 2)는 2, (2, 1)은 3, (1, 3)은 4 와 같은 방식으로 대응시킬 수 있다. 한번 머릿속으로 상상해보면 가능하다는 것을 알 수 있다. 이 $y$ 방향으로 변화하는 변수를 $l$ , 대각선 방향으로 변화하는 값을 $s$ 로 일반화하여 표현해보자.
\[\begin{aligned} n = \sum_{i = 1}^l i + s &= \frac{l(l + 1)}{2} + s\\ &= \frac{(p + q)(p + q + 1)}{2} + p\ (\because s = p,\ l = q + s = p + q) \\ &= \frac{(p + q)^2 + p + q}{2} + p\\ &= \frac{1}{2}(p + q)^2 + \frac{3}{2}p + \frac{1}{2}q \end{aligned}\]이제 정리해보자.
\[f_{\mathbb{Z},\ {\mathbb{Q}^+}}(a) = \frac{1}{2}(p + q)^2 + \frac{3}{2}p + \frac{1}{2}q\ (a = \frac{q}{p})\]음수인 유리수, 0인 경우에 대해 정리하면 정의역을 유리수 집합, 치역을 정수 집합으로 하는 다음과 같은 함수를 구할 수 있다.
\[f_{\mathbb{Z},\ {\mathbb{Q}}}(a) = \begin{cases} \frac{1}{2}(p + q)^2 + \frac{3}{2}p + \frac{1}{2}q\ (a = \frac{q}{p})\ &\text{if}\ a > 0\\ 0\ &\text{if}\ a = 0\\ -\frac{1}{2}(p + q)^2 - \frac{3}{2}p - \frac{1}{2}q\ (a = -\frac{q}{p})\ &\text{if}\ a < 0\\ \end{cases}\]이제 유리수 집합을 자연수 집합에 대응시키는 문제가 남았다. 어떻게 해결해야 할까? 간단하다. 앞서 정수 집합을 자연수 집합에 대응시켰으므로 다음과 같이 합성시키기만 하면 유리수 집합을 정의역으로, 자연수 집합을 치역으로 하는 함수 $f_{\mathbb{Q}}$ 를 쉽게 얻을 수 있다.
\[\begin{array}{ll} f_{\mathbb{Q}} = f_{\mathbb{Z}} \circ f_{\mathbb{Z},\ {\mathbb{Q}}}\\ \exists f_{\mathbb{Q}} \ \text{s.t.} f_{\mathbb{Q}}: \mathbb{Q} \to^{\text{onto}} \mathbb{N}\\ \ \\ \therefore \mathbb{Q}: \text{countable}\\ & \blacksquare \end{array}\]실수
이제 실수 집합만 남았다. 과연 실수집합은 가산일까? 한번 실수 집합을 가산이라고 가정해보자. 실수 집합은 가산 집합이므로 구간 $[0, 1], (0, 1)$ 도 가산일 것이다. 한번 0을 자연수 1에 대응시켜보자. 그러면 0 다음 수인 어떤 수 $\epsilon \in (0, 1)$ 은 1에 대응시킬 수 있을 것이다. 그리고 이 사이(0과 $\epsilon$ 사이)에는 아무런 수가 없어야 한다. 하지만 0과 $\epsilon$ 사이에는 $\frac{\epsilon}{2}, \frac{\epsilon}{3}$ 등 많은 수가 있다. 어떤 $(0,1)$ 의 원소를 선택하든 항상 0과 그 원소 사이에는 수많은 수가 존재한다. 이는 모순이므로 귀류법에 의해 실수 집합은 가산이 아닌 집합, 즉 비가산 집합임을 확인할 수 있다.
이 흐름을 수리논리를 통해 다음과 같이 정리할 수 있다.
\[\begin{array}{ll} \text{Let } \mathbb{R}: \text{countable}\\ \Rightarrow \ [0, 1]: \text{countable}\\ \Rightarrow \ \exists f: \mathbb{[0, 1]} \to^{onto} \mathbb{N} \ \text{s.t.}\ f(0) = 1,\ f: \text{increase}\\ \Rightarrow \ \exists \epsilon \ \text{s.t.}\ f(\epsilon) = 2\\ \Rightarrow \ \emptyset = (0, \epsilon)\\ \frac{\epsilon}{2}, \frac{\epsilon}{3} \in (0, \epsilon)\\ \therefore \ \perp\\ \ \\ \text{By Proof by Contradiction, a.k.a } \perp \text{Elim,}\\ \neg \mathbb{R}: \text{countable} \Leftrightarrow \mathbb{R}: \text{uncountable}\\ &\blacksquare \end{array}\]수 체계와 무한을 보다 더 직관적으로 이해하고 싶다면 힐베르트 호텔 혹은 무한 호텔이라 알려진 사고실험을 참고해도 좋다. 수학도둑이라는 만화에도 실린 이 예시는 무한에 대해 접근하는 방법을 잘 이해하게 도와준다.
수학의 본질과 무한
앞서 보인 과정으로 수 집합이 가산인지 비가산인지 판별하는 것이 가능한 이유는 수학이 때때로 실제 세계에서 영감을 얻기는 하지만, 실제 세계에 의존하는 학문이 아니기 때문이다. 수학은 우리들의 머릿속, 즉 추상의 영역에서만 존재하는 학문이다. 앞서 설명한 증명들은 실제 세계의 직관에선 불가능한 일이지만 수학은 실제 세계 속에 존재하지 않고 머릿속에서 존재하고, 오로지 논리로만 논증을 수행하기 때문에 가능한 것이다.
유물론자들은 이 점을 지적하면서 수학이 공허하다고 말한다. 물리와 달리 수학은 실제 세계와는 아무런 의존을 가지지 않고 머릿속의 결과 만을 내놓기 때문이다. 하지만 수학자들 그리고 다수의 철학자들은 다르게 생각한다. 실제 세계와는 연관되어 있지 않기 때문에 자유로우며, 실제 세계 속에 과하게 고정되어 있는 우리의 사고를 해방시켜 더 높은 차원의 사고를 가능하게 하기 때문이다. 이는 수학자 칸토어가 "수학의 본질은 그 자유로움에 있다."라고 한 것과 연관이 있다. 수학은 추상적 사고에만 의존하기 때문에 마치 우리가 실재하지 않는 것을 상상할 수 있듯이, 자유롭게 모든 것을 논할 수 있다.
그렇기 때문에 우리는 실재하지 않는 개념인 (최소한 실재하는 것이 확실하지 않다) 무한에 대해 다룰 수 있는 것이다. 철저하게 추상적으로, 그리고 논리적으로 무한에 대해 접근함으로써 무한을 명확하고 논리적인 방법으로 논할 수 있다. 앞서 서술한 자연수 집합, 정수 집합, 실수 집합 모두 무한한 개념이다. 하지만 논리를 통해 접근함으로써 무한을 다룰 수 있게 되었다.