대각선 논법

• 상위 문서: 게오르크 칸토어
• 관련 문서: 수 체계, 초한기수, 연속체 가설

Cantor's Diagonal Argument
칸토어의 대각선 논법

1 개요

게오르크 칸토어가 자연수의 집합과 실수의 집합의 원소의 개수가 서로 다르다는 것을 증명할때 사용했던 논법이다. 이전까지 수학계에서 함부로 다루지 않던 무한의 개수에 대한 한 획을 그은 증명. 이후에 연속체 가설로 이어지며 힐베르트의 23가지 문제에도 포함되었다.

2 상세

칸토어에 의하여 제시된 대각선 논법은 실수에서 먼저 쓰인 것이다. 실수 집합의 크기가 자연수 집합의 크기와 같지 않다는 것을 증명하는 데에 쓰인 것이다. 그리고 그 논법이 임의의 집합과 그 멱집합(power set 부분집합들의 집합)에 적용된 것이고. 순서대로 살펴 보자.

2.1 집합의 크기라는 것의 의미

먼저 몇 가지 직관과 벗어나 보이는 사실들을 짚고 가자. 자연수 집합과 정수 집합, 그리고 심지어 유리수 집합의 크기는 모두 같다. 이것은 수 체계에서 간단히 언급된 것이다. 유리수 집합이 자연수들을 모조리 포함하면서도 자연수가 아닌 수들을 포함하고 있다는 당연한 사실을 보면 둘의 크기가 같다는 것을 납득하기 어려울 수도 있겠다. 이러한 직관과 사실의 차이는 집합의 '크기' 혹은 '크기의 대소 비교'로부터 비롯된다. 두 집합 [math]A, B[/math] 간의 대소 비교는 다음으로 정의된다.

1. 한 일대일 대응(bijection) [math]A \to B[/math]가 존재하면 [math]A[/math]와 [math]B[/math]의 크기는 같다고 한다. 즉 [math]A[/math]와 [math]B[/math] 사이에 전단사함수가 존재한다.
2. 한 일대일 사상(injection) [math]A \to B[/math]가 존재하면 [math]A[/math]의 크기는 [math]B[/math]의 크기보다 작거나 같다고 한다. 즉 [math]A[/math]에서 [math]B[/math]로 가는 단사함수가 존재한다.

일대일 사상은 [math]A[/math]의 각 원소가 [math]B[/math]의 원소에 겹침 없이 보내진다는 것이다. 즉, [math]A[/math]의 두 다른 원소 [math]a, a'[/math]에 대해 사상을 취한 결과는 서로 달라야 한다는 것이다. 대표적인 예가 (정의역이 실수 집합의 부분집합일 때) [math]f\left(x\right)=x^3[/math] 혹은 [math]f\left(x\right)=e^x[/math]이고, 일대일 사상이 아닌 예로 [math]f\left(x\right) = x^2[/math]로 정의된 실수 전체에서 실수 전체로 보내지는 사상이다. 일대일 대응은 일대일 사상이면서 [math]B[/math]의 모든 원소가 [math]A[/math]의 한 원소에 대응되는 것인데, 말 그대로 [math]A[/math]와 [math]B[/math]의 각 원소들이 일대일로 매칭이 되는 상황이다. 예컨대 정의역과 공역을 실수 집합 전체로 잡았을 때 [math]f\left(x\right)=e^x[/math]로 정의된 함수는 0보다 작거나 같은 값으로 보내지는 [math]x[/math] 값이 없기에 이 함수는 일대일 대응이 아니다. 하지만 [math]f\left(x\right)=x^3[/math]는 일대일 대응이 된다. 다만, 모든 일대일 사상은 공역을 치역으로 제한한 새로운 사상을 만드는 것으로 일대일 대응을 만들 수 있다. 비록 원래 공역의 한 부분집합과 일대일 대응될 뿐이지만. 예컨대 [math]f\left(x\right)=e^x[/math]의 경우는 공역을 양의 실수 집합으로 제한하는 것으로 일대일 대응으로 만들 수 있다.

