최근에 '원피스'라는 만화를 재밌게 보고 있습니다. IPTV로 무료로 방송되네요. 시즌 3 알라바스타편에서는 속고 속이는 과정의 연속인데, 이것을 보다가 문득, 어디선가 보았던 재밌는 증명이 생각이 나서 여기 옮기려 합니다.
집합 $X$의 원소의 개수를 확장해서 무한집합에서도 개수개념을 다루기 위해 만든 것이 cardinal number인데, 수학자들은 편의상 $\vert X \vert $로 이 수를 나타내곤 합니다.
우리가 유한개의 물건의 개수를 셀 때 하나, 둘, ... 하는 것을 물건과 자연수를 일대일대응시키는 것으로 보고 이것을 확장시켜서 두 집합 $A$, $B$ 사이에 일대일대응을 만들 수 있으면 두 집합의 cardinal number 혹은 cardinality가 같다고 해서 $\vert A \vert = \vert B \vert$와 같이 씁니다. 간단한 예로 자연수 집합 $\mathbb N$과 짝수들의 집합 $2 \mathbb N$ 사이에는 $f(x) = 2x$라는 일대일 대응이 있으니까 $\vert \mathbb N \vert = \vert 2 \mathbb N \vert $입니다.
일대일대응이라는 강력한 함수를 잡는 것은 대체로 쉽지 않은 일인데, 양방향으로 일대일함수만 각각 잡을 수 있어도 cardinality가 같다는 것이 발견됩니다(Schröder-Bernstein Theorem).
그렇다면 $$f : \mathbb N \to \mathbb Q^+ = \left\{ x | x >0, x \in \mathbb Q \right\}$$ 를 $f(x)=x$로 정의하면 이 함수가 일대일이고 $$g: \mathbb Q^+ \to \mathbb N, \quad g(p/q) = 2^p 3^q$$ 도 산술의 기본정리에 의해 일대일이 되므로 앞서 말한 Schröder-Bernstein Theorem에 의해 $|\mathbb Q | = |\mathbb N|$이 된다는 것을 확인할 수 있습니다.
이쯤 되면 무한집합의 cardinal은 다 같아서 의미가 없어질 것 같아보이나, 칸토르가 실수집합과 자연수집합 사이에 일대일대응이 없다는 것을 증명해 버립니다. “대각선논법”이라 검색하면 수도 없이 많은 웹페이지가 검색될 정도로 유명한 증명입니다.
여기서 언급할 칸토르의 정리는 이것을 더 일반화시킨 것입니다. 칸토르가 증명에 사용한 실수의 부분집합은 구간 $[0,1]$이었는데, 이 구간의 수는 자연수 집합 $\mathbb N$의 부분집합 $A$를 실수 $a = \sum_{k \in A} 2^{-k}$(특히 $A= \varnothing$일 때는 $a=0$)에 대응시키는 작업에 의해 자연수의 부분집합 전체와 대응시킬 수 있습니다(물론, 엄밀하게는 countable개의 중복이 생기지만 결론을 봤을 때 중요하지 않습니다.). 그렇다면 칸토르의 증명은 $| \mathbb N | < | 2^{\mathbb N}|$임을 증명한 것이라고도 볼 수 있습니다. 그래서, 과감하게 다음이 성립할 것이라고 기대할 수 있습니다.
뜬금없이 원피스가 나왔던 이유는 이 증명 때문이었는데요, 옛날 어느 말재간이 좋은 분이 다음과 같이 증명을 했었습니다.
$|A| \leq |2^A|$인 것은 당연하니까 $|A| \neq |2^A|$임을 증명하겠습니다. 귀류법을 이용하기 위해 $|A| = |2^A|$이라고 가정합니다. 그러면 두 집합 사이에 일대일대응 $\phi : A \to 2^A$이 정의됩니다. 대응결과를 보고 집합 $A$의 원소를 다음 두 부류로 나누어 봅니다.
Type 1: $ a \in \phi(a)$: 이런 원소를 ‘동료’라고 하고 파란 색으로 칠해줍시다.
Type 2: $ a \notin \phi(a)$: 이런 원소를 ‘첩자’라 하고 빨간 색으로 칠해줍시다.
그러면 집합 $A$의 원소는 두 부류로 나뉘게 됩니다. 그럼, 첩자들을 모두 모아놓은 집합도 $2^A$ 안에 있는 한 원소일텐데, 그 집합에 대응되는 다음 그림의 회색 동그라미는 동료일까요 첩자일가요?
동료라고 하려니 대응집합 안에 온통 빨간 애들만 있어서 첩자가 되어 모순이고, 첩자라 하려니 오른쪽 집합이 첩자를 다 모아놓은 집합이라 그 집합의 원소가 될 수밖에 없어버립니다. 즉, 분류규칙에 따라 동료가 되어 모순이 됩니다. 따라서, 애초에 생각했던 일대일대응은 존재하지 않는다는 결론이 나옵니다.
집합론책을 펴보면 이 정리의 증명이 나오는데, 사실상 동일합니다. 그냥 재미삼아 이렇게 설명한거죠. 하지만, 이렇게 보고나니 증명이 정말 오래 기억에 남습니다.