대각선 논법
1. 개요
diagonal argument · 對角線 論法
게오르크 칸토어가 자연수의 집합과 실수의 집합의 원소의 개수가 서로 다르다는 것을 증명할때 사용했던 방법이다. 이전까지 수학계에서 함부로 다루지 않던 무한의 개수를 다루며 한 획을 그은 증명. 이후에 연속체 가설로 이어지며 힐베르트의 23가지 문제에도 포함되었다.
2. 상세
칸토어가 제시한 대각선 논법은 실수 집합의 크기가 자연수 집합의 크기와 같지 않다는 것을 증명하는 데에 쓰인 것이다. 그리고 그 논법이 임의의 집합과 그 멱집합(power set, 부분집합들의 집합) 사이의 크기 비교에도 적용된 것. 순서대로 살펴 보자.
2.1. 집합의 크기라는 것의 의미
먼저 직관에서 벗어나 보이는 몇 가지 사실들을 짚고 가자. 자연수 집합과 정수 집합, 그리고 심지어 유리수 집합의 크기는 모두 같다. 이것은 수 체계에서 간단히 언급된 것이다. 유리수 집합이 자연수들을 모조리 포함하면서도 자연수가 아닌 수들을 포함하고 있다는 것을 생각해보면 보면 둘의 크기가 같다는 것을 납득하기가 어려울 수도 있다. 이러한 사실들과 직관 사이의 괴리는 집합의 '크기' 혹은 '크기의 대소 비교'로부터 비롯된다. 두 집합 $$A, B$$ 간의 대소 비교는 다음으로 정의된다.
- 한 일대일 대응(bijection) $$A \to B$$가 존재하면 $$A$$와 $$B$$의 크기는 같다고 한다. 즉 $$A$$와 $$B$$ 사이에 전단사함수가 존재한다.
- 한 일대일 사상(injection) $$A \to B$$가 존재하면 $$A$$의 크기는 $$B$$의 크기보다 작거나 같다고 한다. 즉 $$A$$에서 $$B$$로 가는 단사함수가 존재한다.
이 개념을 가지고 집합의 크기를 이해할 수 있다. 유한한 집합이라고 하는 것은 사실 원소 하나하나 세는 것으로 그 크기를 잴 수 있었다. 예를 들어 집합 $$\left\{a, b, c, d, e, f, g\right\}$$ 같은 경우 우리는 손가락으로 하나하나 카리키면서 하나(a), 둘(b), 셋(c), ..., 일곱(g) 끝 하는 식으로 헤아려서 그 집합의 '크기'가 7이라고 말한다. 그런데 이렇게 하나하나 헤아린다는 것은 원소 하나하나에 양의 정수를 하나 씩 대응시키는 작업과 같다. 그리고 방금 든 예의 경우 하나 씩 대응시키면서 남거나 모자르는 일 없이 대응이 될 수 있는 경우는 $$\left\{1, 2, 3, 4, 5, 6\right\}$$도 아니고 $$\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$$도 아닌 $$\left\{1, 2, 3, 4, 5, 6, 7\right\}$$인 경우였다. 그런데 사실 세는 방법은 하나만 있는 것이 아니다. g부터 거꾸로 셀 수도 있고 b부터 셀 수도 있고... 아무튼 많다. 다만 어떻게 세든 간에 결국 그런 일대일 대응이 최소 하나는 존재한다는 것만 확인하면 된다. 이러한 점을 고려해보면 결국 집합의 크기를 센다는 것은 어떤 양의 정수 $$n$$보다 작거나 같은 양의 정수들의 집합 $$\left\{1, 2, 3, \cdots, n\right\}$$와 그 집합을 일대일 대응을 시키는 작업으로 보면 될 것 같다.
하지만 다음과 같은 문제가 있다. 어떤 사람은 $$\left\{1, 3, 5, 7, 9, 11, 13\right\}$$도 되지 않느냐고 따질 수도 있다. 또한 자연수 집합 전체나 유리수 집합의 경우 아무리 큰 양의 정수 $$n$$이 주어지든 $$\left\{1, 2, 3, \cdots, n\right\}$$ 같은 집합과는 일대일 대응이 존재하지 않는다. 이런 점들을 봤을 때 집합의 크기를 정함에 있어 $$\left\{1, 2, 3, \cdots, n\right\}$$ 같은 것에 벗어나야 좀 더 일반적인 '크기'를 말할 수 있을 것 같아 보인다. 사실 위의 예에서 중요한 건 '''일대일 대응이 하나라도 존재하는가''' 하는 것이었다.
결국 집합의 크기 혹은 그 대소 비교는 위와 같이 일대일 대응의 존재 유무만 남게 되었다. 그야말로 ''''하나하나 헤아린다'를 추상화'''시킨 것이다. 한편, $$\left\{1, 2, 3, \cdots, n\right\}$$ 같은 집합과 자연수 전체 집합 사이에는 일대일 대응이 존재하지 않지만 일대일 사상은 만들 수 있다는 것으로부터 같냐 안 같냐만 말할 수 있는 것이 아니라 대소 비교도 정의할 수 있게 되는 것이다. 부분집합과 일대일 대응이 가능해도 전체와 대응이 안 될 때 정의역 집합이 공역 집합보다 더 작다고 말하는 것은 자연스러워 보이기 때문이다. 그래서 위와 같은 정의가 가능해진 것이다.
다시 맨 처음의 자연수 집합과 정수 집합, 유리수 집합으로 돌아가자. 거칠게 설명하자면 지그재그로 정수 집합과 유리수 집합을 헤아리는 것으로 가능하다. 자세한 것은 여기서 다루지 않겠지만 어쨌든 세 집합들 사이에는 일대일 대응이 존재하긴 한다.[2] 추상화가 예상치도 못한 결과를 가져다 준다는 좋은 예시로 볼 수 있겠다.
아무튼 칸토어는 이런 작업 이후 어쩌면 모든 무한 집합($$\left\{1, 2, 3, \cdots, n\right\}$$ 같은 것과 일대일 대응이 되지 않는 집합[3])이 전부 다 자연수 집합과 같은 크기를 가지지 않을까 하는 추측을 하게 된다. 하지만 이런 기대는 칸토어 본인의 손에 의해 무너지게 된다.
2.2. 대각선 논법 - 실수 집합은 양의 정수의 집합보다 크다
증명은 너무나도 직관적이고 아름다운 나머지 에르되시 팔은 이 증명을 '하느님이 가지고 있는 수학책'에 실려 있을 증명이라고 부를 정도였다.
먼저 문제를 간단하게 하기 위해 실수 집합 전체 대신 개구간 $$\left(0,\,1\right)$$을 사용한다. 사실 함수 $$f : \left(0, 1\right) \to \mathbb{R}$$를 $$f\left(x\right) = \tan{\left( \pi x - \frac{\pi}{2} \right)}$$로 정의하면 실수 전체 집합과 구간 $$\left(0,\,1\right)$$의 크기가 같다는 것을 알 수 있고, 따라서 양의 정수의 집합 $$ \mathbb{Z}^+$$과 구간 $$\left(0,\,1\right)$$의 크기만 비교하면 증명은 끝난다.
먼저 양의 정수의 집합에서 구간 $$\left(0,\,1\right)$$로 가는 전단사함수 $$f$$가 존재한다고 가정하자. 이때 각 $$f\left(n\right)$$는 다음과 같이 무한소수로 표현될 수 있을 것이다.
$$f\left(1\right) = 0.a_{11} a_{12} a_{13} a_{14} a_{15} \cdots$$
$$f\left(2\right) = 0.a_{21} a_{22} a_{23} a_{24} a_{25} \cdots$$
$$f\left(3\right) = 0.a_{31} a_{32} a_{33} a_{34} a_{35} \cdots$$
$$f\left(4\right) = 0.a_{41} a_{42} a_{43} a_{44} a_{45} \cdots$$
$$f\left(5\right) = 0.a_{51} a_{52} a_{53} a_{54} a_{55} \cdots$$
$$\cdots$$
여기서 각 $$a_{ij}$$는 [math(0)]부터 $$9$$까지의 어떤 자연수들이다. 이런 식으로 [math(0)]과 $$1$$ 사이의 모슨 실수들이 하나도 빠짐없이 하나의 양의 정수에 중복없이 대응된다. 참고로 혼돈을 피하기 위해 $$0\cdots 999\cdots$$ 같은 어딘가서부터 9로만 이루어진 표현은 없다고 치자. 어차피 이런 경우는 적당한 유한 소수, 즉 어딘가서부터 0으로만 나타나는 표현으로 쓸 수 있기 때문이다. 즉, $$0.0999\cdots$$같은 것은 어차피 $$0.10000\cdots$$과 같으니 쓰지 않겠다는 말이다. 이렇게 실수들을 무한소수로 표현하면 두 소수들의 어느 한 자리만 달라도 두 실수가 다르다는 것을 쉽게 확인할 수 있다.
가정에 따라 모든 [math(0)]과 $$1$$ 사이의 실수들이 $$f$$로 인해 하나의 양의 정수에 빠짐 없이 대응된다고 했다. 즉, [math(0)]과 $$1$$ 사이에 어떤 실수를 고르든 어떤 $$f\left(n\right)$$ 중 하나와 같아야 한다. 하지만 '''어떠한 $$f\left(n\right)$$과도 같지 않은 [math(0)]과 $$1$$ 사이의 어떤 실수를 제시할 수 있다'''.
[math(0)]과 $$1$$ 사이의 어떤 실수 $$x$$의 소수 $$i$$번째 자리의 수 $$b_{i}$$를 $$a_{ii}$$가 $$9$$보다 작은 자연수일 때는 $$a_{ii} + 1$$, $$9$$일 때는 $$a_{ii} - 1$$로 정의하자. 그렇다면 $$x = 0.b_1 b_2 b_3 \cdots$$일 것이다. 그리고 $$a_{ii}$$이 다음과 같다면
$$f\left(1\right) = 0.\; 3 \;\; a_{12} a_{13} a_{14} a_{15} \cdots$$
$$f\left(2\right) = 0.a_{21} \; 1 \;\; a_{23} a_{24} a_{25} \cdots$$
$$f\left(3\right) = 0.a_{31} a_{32} \; 9 \;\; a_{34} a_{35} \cdots$$
$$f\left(4\right) = 0.a_{41} a_{42} a_{43} \; 8 \;\; a_{45} \cdots$$
$$f\left(5\right) = 0.a_{51} a_{52} a_{53} a_{54} \; 5 \;\; \cdots$$
$$\cdots$$
즉 $$a_{11} = 3, a_{22} = 1, a_{33} = 9, a_{44} = 8, a_{55} = 5,\cdots$$이면
$$x$$는 정의에 따라 다음과 같다.
$$x=0.42896\cdots$$
그렇다면 모든 양의 정수 $$n$$에 대하여 '''$$f\left(n\right)$$과 $$x$$의 $$n$$번째 자리 수는 다르게 되고''' $$x$$는 모든 $$f\left(n\right)$$과 적어도 한 자리에서 다르다. 위의 소수 표현에 대한 설명으로부터 $$x$$가 모든 $$f\left(n\right)$$와 다르다는 것이 따라 나오고 이는 위에 강조 처리한 문장 바로 전의 말과 모순이다. 결국 처음에 했던 가정은 거짓이 된다. 즉, '''$$ \mathbb{Z}^+$$과 $$ \mathbb{R}$$ 간에는 일대일 대응이 존재하지 않는다'''는 것이다. 반면 $$ \mathbb{Z}^+$$은 $$ \mathbb{R}$$의 부분집합이므로 $$ \mathbb{R}$$의 크기는 $$ \mathbb{Z}^+$$의 크기보다 크거나 같다. 따라서 $$ \mathbb{R}$$의 크기는 $$ \mathbb{Z}^+$$보다 크다.
위와 같은 방식 덕분에 칸토어의 논증 방법은 '''대각선 논법'''이라는 이름을 얻게 되었다.[4] 이와 비슷한 방식을 일반적인 집합에 적용시킬 수 있다.
2.3. 대각선 논법 - 모든 집합은 자신의 멱집합(power set)보다 작다
멱집합(power set)은 주어진 집합의 부분집합을 모두 모은 집합이다. 주어진 집합이 $$A$$로 표기될 경우 기호로는 $$\mathcal{P}\left(A\right)$$로 표기된다. 이제 할 일은 임의의 $$A$$에 대해 '''$$A$$와 $$\mathcal{P}\left(A\right)$$ 간에 일대일 대응은 존재하지 않는다'''는 것을 보이는 것이다.
논리적인 어려움을 피하기 위해 먼저 $$A$$가 공집합인 경우를 따로 살펴 보자. $$\mathcal{P}\left(A\right)= \left\{\emptyset\right\} $$ 이므로 $$A = \emptyset\ $$과 일대일 대응이 존재하지 않는다.
이제 $$A$$가 공집합이 아닌 경우를 살펴 보자. 위에서 그랬듯이 일대일 대응 $$f : A \to \mathcal{P}\left(A\right)$$가 존재한다고 가정하자. 그러면 $$\mathcal{P}\left(A\right)$$의 모든 원소들, 즉 $$A$$의 모든 부분집합들은 $$f\left(a\right)$$ ($$a \in A$$)와 일대일 대응된다. 이제 할 일은 '''$$f\left(a\right)$$들 중 어느 것과도 같지 않은 $$A$$의 부분집합을 찾아내는 것'''이다.
실수의 경우에는 $$f\left(n\right)$$와 다르게 하기 위해 $$n$$번째 자리가 다르도록 해서 새로운 수를 정의했었다. 집합의 경우면 뭘까? 이걸 그대로 적용시킨다면 아무래도 집합 $$A$$의 어떤 부분집합 $$X$$는 $$f\left(a\right)$$와 $$a$$ 때문에 달라야 할 것이다. 집합론의 언어에서 이걸 가지고 생각할 만한 것은 딱 하나. 원소 $$a$$가 속하느냐 아니냐는 것이다. 따라서 가장 좋은 방법은 $$f\left(a\right)$$가 $$a$$를 원소로 가지느냐 아니냐에 대해서 $$X$$는 그 반대가 되게 하는 것이다.
그러므로 $$X$$를 다음과 같이 정의하자.
$$X = \left\{a \in A \; | \; a \notin f\left(a\right)\right\}$$.
$$X$$는 $$A$$의 원소로만 이루어져 있으므로 $$A$$의 부분집합이고, 그렇다면 $$X = f\left(e\right)$$가 되게 하는 어떤 $$e \in A$$가 존재할 것이다. 그런데
- $$e \in f\left(e\right)$$인 경우 : 정의에 의해 $$e \notin X$$이므로 $$X \ne f\left(e\right)$$.
- $$e \notin f\left(e\right)$$인 경우 : 정의에 의해 $$e \in X$$이므로 $$X \ne f\left(e\right)$$.
결국 $$X$$는 어느 $$f\left(a\right)$$와도 같지 않다는 결과를 얻을 수 있고, 이는 가정과 모순이다. 따라서 $$A$$와 $$\mathcal{P}\left(A\right)$$ 간에는 일대일 대응이 존재하지 않는다.
한편 $$g : A \to \mathcal{P}\left(A\right), a \mapsto \left\{a\right\}$$와 같이 정의된 사상은 일대일 대응이 아닌 일대일 사상이다. 이것으로부터 모든 집합은 그 power set보다 작다는 것을 알 수 있다.
참고로 $$Q = \left\{f \;|\; f : A \to \left\{0, 1\right\}\right\}$$로 두면 $$\mathcal{P}\left(A\right)$$와 $$Q$$ 간에 일대일 대응이 존재한다는 것을 보일 수 있다.[5]
두 집합 $$X, Y$$가 주어져 있을 때 $$Y^X = \left\{f \;|\; f : X \to Y\right\}$$로 표기한다. 이 표기대로라면 사실 $$Q = \left\{0, 1\right\}^A$$인 것이다. 또한 $$X$$, $$Y$$의 크기[6]를 $$\left|X\right|$$, $$\left|Y\right|$$라 적는다. [7], $$\left|X\right|^{\left|Y\right|} = \left|X^Y\right|$$로 정의한다. 따라서 $$\left|\mathcal{P}\left(A\right)\right| = \left|Q\right| = \left|\left\{0, 1\right\}^A\right| = 2^{\left|A\right|}$$가 되는 것이다. 위에서 보인 내용은 다름 아닌
$$\left|A\right| < 2^{\left|A\right|}$$
임을 보인 것이다.
2.4. 대각선 논법 - 어떠한 튜링 기계도 (유한 시간 내에) 풀 수 없는 문제가 존재한다
임의의 (이진 언어) 튜링 머신 M은 그 조작을 어떤 프로그래밍 언어로 기술할 수 있고 (브레인퍽 등) 따라서 (이진) 코드 <M>으로 이것을 나타낼 수 있다. 나아가, (이진 언어) 튜링 머신과 그 입력값의 쌍 (M,w)에 대해, 이것을 돌리면 M은 yes를 뱉으면서 멈추거나, no를 뱉으면서 멈추거나, 그냥 영원히 돌아갈 수 있을 것이다. 이 때 주어진 (이진 언어) 튜링 머신 M에 대해 (이진) 입력값의 모임
로 정의하자. (이것을 '''M이 푸는/결정하는 문제'''(the problem that M decides)라 부른다.)L(M) = {w | (M,w)를 돌리면 yes를 뱉고 멈춘다}
L(M)은 단순히 (이진) 코드의 모임임에도 문제라는 표현을 쓰는 데에는 약간의 배경이 있다. 임의의 참/거짓을 확실히 가릴 수 있는 문제는, 적절한 데이터 구조 아래에서 이 구조가 이런이런 조건을 만족하느냐는 것으로 말을 바꿀 수 있다. 이 데이터 구조는 항상 이진 코드로 나타낼 수 있고, 따라서 대개의 참/거짓 문제는 이진 코드의 집합 $$ S \subset \{ 0,1 \}^{\ast} $$으로 나타난다. 간단히, 뭔가 답이 필요한 입력이 있으면 입력을 이진코드화 해서 S에 들어가는지 아닌지로 체크해서 들어가면 ㅇㅋ 하고 끝내면 문제 해결 개이득!인 셈.
이제 문제는 임의의 부분집합 $$ S \subset \{ 0,1 \}^{\ast} $$이 튜링 머신이 결정하는 문제로 환원이 되느냐인데... 이 절의 제목에서 추론되듯 그런 것 없다. 앞 절과 같은 방법으로 $$ L \colon \{ \text{Turing machines} \} \to \mathcal{P} ( \{ 0,1 \}^{\ast} ) $$으로 해석, 앞 절의 $$\{ a \; | \; a \notin f(a) \} $$와 등가인 방법을 쓴다.
튜링 머신의 코드의 집합 $$ S = \{ \langle M \rangle \; | \; \langle M \rangle \notin L(M) \} $$을 생각하자.[8] 이 때 $$ S = L(N) $$인 튜링 머신 N이 존재하는지를 여기서 물을 것이다. 그러한 N이 존재한다고 하자. 그러면,
- $$ \langle N \rangle \in S $$인 경우, S의 정의에 의해 $$ \langle N \rangle \notin L(N)=S $$이므로 모순.
- $$ \langle N \rangle \notin S = L(N) $$인 경우, S의 정의에 의해 $$ \langle N \rangle \in S $$이므로 모순.
즉, 위에서 쓴 $$ L \colon \{ \text{Turing machines} \} \to \mathcal{P} ( \{ 0,1 \}^{\ast} ) $$은 모든 $$ \{ 0,1 \}^\ast $$의 부분집합을 커버하지 못한다. 따라서 어떤 튜링 머신이 풀지 못하는 문제가 존재하게 된다.
2.5. 러셀의 역설 - 모든 집합의 집합은 존재하지 않는다
멱집합과 튜링 머신에 대한 대각선 논법은, 둘 다 원소 단계의 객체 a를 집합 단계의 객체 f(a)로 보낸 후, a가 f(a)에 속하지 않는 a의 모임을 찾아내 이것이 f(b) 꼴로 나타날 수 없다는 방법을 쓰고 있다. 실수에 대한 대각선 논법 또한 크게 다르지 않아, 근본적으로는 자연수의 멱집합 $$ \mathcal{P} (\mathbb{N}) $$과 0과 1 사이의 실수와 대응하는 데에서 출발한다.
러셀의 역설은 직관적 집합론이 모순이 있다는 것을 밝히는 것 외에도, 임의의 집합의 집합 S에 대해, $$ B = \{ X \in S \; | \; X \notin X \} $$라는 S에서 보이지 않는 새 집합을 만들어내는 수순으로 볼 수 있다. X를 S의 원소 단계의 객체로 볼 수도, (X 자체가 집합이니까) 집합 단계의 객체로 볼 수 있기 때문. 이 B를 만들어내는 과정 자체도 대각선 논법의 일종으로, 그 따름정리로 다음을 얻는다.
곧, 모든 집합의 모임은 "집합 수준의" 크기로는 도저히 담을 수 없을 정도로 크다는 뜻으로 받아들일 수 있다. 즉, 대각선 논법은 집합을 초월하는 크기에 대해서도 그 크기 비교를 할 수 있는 것.어떤 집합의 집합 S에 대해, S보다 더 큰 집합의 집합이 존재한다.
3. 의의
수학사적으로 칸토어 이전에 '무한'이라는 것을 이렇게 체계적으로 다룬 사람은 없었다. 심지어 무한이라는 것을 다루는 것을 금기시할 정도로, 무한의 성질 때문에 제논의 역설이나 힐베르트의 호텔과 같은 이상한 일들이 벌어지기도 했기 때문이다. 하지만 집합론이 발달하기 위해선 무한집합을 제대로 이해할 필요가 있었고, 칸토어는 최초로 이를 해낸 사람인 것이다. 그 성과 중 하나가 '''무한의 크기는 다양하다'''이고 위에서 보인 것이 바로 그 사실이다. 자연수 집합이 무한집합이고 그 어떤 집합보다 커 보였지만 사실 더 큰 집합이 존재하고 사실 그 어떤 (무한)집합을 택해도 그 집합보다 더 큰 집합이 존재한다는 것을 밝힌 것이다.
이런 놀라운 결과는 수학계에서 바로 받아들여지지 못했다. 칸토어의 말년이 불우했던 까닭도 여기서 찾을 수 있다. 하지만 집합의 성질들이 수학의 영역에서 갈 수록 중요해지면서[9] 후대 수학자들은 칸토어의 집합론을 받아들이기 시작했고 더더욱 발전시켰다.
한편 우리는 임의의 집합 $$A$$에 대해 $$|A| < 2^{|A|}$$임을 봤었다. 사실 모든 무한집합은 자연수와 크기가 같은 부분집합을 포함한다. 이는 자연수 집합이 무한집합들 중에서 제일 작은 집합이라는 것을 의미한다. 수학자들은 자연수 집합의 크기를 흔히 $$\aleph_0$$로 표기한다.[10] 한편, 우리가 아는 상당 수의 집합들이 사실은 (안 그래 보여도) 자연수 집합과 크기가 같다는 것을 설명했었고, 그러면서도 실수 집합은 그 크기가 $$2^{\aleph_0}$$임을 알았다. 그리고 흔히 $$c = 2^{\aleph_0}$$로 표현한다. 사실 자연수를 포함하거나 혹은 우리가 잘 아는 수 체계로부터 출발하여 얻어진 집합들 중에 $$\aleph_0$$ 혹은 $$c$$가 아녔던 것은 거의 없었다. 있다 해도 $$2^{c}$$라든가 혹은 이것의 또다른 지수 같은 것이었을 뿐이었다.
여기서 한 가지 질문을 할 수 있다. 그러면 '''$$\aleph_0 < |X| < c$$를 만족하는 집합 $$X$$가 존재하는가?''' 해봄직한 질문이긴 한데 문제는 어느 누구도 저런 집합을 찾지 못 하였고 그러면서도 저런 집합이 없다고 밝힌 사람은 또 없었다는 것이다. 왠지 있을 것 같은데 전혀 안 보이고 그렇다고 없다고 말할 수도 없으니 사람들은 아리송할 수 밖에. 저런 집합이 존재하지 않을 거라고 가정하는 것을 가리켜 '''연속체 가설(Continuum Hypothesis)'''라고 부른다. 그리고 잘 알려져 있다시피 연속체 가설이 맞느냐 틀리느냐를 밝히라는 게 바로 '''힐베르트의 23가지 문제 중 첫번째 문제'''였다.
결론부터 말하자면 '''이 문제는 풀렸는데''' 그 답이 또 골 때린다. '''맞다고 가정해도 문제 없고 틀렸다고 가정해도 문제 없다'''가 답이다. 즉, 저 가설의 참과 거짓 어느 것을 주장해도 수학을 모순 없이 잘 전개할 수 있다는 것이다.
4. 관련 문서
[1] 특히 $$B$$가 수 집합이면 일대일 함수라고도 불린다.[2] 실제로는 주어진 집합이 자연수 집합보다 작거나 같다는 것을 보이는 것으로 증명을 완료하는 경우가 많다. 즉, 일대일 대응은 아니더라도 '크거나 같다'와 '작거나 같다' 둘 다를 보여 결국 크기가 같다고 주장하는 식이다. 하지만 집합 A가 B보다 크거나 같고 B가 A보다 크거나 같다면 당연히 두 집합의 크기가 동일해야 할 것 같지만 이 또한 증명되어야 한다. 이는 선택공리를 가정했을 때 '칸토어-베른슈타인 정리'라는 이름으로 증명이 되었다.[3] 자기 자신과 일대일 대응이 되는 진부분집합을 갖는 집합이라고 정의되기도 한다. 그런데 이 두 정의는 사실 똑같다는 것을 증명할 수 있다.[4] 사실 칸토어는 대각선 논법 이전에 이미 자연수 집합과 실수 집합 간에 일대일 대응은 있을 수 없다는 것을 다른 방식으로 보였다. 이 방법은 실수의 근본적인 성질에 기초한 것이라 더 어려워 보이지만 그만큼 더 확실해 보인다. 반면 대각선 논법에서 쓰인 실수의 소수 표현은 모호하다는 느낌을 받을 수 있다. 칸토어가 최초로 실수가 비가산임을 증명하는 방법은 실수의 위상적 성질중 하나인 축소구간정리를 이용한 것이다.[5] $$\chi : \mathcal{P}\left(A\right) \to Q$$를 $$\chi\left(A\right)\left(x\right):=\begin{cases}1 & \phantom{\cdots}x\in A\\0 & \phantom{\cdots}x\notin A\end{cases}$$, $$\overline{\chi} : Q \to \mathcal{P}\left(A\right)$$를 $$\overline{\chi}\left(f\right) = \left\{x \in A \;|\; f\left(x\right) = 1\right\}$$로 정의하자. 그러면 (일단 $$\chi$$가 올바른 사상인지부터 보인 다음) $$\chi \circ \overline{\chi}$$와 $$\overline{\chi} \circ \chi$$ 둘 다 항등 사상임을 금방 알 수 있다. 따라서 두 사상 $$\overline{\chi}$$, $$\chi$$는 서로 역사상 관계이며 이로부터 $$\overline{\chi}$$, $$\chi$$가 일대일 대응임을 알 수 있다. [6] 여기선 이해를 돕기 위해 '크기'라고 썼지만 실제로는 농도(cardinality)라고 흔히 표현한다.[7] 책에 따라서는 $$\text{card}\left(X\right)$$, $$\text{card}\left(Y\right)$$로 표기하기도 한다.[8] 즉 S의 원소 <M>은, M에 <M>을 입력값으로 넣으면 영원히 안 멈추거나 no를 뱉는다.[9] 현대 수학의 대부분은 어떤 특정한 성질을 만족하는 집합들과 그 성질을 보존하는 사상(함수)의 성질들을 연구하는 데에 집중되어 있다. 예컨대 대수학의 경우 대수적인 구조를 가진 집합들(군, 환, 체, 모듈, 벡터 공간, 대수 등)의 성질과 연산을 보존하는 사상인 Homomorphism을 연구한다. 또한 위상수학에서는 어떤 특정한 성질을 만족하는 부분집합들을 모아놓고 열린 집합(Open Set)으로 부르며 이들의 성질을 다루고 있으며 특히 연속 사상(Continuous Map)에 의해 어떤 성질들이 보존되는가를 연구한다.[10] 저 희한한 문자는 '알레프'라고 부르며 히브리 문자 중 하나이다. 즉, 자연수 집합의 크기는 '알레프 제로'라고 읽는다.