이 개념을 가지고 집합의 크기를 이해할 수 있다. 유한한 집합이라고 하는 것은 사실 원소 하나하나 세는 것으로 그 크기를 잴 수 있었다. 예를 들어 집합 [math]\left\{a, b, c, d, e, f, g\right\}[/math] 같은 경우 우리는 손가락으로 하나하나 카리키면서 하나(a), 둘(b), 셋(c), ..., 일곱(g) 끝 하는 식으로 헤아려서 그 집합의 '크기'가 7이라고 말한다. 그런데 이렇게 하나하나 헤아린다는 것은 원소 하나하나에 자연수를 하나 씩 대응시키는 작업과 같다. 그리고 방금 든 예의 경우 하나 씩 대응시키면서 남거나 모자르는 일 없이 대응이 될 수 있는 경우는 [math]\left\{1, 2, 3, 4, 5, 6\right\}[/math]도 아니고 [math]\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}[/math]도 아닌 [math]\left\{1, 2, 3, 4, 5, 6, 7\right\}[/math]인 경우였다. 그런데 사실 세는 방법은 하나만 있는 것이 아니다. g부터 거꾸로 셀 수도 있고 b부터 셀 수도 있고... 아무튼 많다. 다만 어떻게 세든 간에 결국 그런 일대일 대응이 최소 하나는 존재한다는 것만 주목하면 된다. 그러고 보면 [math]\left\{1, 2, 3, 4, 5, 6\right\}[/math]나 [math]\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}[/math] 같은 경우에는 어떻게 해도 일대일 대응은 단 하나도 만들 수 없잖은가. 바로 이런 점을 봤을 때 결국 집합의 크기를 잰다는 것은 어떤 집합 [math]\left\{1, 2, 3, \cdots, n\right\}[/math]와 일대일 대응을 시키는 작업이라고 볼 수 있을 것이다.

하지만 여기서 끝나지 않는다. 사실 문제가 좀 있다. 어떤 사람은 [math]\left\{1, 3, 5, 7, 9, 11, 13\right\}[/math]도 되지 않느냐고 따질 수도 있다. 또한 자연수 집합 전체나 유리수 집합의 경우에는 [math]\left\{1, 2, 3, \cdots, n\right\}[/math] 같은 집합과 어떻게 해도 대응되지 않는다. 이런 점들을 봤을 때 집합의 크기를 정함에 있어 [math]\left\{1, 2, 3, \cdots, n\right\}[/math] 같은 것에 벗어나야 좀 더 일반적인 '크기'를 말할 수 있을 것 같아 보인다. 그러고 보면 사실 위의 예에서 중요한 건 일대일 대응이 하나라도 존재하는가 하는 것이었다.

결국 집합의 크기 혹은 그 대소 비교는 위와 같이 일대일 대응의 존재 유무만 남게 되었다. 그야말로 '하나하나 헤아린다'를 극한으로 추상화시킨 것이다. 한편, [math]\left\{1, 2, 3, \cdots, n\right\}[/math] 같은 집합으로 어떻게 해도 자연수 전체 집합과는 일대일 대응을 만들 수 없지만 일대일 사상은 만들 수 있다는 것으로부터 같냐 안 같냐만 말할 수 있는 것이 아니라 대소 비교도 정의할 수 있게 되는 것이다. 부분집합과 일대일 대응이 가능해도 전체와 대응이 안 될 때 정의역 집합이 공역 집합보다 더 작다고 말하는 것은 자연스러워 보이기 때문이다. 그래서 위와 같은 정의가 가능해진 것이다.

다시 맨 처음의 자연수 집합과 정수 집합, 유리수 집합으로 돌아가자. 이 셋의 크기가 같다는 것은 결국 셋 간에 일대일 대응이 존재한다는 것이다. 대충 말해 이것은 지그재그로 정수 집합과 유리수 집합을 헤아리는 것으로 가능한 작업이다. 자세한 것은 여기서 다루지 않겠지만 (집합론 교재를 참고할 것) 어쨌든 일대일 대응이 존재하긴 한다. 추상화가 예상치도 못한 결과를 가져다 준다는 좋은 예시로 볼 수 있겠다.

