PART I — 증명
유한한 세계에서 \(|A| = |B|\)는 그냥 원소를 세서 비교하면 됩니다. 그런데 무한이 되면 "센다"는 행위 자체가 의심스러워지죠. 이 챕터에서는 무한 집합의 크기를 어떻게 비교할지 정의하고, 모든 무한이 같은 크기가 아니라는 충격적인 사실을 만나봅니다. 그리고 그 발견의 부산물로 컴퓨터과학의 가장 유명한 결과 중 하나, 정지 문제(Halting Problem)의 해결 불가능성을 증명합니다. 누군가 그랬어요. "어떤 무한이 다른 무한보다 크다는 사실에 충격받지 않으면 마음이 죽은 것이다." 다행히 우리는 살아있습니다.
유한 집합이라면 크기 비교는 쉽습니다. 사과 5개와 배 5개는 같은 개수이고, 사과 5개와 배 7개는 배가 더 많죠. 하지만 자연수 \(\mathbb{N} = \{0, 1, 2, 3, \dots\}\)와 짝수 전체 \(2\mathbb{N} = \{0, 2, 4, 6, \dots\}\)는 누가 더 많을까요?
"짝수는 자연수의 절반이니까 자연수가 두 배 많지!" — 이게 직관적인 답이지만, 무한의 세계에서는 직관이 자주 무너집니다. 19세기 칸토어(Cantor)가 제시한 답은 깔끔합니다. 두 집합 사이에 일대일 대응(전단사)이 존재하면 같은 크기다. 짝수와 자연수 사이엔 \(n \mapsto 2n\)이라는 전단사가 있으니, 두 집합은 같은 크기입니다. "전체와 일부가 같은 크기"라는 게 무한의 본질이에요.
정의 8.1.1 (집합의 크기 비교)
집합 \(A\), \(B\)에 대해:
(1) 단사 \(f : A \to B\)가 존재하면 \(|A| \le |B|\)라고 씁니다.
(2) 전단사 \(f : A \to B\)가 존재하면 \(|A| = |B|\)라고 씁니다.
(3) \(|A| \le |B|\)이면서 \(|A| = |B|\)는 아니면 \(|A| < |B|\)라고 씁니다.
유한 집합에서 이 정의는 우리가 아는 "원소 개수"와 정확히 일치합니다. 그리고 이 정의는 무한 집합으로 자연스럽게 확장돼요. 단, 직관과 충돌할 각오는 해야 합니다.
정의 8.1.2 (가산집합)
집합 \(A\)가 자연수 집합 \(\mathbb{N}\)과 같은 크기일 때, 즉 \(|A| = |\mathbb{N}|\)일 때 \(A\)를 가산무한(countably infinite)이라고 합니다. 유한이거나 가산무한이면 그냥 가산(countable)이라고 부르고, 그렇지 않으면 비가산(uncountable)입니다.
가산무한이라는 건 결국 "원소를 \(a_0, a_1, a_2, \dots\)로 줄세울 수 있다"는 뜻입니다. 자연수와 일대일 대응이라는 건 자연수 인덱스를 붙일 수 있다는 거니까요.
예제 8.1.3 (정수는 가산이다)
정수 집합 \(\mathbb{Z}\)는 음수까지 포함해서 자연수보다 두 배 큰 것 같은데, 사실 가산입니다. 다음과 같이 줄세우면 돼요:
\[ 0, \ 1, \ -1, \ 2, \ -2, \ 3, \ -3, \ \dots \]
전단사 \(f : \mathbb{N} \to \mathbb{Z}\)를 명시적으로 쓰면:
\[ f(n) = \begin{cases} n/2 & n \text{이 짝수} \\ -(n+1)/2 & n \text{이 홀수} \end{cases} \]
이걸로 \(|\mathbb{Z}| = |\mathbb{N}|\)이 증명됩니다.
예제 8.1.4 (유리수도 가산이다)
유리수 \(\mathbb{Q}\)는 정수보다 훨씬 빽빽해 보입니다. 어떤 두 유리수 사이에도 무한히 많은 유리수가 있죠. 그런데도 가산입니다. 양의 유리수 \(p/q\) (단, \(p, q > 0\))를 격자 위에 펼쳐놓고 대각선을 따라 지그재그로 줄세우면 됩니다:
1/1 1/2 1/3 1/4 ...
2/1 2/2 2/3 2/4 ...
3/1 3/2 3/3 3/4 ...
. . . .
순서: 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, ...
중복된 분수(예: \(2/2 = 1/1\))는 건너뛰면 양의 유리수 전체에 자연수 인덱스가 매겨집니다. 음의 유리수와 0까지 끼워 넣으면 \(|\mathbb{Q}| = |\mathbb{N}|\)이 끝납니다.
여기까지 보면 "어쩌면 모든 무한이 다 같은 크기 아닌가?" 싶죠. 칸토어 본인도 한동안 그렇게 의심했다고 합니다. 그런데 1874년경 그는 충격적인 사실을 발견합니다. 실수 \(\mathbb{R}\)은 자연수와 같은 크기가 아니다. 더 큽니다.
정리 8.1.5 (칸토어, 1874)
실수 집합 \(\mathbb{R}\)은 비가산이다. 즉 \(|\mathbb{N}| < |\mathbb{R}|\).
증명 (대각선 논법)
편의를 위해 구간 \([0, 1)\)에 속하는 실수만 봐도 충분합니다. 이것이 가산이 아님을 보이면 \(\mathbb{R}\) 전체도 가산일 수 없으니까요.
모순을 위해 \([0, 1)\)이 가산이라고 가정합시다. 그러면 모든 원소를 \(r_0, r_1, r_2, \dots\)로 줄세울 수 있어요. 각 실수를 무한 소수로 표현합시다 (예를 들어 0.5는 \(0.5000\dots\)으로):
\[ \begin{aligned} r_0 &= 0.\,d_{00} d_{01} d_{02} d_{03} \dots \\ r_1 &= 0.\,d_{10} d_{11} d_{12} d_{13} \dots \\ r_2 &= 0.\,d_{20} d_{21} d_{22} d_{23} \dots \\ &\vdots \end{aligned} \]
여기서 \(d_{ij}\)는 \(r_i\)의 소수점 \(j+1\)번째 자리 숫자입니다. 이제 새로운 실수 \(x\)를 다음 규칙으로 만듭시다. \(x\)의 \(i\)번째 소수 자리를:
\[ x_i = \begin{cases} 1 & d_{ii} \neq 1 \\ 2 & d_{ii} = 1 \end{cases} \]
즉 대각선의 \(d_{ii}\)와 다른 숫자를 골라 넣습니다. 그리고 \(0\)이나 \(9\)는 일부러 피해서, "\(0.4999\dots = 0.5000\dots\)" 같은 표현 중복 문제를 차단했어요.
이제 이 \(x\)를 봅시다. \(x\)는 \([0, 1)\)에 속하는 실수입니다. 그런데 어떤 \(r_i\)와도 같지 않아요. 왜냐하면 \(x\)와 \(r_i\)는 적어도 \(i\)번째 소수 자리에서 다르거든요. 따라서 \(x\)는 우리의 목록 어디에도 등장하지 않습니다. 이는 "모든 원소를 줄세웠다"는 가정에 모순이에요. 따라서 \([0, 1)\)은 비가산이고, \(\mathbb{R}\)도 비가산입니다.
∎
이 기법이 그 유명한 칸토어 대각선 논법(Cantor's diagonal argument)입니다. 표를 만들어놓고 대각선을 골라 그것과 다른 무언가를 만든다는 발상이에요. 이 발상은 다음 절에서 컴퓨터과학을 뒤흔들게 됩니다.
노트
가산 무한의 크기를 \(\aleph_0\) (알레프 영, aleph-null)이라고 부릅니다. 실수의 크기는 \(\mathfrak{c}\) (continuum)라 부르고, \(\aleph_0 < \mathfrak{c}\)입니다. "그 사이 크기의 집합이 있는가?"라는 질문이 그 유명한 연속체 가설(Continuum Hypothesis)인데, 8.4절에서 살짝 다시 언급합니다.
"이 프로그램이 무한 루프에 빠지나, 아니면 언젠가 끝나나?" — 코드를 짜본 사람이라면 누구나 떠올린 질문일 겁니다. 이걸 자동으로 판정해주는 도구가 있다면 디버깅이 얼마나 편해질까요. 컴파일러가 무한 루프를 미리 잡아주면 좋잖아요. 그런데 1936년 앨런 튜링(Alan Turing)이 결정적인 답을 줬습니다. 그런 도구는 원리적으로 만들 수 없다.
여기서 "프로그램"은 임의의 알고리즘을 의미합니다. 파이썬, C, 튜링 기계, 람다 계산 — 표현 방식이 무엇이든 상관없어요. 핵심은 다음 함수를 계산하는 알고리즘이 존재하느냐는 것입니다:
정의 8.2.1 (정지 문제)
입력 \((P, x)\) — 프로그램 \(P\)의 소스 코드와 입력 \(x\) — 를 받아 다음을 출력하는 알고리즘이 있는가?
\[ \text{Halt}(P, x) = \begin{cases} \text{true} & P \text{가 입력 } x \text{에 대해 정지} \\ \text{false} & P \text{가 입력 } x \text{에 대해 무한 루프} \end{cases} \]
"그냥 돌려보면 되지 않나?" 싶지만, 무한 루프인 경우엔 영원히 결과를 알 수 없습니다. 우리가 원하는 건 유한 시간 안에 항상 정확한 답을 내는 알고리즘이에요.
정리 8.2.2 (튜링, 1936)
정지 문제를 풀 수 있는 알고리즘은 존재하지 않는다.
증명 (대각선 논법의 컴퓨터과학판)
모순을 위해 가정합니다. \(\text{Halt}(P, x)\)를 정확히 계산하는 알고리즘이 있다고 합시다. 그러면 우리는 이걸 부품으로 써서 또 다른 프로그램 \(\text{Trouble}\)을 만들 수 있어요:
def Trouble(P):
if Halt(P, P) == True:
while True:
pass # 일부러 무한 루프
else:
return # 그냥 정지
\(\text{Trouble}\)은 프로그램 \(P\)를 입력으로 받아, "\(P\)가 자기 자신을 입력으로 했을 때 정지한다면 무한 루프에 빠지고, 정지 안 한다면 정지한다." 청개구리처럼 거꾸로 행동합니다.
이제 결정적인 한 수. \(\text{Trouble}\) 자체에 \(\text{Trouble}\)을 입력으로 줘봅시다. \(\text{Trouble}(\text{Trouble})\)은 정지할까요?
두 경우 모두 모순이므로, 처음 가정 — "\(\text{Halt}\)를 계산하는 알고리즘이 있다" — 이 틀렸습니다.
∎
이 증명은 정확히 칸토어의 대각선 논법과 같은 골격입니다. 칸토어는 "모든 실수의 목록"을 가정하고, 대각선의 \(i\)번째 자리를 뒤집어서 목록에 없는 실수를 만들었어요. 튜링은 "모든 프로그램에 대한 정지 판정"을 가정하고, "자기 자신에 대한 답"을 뒤집은 \(\text{Trouble}\)을 만들었습니다. 둘 다 "표의 대각선을 부정하면 모순"이라는 같은 패턴이에요.
노트
정지 문제의 결과는 단순히 "한 가지 문제를 못 푼다"가 아닙니다. 컴퓨터로 표현 가능한 모든 알고리즘의 한계를 보여주는 결과예요. 함수의 가짓수는 비가산인데(실수만큼 많음), 프로그램의 가짓수는 가산이거든요(유한한 문자열의 집합이니까). 그러니 대부분의 함수는 어떤 프로그램으로도 계산할 수 없습니다. 정지 문제는 그 무수히 많은 "계산 불가능한 함수" 중 하나일 뿐이에요.
실용적으로 보면 슬픈 결과지만, 한편으론 컴파일러 작성자에게 면죄부이기도 합니다. "왜 무한 루프 못 잡아줘?"에 대해 "그건 원리적으로 불가능합니다"라고 답할 수 있게 됐으니까요.
지금까지 \(|A| = |B|\)는 전단사로, \(|A| \le |B|\)는 단사로 정의했습니다. 그런데 정말 이 정의가 우리의 직관처럼 작동할까요? 예를 들어 "\(|A| \le |B|\)이고 \(|B| \le |A|\)이면 \(|A| = |B|\)다"라는 명제는 당연해 보이지만, 무한 집합에선 증명이 필요합니다. 이게 바로 슈뢰더-베른슈타인 정리예요.
정리 8.3.1 (슈뢰더-베른슈타인)
단사 \(f : A \to B\)와 단사 \(g : B \to A\)가 모두 존재하면, 전단사 \(h : A \to B\)가 존재한다. 즉 \(|A| \le |B|\)이고 \(|B| \le |A|\)이면 \(|A| = |B|\).
증명은 여기선 생략하지만, 핵심 아이디어는 이렇습니다. 각 원소의 "출신 사슬"을 거꾸로 거슬러 올라가서, 사슬이 \(A\)에서 시작했는지 \(B\)에서 시작했는지에 따라 \(f\)를 쓸지 \(g^{-1}\)을 쓸지 골라 \(h\)를 정의합니다. 손으로 그림 그려보면 의외로 깔끔해요.
이제 한 단계 더 나아가, "주어진 집합보다 더 큰 집합을 항상 만들 수 있는가?"라는 질문을 던져봅시다. 답은 그렇습니다 — 그것도 매우 자연스러운 방법으로요. 멱집합을 쓰면 됩니다.
정의 8.3.2 (멱집합)
집합 \(A\)의 멱집합(power set) \(\mathcal{P}(A)\)는 \(A\)의 모든 부분집합을 모은 집합이다. 표기로 \(2^A\)라고도 쓴다. 유한 집합에서 \(|A| = n\)이면 \(|\mathcal{P}(A)| = 2^n\).
정리 8.3.3 (칸토어 정리)
임의의 집합 \(A\)에 대해 \(|A| < |\mathcal{P}(A)|\)이다. 즉 멱집합은 항상 원래 집합보다 진짜로 더 크다.
증명 스케치
\(|A| \le |\mathcal{P}(A)|\)는 쉽습니다. \(a \mapsto \{a\}\)이 단사예요. 핵심은 전단사가 없다는 것. 모순을 위해 전단사 \(f : A \to \mathcal{P}(A)\)가 있다고 가정합시다. 그러면 다음 부분집합을 정의해요:
\[ D = \{ a \in A : a \notin f(a) \}. \]
즉 \(D\)는 "자기가 매핑된 부분집합에 자기 자신이 들어있지 않은 원소들"의 모음입니다. \(D \subseteq A\)이므로 \(D \in \mathcal{P}(A)\)이고, \(f\)가 전사라면 어떤 \(a^* \in A\)가 있어 \(f(a^*) = D\). 이제 \(a^* \in D\)인지 묻습니다:
두 경우 모두 모순이므로 전단사는 없습니다. 따라서 \(|A| < |\mathcal{P}(A)|\).
∎
또 대각선 논법이에요! \(D\)를 정의할 때 "\(a \in f(a)\)라는 진술을 부정"한 게 본질적으로 대각선을 뒤집은 것입니다. 칸토어 대각선 논법, 정지 문제, 칸토어 정리 — 모두 같은 도구로 같은 형태의 결론을 끌어냅니다.
이 정리는 무한의 위계가 끝없이 올라간다는 뜻이기도 합니다. \(\mathbb{N}\)보다 큰 \(\mathcal{P}(\mathbb{N})\), 그보다 큰 \(\mathcal{P}(\mathcal{P}(\mathbb{N}))\), \(\dots\) 무한히 많은 "다른 크기의 무한"이 존재해요. 칸토어 본인이 이걸 발견하고 한참 어지러워했다고 합니다. 그럴 만 하죠.
노트 (\(2^A\) 표기의 정당화)
멱집합을 \(2^A\)라고 쓰는 이유: \(A\)의 부분집합은 각 원소마다 "포함/제외"의 두 선택을 한 결과로 볼 수 있어요. 즉 \(A\)에서 \(\{0, 1\}\)로 가는 함수와 일대일 대응이고, 그런 함수의 모음을 보통 \(\{0,1\}^A\)라고 표기합니다. 그래서 \(\mathcal{P}(A) = 2^A\). 유한일 땐 \(|2^A| = 2^{|A|}\)와도 일관됩니다.
참고로 이 모든 논의가 깔끔하게 이뤄지려면 "집합"이 무엇인지를 엄밀하게 정의해야 합니다. 현대 수학은 ZFC(Zermelo-Fraenkel + 선택공리)라는 공리계 위에서 작동해요. 9개 정도의 공리들이 "이런 집합은 만들 수 있다", "이렇게 모으면 또 집합이다"를 정해놓은 것입니다. 우리가 쓴 모든 집합론 기법 — 합집합, 교집합, 멱집합, 함수, 카르테시안 곱 — 이 거기서 파생됩니다.
여기까지 따라오셨다면 한 번쯤 이런 의심이 드실 거예요. "임의의 조건으로 자유롭게 집합을 모을 수 있다면, 뭔가 위험한 일이 일어나지 않을까?" 정확한 직감입니다. 1901년 버트런드 러셀(Bertrand Russell)이 그 위험을 정확히 짚었어요.
러셀의 역설
"자기 자신을 원소로 포함하지 않는 모든 집합의 집합"을 \(R\)이라고 하자:
\[ R = \{ S : S \notin S \}. \]
이제 \(R \in R\)인가? \(R \in R\)이라면 \(R\)의 정의상 \(R \notin R\). 반대로 \(R \notin R\)이라면 정의상 \(R \in R\). 어느 쪽도 안 됩니다.
이건 또 대각선 논법의 변형이에요(이쯤 되면 패턴이 보이죠). 그리고 이 역설은 19세기 말 프레게가 막 완성하려던 "조건만 있으면 어떤 집합이든 만들어진다"는 소박한 집합론을 무너뜨립니다. 프레게는 책이 인쇄소에 있을 때 러셀의 편지를 받고 충격을 받았다는 일화가 유명해요.
해법은 "어떤 조건이든 집합을 만든다"를 포기하는 것입니다. 대신 더 신중하게, 안전한 방식으로만 집합을 만들 수 있도록 공리를 깔아요. 그게 ZFC의 핵심 아이디어입니다. 예를 들어 "이미 있는 집합 \(A\) 안에서 조건 \(\varphi\)를 만족하는 원소들만 모은다"는 분리 공리만 허용하면 \(R = \{S : S \notin S\}\) 같은 정체불명의 모음은 원천 차단됩니다. \(R\)을 만들려면 "모든 집합"이라는 모집단이 있어야 하는데, ZFC는 그것을 집합으로 인정하지 않거든요.
그럼 ZFC 자체가 무모순인지는 어떻게 아나요? 슬프게도, 안에서 증명할 수 없습니다. 1931년 쿠르트 괴델(Kurt Gödel)의 불완전성 정리가 이걸 보여줬어요.
괴델 불완전성 정리 (대단히 요약)
충분히 강력한(산술을 표현할 수 있는) 무모순 공리계는, 자기 안에서 자신의 무모순성을 증명할 수 없다. 또한 그런 공리계 안에는 참이지만 증명할 수 없는 명제가 존재한다.
이 정리는 "수학 전체를 단 하나의 완전한 공리계로 환원하자"는 힐베르트의 꿈을 영구히 종결시켰습니다. 흥미롭게도 괴델의 증명도 핵심에 자기참조와 대각선 기법이 있어요. "이 명제는 증명 불가능하다"라는 명제를 산술 안에서 코딩한 다음, 정지 문제 비슷한 모순 구조를 끌어냅니다.
또 하나, 앞서 잠깐 언급한 연속체 가설 — "\(\aleph_0 < \kappa < \mathfrak{c}\)인 무한 기수 \(\kappa\)는 없다" — 도 운명이 비슷합니다. 괴델(1940)과 코언(1963)의 결과를 합치면, 연속체 가설은 ZFC로 증명할 수도 반증할 수도 없습니다. 즉 ZFC와 독립이에요. "참인지 거짓인지 정해지지 않은 명제가 있다"는 게 아니라, "ZFC가 결정해주지 않는 명제가 있다"는 거죠. 누군가는 이걸 두고 "수학은 우리가 생각한 것보다 자유롭다"고 말하기도 합니다.
노트
이 모든 위태로움에도 불구하고, 일상의 수학과 컴퓨터과학은 ZFC 위에서 잘 작동합니다. 마치 일상의 물리학이 양자역학의 측정 문제와 무관하게 잘 굴러가듯이요. ZFC가 모순일 가능성을 완전히 배제할 순 없지만, 100년 넘게 모순이 발견되지 않았고 그 안에서 우리가 쓰는 모든 수학적 도구가 일관되게 작동합니다. 이산수학을 공부하는 입장에선 "기초가 단단하다"고 안심하고 위층 작업에 집중하면 됩니다. 다만 가끔, 이렇게 가끔, 토대가 어떻게 깔렸는지 들춰보는 것도 나쁘지 않아요.
이 챕터를 한 줄로 요약하면 이렇습니다. 무한은 한 종류가 아니고, 어떤 무한은 다른 무한보다 진짜로 크다. 그 사실을 증명한 도구(대각선 논법) 하나로 우리는 비가산성, 정지 문제의 결정 불가능성, 멱집합의 위계, 그리고 러셀과 괴델의 역설까지 한 번에 꿰뚫었습니다. 한 기법이 이렇게 멀리 데려다주는 경우는 흔치 않아요. 마음이 살짝 흔들렸다면, 정상입니다.