11. 모든 피보나치 수의 합과 모든 자연수의 합 중 뭐가 더 큰가요?

어느 날, solved.ac 디스코드에 흥미로운 주제가 날아왔다. 수학을 나름 사랑하는 사람으로서 절대 물지 않고 넘어갈 수 없던 떡밥이라 얌전히 물어 보기로 했다.

 

피보나치 수의 합과 자연수의 합 중 어느 쪽이 더 크냐는 질문이었고, 이 질문을 던진 분은 세 가지 케이스에 대해서 다음과 같은 근거를 달았다(정확하게는, 약간의 윤색을 거쳤다.).

모든 피보나치 수의 합과 모든 자연수의 합이 같다 : 딱히 주장할 만한 근거가 떠오르지 않는다.

모든 피보나치 수의 합 쪽이 더 크다 : $n>4$이면 $n\le F_n$임을 보일 수 있고, 이를 이용하여 $n>6$이면 $\sum _{i=0}^{n}i<\sum _{i=0}^n{F}_i$이 성립함을 보일 수 있다. 좌변에 $n$, 우변에 $F_n$을 더하면 $n$이 커져도 부등호의 방향은 바뀌지 않을 것이므로, 모든 피보나치 수의 합 쪽이 더 클 것이다.

모든 피보나치 수의 합 쪽이 더 작다 : 피보나치 수를 원소로 가지는 집합이 자연수를 원소로 가지는 집합의 부분집합이므로 모든 피보나치 수의 합 쪽이 더 작을 것이다.

 

결론부터 말하자면, 질문을 던진 분이 정당화할 근거를 떠올리지 못했던 같다 쪽이 정답이다. 임의의 자연수를 같은 크기를 가지는 집합의 기수인 유한기수로 생각하자면 이 둘이 같다는 것을 증명할 수 있다.

이후로는 $F_n$을 처음 두 항이 $F_0=0,F_1=1$인 피보나치 수열의 $n$번째 항이라는 의미로 사용하겠다.

 

Proof 1: 거의 완벽한 증명

자연수 $n$에 대해 집합 $X_n=\{(x,n)\mid 0\le x<n\}$으로 정의한다면 $n\ne m$이면 $X_n\cap X_m=\mathrm{\varnothing }$이며 $\text{card}(X_n)=n$이 성립한다. 따라서 모든 자연수의 합은 $\sum _0^{\mathrm{\infty }}n=\text{card}(\bigcup _0^{\mathrm{\infty }}{X}_n)$이 된다.

$X=\bigcup _0^{\mathrm{\infty }}{X}_n$으로 둔다면, $\{0\}\times \mathbb{N}\subseteq X\subseteq \mathbb{N}\times \mathbb{N}$이다. $\{0\}\times \mathbb{N}$은 자명하게 가산 무한이며, $\mathbb{N}\times \mathbb{N}$은 $(0,0)\to (0,1)\to (1,0)\to (0,2)\to (1,1)\to (2,0)\to \cdots$의 형식으로 열거 가능한 가산 무한 집합이다. 이 둘 사이에 끼인 $X$ 또한 가산 무한 집합이므로, $\sum _0^{\mathrm{\infty }}n={\mathrm{\aleph }}_0$이 된다(여기서 ${\mathrm{\aleph }}_0$은 가산 무한 집합인 $\mathbb{N}$의 기수이다.).

모든 피보나치 수의 합을 기수로 가지는 집합을 $Y_n=\{(x,n)\mid 0\le x<F_n\},Y=\bigcup _0^{\mathrm{\infty }}{Y}_n$으로 정의할 수 있다. 자명하게 $\{0\}\times \mathbb{N}\subseteq Y\subseteq \mathbb{N}\times \mathbb{N}$이고, $Y$ 또한 두 가산 무한 집합 사이에 끼인 집합이므로 가산 무한 집합이다. 따라서 $\sum _0^{\mathrm{\infty }}{F}_n={\mathrm{\aleph }}_0$이 된다.

따라서 $\sum _0^{\mathrm{\infty }}n=\sum _0^{\mathrm{\infty }}{F}_n$이 성립한다. ■...?

 

위 증명을 거의 완벽한 증명이라고 한 이유는, 두 가산 무한 집합 사이에 끼인 집합이 가산 무한 집합이 되는 이유를 증명하지 않았기 때문이다. 이를 증명할 수 있는 정리는 집합론의 태동기에 탄생한 Cantor=Schröder-Bernstein Theorem이다. 이 정리는 다음과 같다:

두 집합 $X,Y$를 정의역과 공역으로 하는 두 단사 함수 $f:X\to Y,g:Y\to X$가 존재하면 전단사 함수 $h:X\to Y$가 존재한다.

이는 선택 공리 없이 증명할 수 있다. 다행히, 선택 공리를 채택하지 않음으로서 기수의 순서가 부분 순서임마저도 깨지지는 않게 된다(기수 A가 기수 B보다 크거나 같으면서 동시에 작다는 이상한 상황은 발생할 수 없다는 이야기이다.). 물론 전순서임은 깨지지만(임의의 두 집합의 기수를 비교하지 못하게 된다는 이야기이다.).