아무튼 칸토어는 이런 작업 이후 어쩌면 모든 무한 집합([math]\left\{1, 2, 3, \cdots, n\right\}[/math] 같은 것과 일대일 대응이 되지 않는 집합)이 전부 다 자연수 집합과 같은 크기를 가지지 않을까 하는 추측을 하게 된다. 하지만 이런 기대는 칸토어 본인의 손에 의해 무너지게 된다.

2.2 대각선 논법 - 실수 집합은 자연수 집합보다 크다

제목 그대로이다. 증명은 굉장히 직관적이다. 먼저 문제를 간단하게 하기 위해 실수 전체 대신 구간 [math]\left(0,\,1\right)[/math]로 문제를 제한할 수 있다. 사실 함수 [math]f : \left(0, 1\right) \to R \left( f\left(x\right) = \tan{\left( \pi x - \frac{\pi}{2} \right)} \right)[/math] 때문에 실수 전체 집합과 구간 [math]\left(0,\,1\right)[/math]의 크기가 같다는 것을 알 수 있고, 따라서 자연수와 구간 [math]\left(0,\,1\right)[/math]만 그 크기를 비교하면 끝이다.

먼저 자연수 집합에서 구간 [math]\left(0,\,1\right)[/math]로 보내지는 어떤 함수 [math]f[/math]가 존재한다고 가정하자. 이때 각 [math]f\left(n\right)[/math]는 다음과 같이 소수 꼴로 표현될 수 있을 것이다.

[math]f\left(1\right) = 0.a_{11} a_{12} a_{13} a_{14} a_{15} \cdots[/math]
[math]f\left(2\right) = 0.a_{21} a_{22} a_{23} a_{24} a_{25} \cdots[/math]
[math]f\left(3\right) = 0.a_{31} a_{32} a_{33} a_{34} a_{35} \cdots[/math]
[math]f\left(4\right) = 0.a_{41} a_{42} a_{43} a_{44} a_{45} \cdots[/math]
[math]f\left(5\right) = 0.a_{51} a_{52} a_{53} a_{54} a_{55} \cdots[/math]
[math]\cdots[/math]

여기서 각 [math]a_{ij}[/math]는 0부터 9까지의 어떤 정수들이다. 이런 식으로 모든 소수([math]0[/math]과 [math]1[/math] 사이의 수)들이 하나도 빠짐없이 한 자연수에 겹침 없이 대응된 상황이다. 참고로 혼돈을 피하기 위해 [math]0\cdots 999\cdots[/math]같은 어딘가서부터 9로만 이루어진 표현은 없다고 치자. 어차피 저런 경우는 적당한 유한 소수, 즉 어딘가서부터 0으로만 나타나는 표현으로 쓸 수 있기 때문이다. 즉, [math]0.0999\cdots[/math]같은 것은 어차피 [math]0.10000\cdots[/math]과 같으니 쓰지 않는 것으로 말이다. 이렇게 소수를 표현했을 때 얻을 수 있는 것이 뭐냐면, 만약 두 소수가 어느 딱 한 자리만이라도 서로 다르다면 두 수는 다른 수가 되는 것이다.

모든 [math]0[/math]과 [math]1[/math]사이의 수들이 [math]f[/math]로 인해 한 자연수에 빠짐 없이 대응된다고 했었다. 즉, 어떤 것을 고르든 [math]0[/math]과 [math]1[/math] 사이의 수는 어떤 [math]f\left(n\right)[/math] 중 하나와 같아야 한다. 그러면 지금부터 어느 [math]f\left(n\right)[/math]와 같지 않은 [math]0[/math]과 [math]1[/math] 사이의 수를 만들어 보도록 하겠다.

[math]x = 0.b_1 b_2 b_3 \cdots[/math]를 이렇게 정의하자. 각 자연수 [math]i[/math]에 대해 [math]b_i[/math]가 [math]a_{ii}[/math]와 다르도록 말이다. 그러면 [math]x[/math]는 모든 자연수 [math]n[/math]에 대하여 [math]f\left(n\right)[/math]와 [math]n[/math]번째 자리 수에서 다르게 된다. 예를 들어 [math]f\left(3\right)[/math]의 3번째 자리 수가 7이라고 하자. 그러면 [math]x[/math]의 3번째 자리 수는 7과는 다른 수로 잡는 것이다. 더 구체적인 예로 다음과 같이 [math]x[/math]를 정하자는 것이다.

[math]f\left(1\right) = 0.\; 3 \;\; a_{12} a_{13} a_{14} a_{15} \cdots[/math]
[math]f\left(2\right) = 0.a_{21} \; 1 \;\; a_{23} a_{24} a_{25} \cdots[/math]
[math]f\left(3\right) = 0.a_{31} a_{32} \; 7 \;\; a_{34} a_{35} \cdots[/math]
[math]f\left(4\right) = 0.a_{41} a_{42} a_{43} \; 8 \;\; a_{45} \cdots[/math]
[math]f\left(5\right) = 0.a_{51} a_{52} a_{53} a_{54} \; 9 \;\; \cdots[/math]
[math]\cdots[/math]
[math]x \;\;\;\;\; = 0.\; 5 \;\;\; 4 \;\;\; 2 \;\;\; 9 \;\;\; 6 \;\; \cdots[/math]

모든 대각선에서 [math]x[/math]와 [math]f\left(n\right)[/math]가 다르다. 따라서 [math]x[/math]는 모든 [math]f\left(n\right)[/math]와 최소 한 자리에서 다르다. 아까 소수의 표현에 대한 설명으로부터 이는 [math]x[/math]가 모든 [math]f\left(n\right)[/math]와 다르다는 것을 밝혀준다. 우리가 찾던 수이다. 그리고 이것은 위에 강조 처리한 문장 바로 전의 말과 모순인 결론이다. 모순이 생겼으므로 우리는 맨 처음에 했던 가정을 포기해야 한다. 즉, 자연수 집합과 실수 집합 간에는 일대일 대응이 존재할 수 없다는 것이다.

위 식들로부터 칸토어의 논증 방법은 대각선 논법이라는 이름을 얻게 되었다. 이와 비슷한 방식을 일반적인 집합에 적용시킬 수 있다. 그걸 바로 아래에서 다루도록 하겠다.

2.3 대각선 논법 - 어떤 집합도 자신의 멱집합(power set)보다 작다

멱집합(power set)은 주어진 집합의 부분집합을 모두 모은 집합이다. 주어진 집합이 [math]A[/math]로 표기될 경우 기호로는 [math]\mathcal{P}\left(A\right)[/math]로 표기된다. 이제 할 일은 임의의 [math]A[/math]에 대해 [math]A[/math]와 [math]\mathcal{P}\left(A\right)[/math] 간에 일대일 대응 같은 건 존재하지 않는다는 것을 보이는 것이다.

논리적인 어려움을 피하기 위해 먼저 [math]A[/math]가 공집합인 경우를 따로 살펴 보자. 참고로 이때 [math]\mathcal{P}\left(A\right)[/math]는 [math]\left\{\emptyset\right\}[/math]으로 원소가 하나는 있다. 당연히 일대일 대응 따윈 없다.

이제 [math]A[/math]가 공집합이 아닌 경우를 살펴 보자. 그리고 위에서 그랬듯이 일대일 대응 [math]f : A \to \mathcal{P}\left(A\right)[/math]가 존재한다고 가정하자. 그러면 [math]A[/math]의 모든 부분집합들, 그러니까 [math]\mathcal{P}\left(A\right)[/math]의 모든 원소들은 [math]f\left(a\right)[/math] ([math]a \in A[/math])들 중 하나이다. 이제부터 보일 일은 위에서 그랬던 것처럼 [math]f\left(a\right)[/math]들 중 어느 것과도 같지 않은 [math]A[/math]의 부분집합을 찾아내는 것이다.