이 Cantor-Schröder-Bernstein Theorem에는 비슷한 맥락을 가진 여러 증명법이 있다. 집합론 전공서에 포함되어 있음직한 표준적인 증명이 있고, Kőnig(그래프 이론, 최대 매칭에 대한 유용한 정리의 쾨니그와는 다르다. 그 사람은 Dénes Kőnig이고, 이 사람은 Gyula Kőnig이다.)의 증명법과 Tarski's Fixed Point Theorem을 이용한 증명법이 있다. 표준적인 증명은 너무 유명하고, Tarski's Fixed Point Theorem을 이용한 증명은 서술할 것이 너무 많아서(complete lattice부터 정의하고 시작해야 한다.) 여기 담기에는 부적절하다. 자연스럽게 무얼 가지고 증명해야 하는지는 결정된 셈 치겠다.

 

Proof 2: Kőnig에 의한 Cantor-Schröder-Bernstein Theorem의 증명

편의상 $X\cap Y=\mathrm{\varnothing }$이라고 하자. 아니라고 해도 $X\times \{0\},Y\times \{1\}$을 $X,Y$의 대체제로 사용하면 되니 큰 문제 없다. 이제 두 단사함수 $f,g$의 부분적 역함수 $f^{-1}:fX\to X$, $g^{-1}:gY\to Y$를 정의하자.

그러면 임의의 $x\in X$에 대해서 $X\cup Y$의 원소로 이루어진 chain $\cdots \to f^{-1}{g}^{-1}(x)\to g^{-1}(x)\to x\to f(x)\to gf(x)\to \cdots$이 존재한다. 이 chain은 오른쪽으로는 무한히 이어지고, 왼쪽으로는 끝이 없거나 더 이상 $f^{-1}$이나 $g^{-1}$이 정의되지 않는 어떠한 $X$ 혹은 $Y$의 원소에서 끝이 난다. 반대로 임의의 $y\in Y$에 대해서도 매우 비슷한 성질을 가진 chain $\cdots \to g^{-1}{f}^{-1}(y)\to f^{-1}(y)\to y\to g(y)\to fg(y)\to \cdots$이 존재한다.

어떠한 chain에 대해서 오른쪽으로 가는 길은 유일하므로, 어떠한 두 chain이 하나의 원소를 공유한다면 이 두 chain은 같다. 따라서 모든 chain을 중복 없이 단 한 번씩만 쓴다면, 그 과정에서 $X\cup Y$의 모든 원소가 중복 없이 정확히 단 한 번씩만 등장할 것이다.

어떠한 chain의 가장 왼쪽 원소가 $X$의 원소일 시, 그 chain에 등장하는 모든 원소를 $X$-stopper라고 부르며, 반대로 어떠한 chain의 가장 왼쪽 원소가 $Y$의 원소일 시, 그 chain에 등장하는 모든 원소를 $Y$-stopper, 그리고 어떠한 chain이 반복되거나 영원히 끝나지 않을 시 doubly infinite라고 하자. 이 세 종류의 원소에 대해서, chain 내에서 특정한 방향으로 이동하도록 하는 식으로 새로운 함수 $h$를 정의할 것이고, 이것이 전단사가 됨을 보일 것이다.

$h:X\to Y$를, $x$이 $X$-stopper이거나 doubly infinite일 시 $x$의 바로 오른쪽 원소, 즉 $f(x)$로, $x$이 $Y$-stopper일 시 $x$의 바로 왼쪽 원소, 즉 $g^{-1}(x)$로 정의할 것이다. 그러면 이는 $f,g$와 그들의 역함수가 단사이기 때문에 자명하게 단사함수이다. 또한 $Y$-stopper가 아닌 모든 $y$의 원소는 자신의 왼쪽 원소가 존재하고, 모든 원소는 자신의 오른쪽 원소가 존재하기 때문에 임의의 $y\in Y$에 대해서 $h(x)=y$인 $x\in X$이 존재한다.

따라서 $h:X\to Y$는 전단사 함수이다. 이와 유사한 방식으로 전단사 함수인 $k:Y\to X$를 구성할 수도 있다. ■

 

이 정리를 통해서 서로 기수가 같은 집합 속에 끼어 있는 집합 또한 기수가 같음은 쉽게 증명된다. 조금 더 formal하게 서술하자면, $X\subseteq Z\subseteq Y$이고 $\text{card}(X)=\text{card}(Y)=\lambda$이면, $\text{card}(Z)=\lambda$가 성립한다. 왜냐하면 전단사 함수 $f:X\to Y$가 존재할 것이고, 두 inclusion $ı:X\hookrightarrow Z$와 $ȷ:Z\hookrightarrow Y$는 단사함수이기 때문이다. 곧 $f\circ ȷ:Z\to X$은 단사가 되며, Cantor-Schröder-Bernstein Theorem에 의하여 전단사함수 $X\to Z$이 존재하여 $\text{card}(X)=\text{card}(Z)$이 되기 때문이다.

이제 Proof 1: 거의 완벽한 증명의 간극을 메울 수 있다. 두 가산 무한 집합에 끼인 집합은 Cantor-Schröder-Bernstein Theorem에 의하여 가산 무한 집합이 되기 때문이다. ■