실수의 경우에는 [math]f\left(n\right)[/math]와 다르게 하기 위해 [math]n[/math]번째 자리가 다르도록 해서 새로운 수를 정했었다. 집합의 경우면 뭘까? 이걸 그대로 적용시킨다면 아무래도 새로운 집합 [math]X[/math]는 어떤 [math]f\left(a\right)[/math]와 [math]a[/math] 때문에 달라야 할 것이다. 집합의 언어에서 이걸 가지고 생각할 만한 것은 딱 하나. 원소 [math]a[/math]가 들어가느냐 마느냐 하는 것이다. 따라서 가장 좋은 생각은 아무래도 [math]f\left(a\right)[/math]가 [math]a[/math]를 포함하고 있는가 아닌가를 [math]X[/math]는 반대로 되어 있도록 하는 것이다.

이걸 가지고 [math]X[/math]를 이렇게 만들 수 있을 것이다.

[math]X = \left\{a \in A \; | \; a \notin f\left(a\right)\right\}[/math].

[math]X[/math]는 [math]A[/math]의 원소들로 이루어져 있으므로 [math]A[/math]의 부분집합이고, 따라서 [math]f\left(a\right)[/math]들 중 하나와 같을 것이다. 그런데

• [math]a \in f\left(a\right)[/math]인 경우 : 정의에 의해 [math]a \notin X[/math]이므로 [math]X \ne f\left(a\right)[/math].
• [math]a \notin f\left(a\right)[/math]인 경우 : 정의에 의해 [math]a \in X[/math]이므로 [math]X \ne f\left(a\right)[/math].

결국 어느 [math]f\left(a\right)[/math]와도 같지 않음을 알 수 있다. 이는 모순이다. 따라서 [math]A[/math]와 [math]\mathcal{P}\left(A\right)[/math] 간에는 일대일 대응이 존재하지 않는다.

한편 [math]g : A \to \mathcal{P}\left(A\right), a \mapsto \left\{a\right\}[/math]와 같이 정의된 사상은 일대일 대응이 아닌 일대일 사상이다. 이것으로부터 모든 집합은 그 power set보다 작다는 것을 알 수 있다.

참고로 [math]Q = \left\{f \;|\; f : A \to \left\{0, 1\right\}\right\}[/math]로 두면 [math]\mathcal{P}\left(A\right)[/math]와 [math]Q[/math] 간에 일대일 대응이 존재한다는 것을 보일 수 있다.

두 집합 [math]X, Y[/math]가 주어져 있을 때 [math]Y^X = \left\{f \;|\; f : X \to Y\right\}[/math]로 표기한다. 이 표기대로라면 사실 [math]Q = \left\{0, 1\right\}^A[/math]인 것이다. 또한 [math]X[/math], [math]Y[/math]의 크기를 [math]\left|X\right|[/math], [math]\left|Y\right|[/math]라 적는다. , [math]\left|X\right|^{\left|Y\right|} = \left|X^Y\right|[/math]로 정의한다. 따라서 [math]\left|\mathcal{P}\left(A\right)\right| = \left|Q\right| = \left|\left\{0, 1\right\}^A\right| = 2^{\left|A\right|}[/math]가 되는 것이다. 위에서 보인 내용은 다름 아닌

[math]\left|A\right| \lneq 2^{\left|A\right|}[/math]

임을 보인 것이다.

2.4 대각선 논법 - 어떠한 튜링 기계도 (유한 시간 내에) 풀 수 없는 문제가 존재한다

임의의 (이진 언어) 튜링 머신 M은 그 기작을 어떤 프로그래밍 언어로 기술할 수 있고 (브레인퍽 등) 따라서 (이진) 코드 <M>으로 이것을 나타낼 수 있다. 나아가, (이진 언어) 튜링 머신과 그 입력값의 쌍 (M,w)에 대해, 이것을 돌리면 M은 yes를 뱉으면서 멈추거나, no를 뱉으면서 멈추거나, 그냥 영원히 돌아갈 수 있을 것이다. 이 때 주어진 (이진 언어) 튜링 머신 M에 대해 (이진) 입력값의 모임

L(M) = {w | (M,w)를 돌리면 yes를 뱉고 멈춘다}

로 정의하자. (이것을 M이 푸는/결정하는 문제(the problem that M decides)라 부른다.)

L(M)은 단순히 (이진) 코드의 모임임에도 문제라는 표현을 쓰는 데에는 약간의 배경이 있다. 임의의 참/거짓을 확실히 가릴 수 있는 문제는, 적절한 데이터 구조 아래에서 이 구조가 이런이런 조건을 만족하느냐는 것으로 말을 바꿀 수 있다. 이 데이터 구조는 항상 이진 코드로 나타낼 수 있고, 따라서 대개의 참/거짓 문제는 이진 코드의 집합 [math] S \subset \{ 0,1 \}^{\ast} [/math]으로 나타난다. 간단히, 뭔가 답이 필요한 입력이 있으면 입력을 이진코드화 해서 S에 들어가는지 아닌지로 체크해서 들어가면 ㅇㅋ 하고 끝내면 문제 해결 개이득!인 셈.

이제 문제는 임의의 부분집합 [math] S \subset \{ 0,1 \}^{\ast} [/math]이 튜링 머신이 결정하는 문제로 환원이 되느냐인데... 이미 이게 가산인지 아닌지 미리 견적 내 봤으면 답은 알고 있을 것이다 이 절의 제목에서 추론되듯 그런 것 없다. 앞 절과 같은 방법으로 [math] L \colon \{ \text{Turing machines} \} \to \mathcal{P} ( \{ 0,1 \}^{\ast} ) [/math]으로 해석, 앞 절의 [math]\{ a \; | \; a \notin f(a) \} [/math]와 등가인 방법을 쓴다.

튜링 머신의 코드의 집합 [math] S = \{ \langle M \rangle \; | \; \langle M \rangle \notin L(M) \} [/math]을 생각하자. 이 떄 [math] S = L(N) [/math]인 튜링 머신 N이 존재하는지를 여기서 물을 것이다. 그러한 N이 존재한다고 하자. 그러면,

• [math] \langle N \rangle \in S [/math]인 경우, S의 정의에 의해 [math] \langle N \rangle \notin L(N)=S [/math]이므로 모순.
• [math] \langle N \rangle \notin S = L(N) [/math]인 경우, S의 정의에 의해 [math] \langle N \rangle \in S [/math]이므로 모순.

으로 (러셀의 역설에서 봤던) 논리가 그대로 성립한다. 따라서 [math] S = L(N) [/math]인 튜링 머신은 존재하지 않는다.

즉, 위에서 쓴 [math] L \colon \{ \text{Turing machines} \} \to \mathcal{P} ( \{ 0,1 \}^{\ast} ) [/math]은 모든 [math] \{ 0,1 \}^\ast [/math]의 부분집합을 커버하지 못한다. 따라서 어떤 튜링 머신이 풀지 못하는 문제가 존재하게 된다.

2.5 러셀의 역설 - 모든 집합의 집합은 존재하지 않는다

멱집합과 튜링 머신에 대한 대각선 논법은, 둘 다 원소 단계의 객체 a를 집합 단계의 객체 f(a)로 보낸 후, a가 f(a)에 속하지 않는 a의 모임을 찾아내 이것이 f(b) 꼴로 나타날 수 없다는 방법을 쓰고 있다. 실수에 대한 대각선 논법 또한 크게 다르지 않아, 근본적으로는 자연수의 멱집합 [math] \mathcal{P} (\mathbb{N}) [/math]과 0과 1 사이의 실수와 대응하는 데에서 출발한다.

러셀의 역설은 직관적 집합론이 모순이 있다는 것을 밝히는 것 외에도, 임의의 집합의 집합 S에 대해, [math] B = \{ X \in S \; | \; X \notin X \} [/math]라는 S에서 보이지 않는 새 집합을 만들어내는 수순으로 볼 수 있다. X를 S의 원소 단계의 객체로 볼 수도, (X 자체가 집합이니까) 집합 단계의 객체로 볼 수 있기 때문. 이 B를 만들어내는 과정 자체도 대각선 논법의 일종으로, 그 따름정리로 다음을 얻는다.

어떤 집합의 집합 S에 대해, S보다 더 큰 집합의 집합이 존재한다.

곧, 모든 집합의 모임은 "집합 수준의" 크기로는 도저히 담을 수 없을 정도로 크다는 뜻으로 받아들일 수 있다. 즉, 대각선 논법은 집합을 초월하는 크기에 대해서도 그 크기 비교를 할 수 있는 것.

3 의의

수학사적으로 칸토어 이전에 '무한'이라는 것을 이렇게 체계적으로 다룬 사람은 없었다. 심지어 무한이라는 것을 다루는 것을 금기시할 정도였다. 하지만 집합론이 발달하기 위해선 무한집합을 제대로 이해할 필요가 있었고, 칸토어는 최초로 이를 해낸 사람인 것이다. 그 성과 중 하나가 무한의 크기는 다양하다이고 위에서 보인 것이 바로 그 사실이다. 자연수 집합이 무한집합이고 그 어떤 집합보다 커 보였지만 사실 더 큰 집합이 존재하고 사실 그 어떤 (무한)집합을 택해도 그 집합보다 더 큰 집합이 존재한다는 것을 밝힌 것이다.

이런 놀라운 결과는 수학계에서 바로 받아들여지지 못했다. 칸토어의 말년이 불우했던 까닭도 여기서 찾을 수 있다. 하지만 집합의 성질들이 수학의 영역에서 갈 수록 중요해지면서 후대 수학자들은 칸토어의 집합론을 받아들이기 시작했고 더더욱 발전시켰다.

한편 우리는 임의의 집합 [math]A[/math]에 대해 [math]|A| \lt 2^{|A|}[/math]임을 봤었다. 사실 모든 무한집합은 자연수와 크기가 같은 부분집합을 포함한다. 이는 자연수 집합이 무한집합들 중에서 제일 작은 집합이라는 것을 의미한다. 수학자들은 자연수 집합의 크기를 흔히 [math]\aleph_0[/math]로 표기한다. 한편, 우리가 아는 상당 수의 집합들이 사실은 (안 그래 보여도) 자연수 집합과 크기가 같다는 것을 설명했었고, 그러면서도 실수 집합은 그 크기가 [math]2^{\aleph_0}[/math]임을 알았다. 그리고 흔히 [math]c = 2^{\aleph_0}[/math]로 표현한다. 사실 자연수를 포함하거나 혹은 우리가 잘 아는 수 체계로부터 출발하여 얻어진 집합들 중에 [math]\aleph_0[/math] 혹은 [math]c[/math]가 아녔던 것은 거의 없었다. 있다 해도 [math]2^{c}[/math]라든가 혹은 이것의 또다른 지수 같은 것이었을 뿐이었다.

여기서 한 가지 질문을 할 수 있다. 그러면 [math]\aleph_0 \lt |X| \lt c[/math]를 만족하는 집합 [math]X[/math]가 존재하는가? 해봄직한 질문이긴 한데 문제는 어느 누구도 저런 집합을 찾지 못 하였고 그러면서도 저런 집합이 없다고 밝힌 사람은 또 없었다는 것이다. 왠지 있을 것 같은데 전혀 안 보이고 그렇다고 없다고 말할 수도 없으니 사람들은 아리송할 수 밖에. 저런 집합이 존재하지 않을 거라고 가정하는 것을 가리켜 연속체 가설(Continuum Hypothesis)라고 부른다. 그리고 잘 알려져 있다시피 연속체 가설이 맞느냐 틀리느냐를 밝히라는 게 바로 힐베르트의 23가지 문제 중 첫번째 문제였다.

결론부터 말하자면 이 문제는 풀렸다. 그런데 그 답이 또 골 때린다. 맞다고 가정해도 문제 없고 틀렸다고 가정해도 문제 없다가 답이다. 즉 저 가설의 참과 거짓 어느 것을 주장해도 수학을 모순 없이 잘 전개할 수 있다는 것이다.