칸토어의 대각선 논증은 무엇을 증명하나요?

0과 1 사이의 실수는 비가산임을 증명합니다. 아무리 영리하게 구성된 목록이라도 그 구간의 모든 실수를 담을 수는 없습니다. 단순히 목록의 어느 자리보다 실수가 더 많습니다.

비가산이란 무엇인가요?

집합의 원소 각각을 자연수(1, 2, 3, ...)와 하나씩 대응시킬 수 있고 빠지는 것이 없다면 그 집합은 가산입니다. 자연수, 정수, 심지어 유리수도 모두 가산입니다. 실수는 그렇지 않습니다. 어떤 일대일 대응도 불가능할 만큼 실수가 더 많습니다.

빠진 수를 목록에 추가하면 안 되나요?

추가할 수는 있습니다. 하지만 그러면 새롭고 더 긴 목록에 대각선 논증이 다시 적용되어 또 다른 빠진 수를 만들어 냅니다. 논증은 아무리 길고 영리하게 배열된 목록에도 작동하므로, 목록을 완전하게 만들 방법은 없습니다.

뒤집을 때 왜 0과 9를 피하나요?

일부 실수는 두 가지 소수 표현을 가집니다. 0.4999...와 0.5000...은 같은 수입니다. 숫자를 0이나 9로 뒤집으면 이미 목록에 있는 수의 다른 이름을 실수로 만들 수 있습니다. 0과 9를 피하면 이 기술적 문제를 우회하고 증명을 깔끔하게 유지할 수 있습니다.

유리수도 비가산인가요?

아닙니다. 유리수는 가산입니다. 모든 분수 p/q를 체계적으로 나열하고 각각에 자연수 인덱스를 부여할 수 있으며, 빠지는 것이 없습니다. 칸토어의 대각선 논증은 실수를 대상으로 하지, 유리수를 대상으로 하지 않습니다.

칸토어의 대각선 논증: 실수를 목록으로 나열할 수 없는 이유

누군가 목록을 하나 건넨다고 상상해 보세요. 무한한 목록이고, 0과 1 사이의 모든 실수를 담고 있다고 주장합니다. 샘플도 아니고 일부 선택도 아닙니다. r1, r2, r3, 이런 식으로 깔끔하게 인덱스가 붙은, 영원히 이어지는 목록에 모든 실수가 하나씩 담겨 있다는 것입니다.

1891년 게오르크 칸토어의 반응은 이러했습니다: 어떤 목록을 건네든, 그 목록에 없는 수를 하나 읽어 드리겠습니다. 설명하는 데 30초쯤 걸리는 구성이었습니다. 그 결과는 수학자들이 수십 년에 걸쳐 소화해야 했습니다. 무한이 하나 이상의 크기로 존재한다는 것을 의미하기 때문입니다.

세기와 나열하기

대각선 이동 전에, '가산'이 무엇을 의미하는지 정확히 짚어 두면 좋습니다. 집합이 가산이라는 것은 원소 각각에 고유한 자연수 레이블, 즉 첫 번째, 두 번째, 세 번째 등을 부여할 수 있고 남는 것이 없다는 뜻입니다. 자연수 자체는 정의상 가산입니다. 정수도 마찬가지이고(0, 1, -1, 2, -2, ... 순서로 나열), 유리수도 나열하려면 영리한 지그재그 패턴이 필요하지만 가산입니다.

칸토어의 논증은 0과 1 사이의 실수가 진정으로 다르다는 것을 보여 줍니다. 아무리 시도해도 레이블링은 존재하지 않습니다. 이것은 상상력의 실패가 아닙니다. 그 작업이 불가능하다는 증명입니다.

목록이 존재한다고 가정하기

논증은 귀류법 증명입니다. 상대방이 원하는 모든 것을 허용하는 것에서 시작합니다. (0, 1) 안의 모든 실수를 담은 완전한 목록이 실제로 존재한다고 가정합니다. 각 수를 무한 소수 전개로 씁니다.

목록은 다음과 같이 시작할 수 있습니다:

r1 = 0.14159265...
r2 = 0.73205080...
r3 = 0.00000000...
r4 = 0.27182818...
r5 = 0.91415926...
...

각 항목은 영원히 이어집니다. 목록도 영원히 이어집니다. 그리고 가정에 따라, 0과 1 사이의 모든 실수가 어딘가에 등장합니다.

이제 대각선을 따라 읽으면 무슨 일이 생기는지 지켜보세요.

대각선 읽기

r1의 첫 번째 소수 자리, r2의 두 번째 소수 자리, r3의 세 번째 소수 자리, 이런 식으로 읽습니다. 위 예시에서 대각선 숫자들은 1, 3, 0, 2, 9, ... 입니다.

이제 새로운 수 d를 한 자리씩 만들어 갑니다. 규칙: 각 대각선 숫자에 대해 다른 숫자를 선택하되, 의도적으로 0과 9를 피합니다.

r₁	.	1	4	1	5	9
r₂	.	3	3	3	3	3
r₃	.	5	0	0	0	0
r₄	.	7	1	8	2	8
r₅	.	6	0	2	5	9
new	.	2	4	1	3	8	…

Each highlighted digit sits on the diagonal. The new number changes every one of them (1 3 0 2 9 becomes 2 4 1 3 8), so it cannot equal any row in the list.

대각선 숫자는 1, 3, 0, 2, 9입니다. 규칙을 적용하면 2, 4, 1, 3, 8이 나옵니다. 따라서 d = 0.24138...

0과 9를 피하는 것은 작지만 필요한 장치입니다. 일부 실수는 두 가지 소수 표현을 갖습니다. 0.4999...와 0.5000...은 수직선의 같은 점을 가리킵니다. 숫자를 0이나 9로 뒤집으면 이미 목록에 있는 수의 '다른 이름'으로 끝날 수 있고, 그러면 논증이 흐려집니다. 뒤집힌 모든 숫자를 1부터 8 범위 안에 유지함으로써, d가 정확히 하나의 소수 전개를 가짐을 보장하고 아래 비교가 깔끔해집니다.

새 수는 모든 항목과 다르다

이제 핵심입니다.

d는 첫 번째 소수 자리에서 r1과 다르다

d의 첫 번째 자리는 r1의 첫 번째 자리와 다르도록 선택되었습니다. 따라서 d는 r1과 같지 않습니다. 위치 1에서 다릅니다.

d는 두 번째 소수 자리에서 r2와 다르다

d의 두 번째 자리는 r2의 두 번째 자리와 다르도록 선택되었습니다. 따라서 d는 r2와 같지 않습니다. 위치 2에서 다릅니다.

d는 모든 n에 대해 n번째 소수 자리에서 rn과 다르다

구성에 의해, d의 n번째 자리는 rn의 n번째 자리와 다릅니다. 어떤 위치에서든 다른 숫자를 가지는 두 수는 같지 않으므로, d는 어떤 n을 지정하더라도 rn과 같지 않습니다.

이것이 대각선 이동입니다. d는 목록의 모든 항목과, 각 항목이 가장 노출된 단 하나의 지점, 즉 자신의 대각선 위치에서 충돌하도록 설계되었습니다.

d는 0과 1 사이의 실수이지만 목록에 없다

d = 0.24138...은 명백히 (0, 1) 구간의 실수입니다. 하지만 방금 d가 r1과도, r2와도, r3와도, 모든 항목과도 다르다는 것을 보였습니다. 목록이 완전하다면 d는 어딘가에 나타나야 합니다. 나타나지 않습니다. 따라서 목록은 완전하지 않습니다.

모순이 명확합니다. 목록이 완전하다고 가정했는데, 목록에 없는 실수를 만들어 냈습니다. 가정은 거짓이어야 합니다. 0과 1 사이의 실수에 대한 완전한 목록은 존재할 수 없습니다.

이것이 실제로 말하는 것

수학자들은 자연수의 농도를 알레프-눌(히브리 문자 알레프로 쓰인 첫 번째 초한 기수)이라고 합니다. 실수의 농도는 엄격하게 더 크며, 때로 c 또는 알레프-눌의 2제곱으로 씁니다. 칸토어의 논증은 이 두 무한이 같은 크기가 아님을 확립하는 것입니다.

칸토어가 이것을 발표했을 때 깊은 논란이 있었습니다. 일부 동료들은 이 결과를 호기심 어린 것 또는 오류로 무시했습니다. 어느 쪽도 아닙니다. 수학자들이 집합, 농도, 실수직선의 구조를 생각하는 방식의 토대에 자리하고 있으며, 무엇이 계산 가능하고 무엇이 그렇지 않은지에 관한 질문과 직결됩니다(형식 체계의 한계에 부딪히는 증명 가능하게 참인 것의 또 다른 사례로 굿스타인 정리도 참고하세요).

왜 대각선이 작동하는가

논증이 우아한 이유는 구체성 때문입니다. 빠진 수를 추측하거나 실수가 얼마나 큰지에 대한 막연한 직관에 의존하지 않습니다. 목록의 각 항목이 어떤 위치를 장악하는지 정확히 읽어 내고, 그 위치 각각에서 모든 항목을 피하는 수를 만듭니다.

목록 자체가 어디를 봐야 할지 알려 줍니다. 목록의 모든 항목이 하나의 좌표, 즉 자신의 대각선 숫자를 건네주고, 그 구성은 그 좌표들을 목록이 담을 수 없는 수로 만듭니다.

단순함은 기만적입니다. 목록의 항목에 대해 아무것도 알 필요가 없습니다. 어떤 수가 있는지, 어떤 순서인지, 어떻게 선택되었는지는 중요하지 않습니다. 논증은 보편적입니다. 어떤 실수 목록을 선택하든, 대각선 구성은 그 목록에 없는 실수를 만들어 냅니다.

그 속의 선(禪)

칸토어의 대각선 논증은 작동해서는 안 될 것 같은 수학적 결과들의 긴 전통 안에 자리합니다. 증명을 들여다보며 트릭을, 숨겨진 가정을, 논리가 미끄러지는 지점을 기다립니다. 그것은 없습니다. 증명은 겉으로 보이는 것만큼 단순합니다.

증명 자체보다 더 낯선 것을 받아들이라고 요구합니다. '무한'이 단 하나의 목적지가 아니라는 것입니다. 정수와 실수 모두 무한이지만, 범주적으로 다른 방식으로 무한합니다. 대각선 논증이 그 경계선입니다.

무한한 컬렉션이 얼마나 이상하게 행동할 수 있는지 더 깊이 느끼고 싶다면, 무한 소수의 구조를 다음에 살펴보거나, 수열이 값에 영원히 접근하면서도 도달하지 않을 때 극한이 어떻게 작동하는지를 살펴보면 좋습니다. 대각선 논증은 같은 가족에 속합니다. 무한의 가장자리에서, 직관이 정직함을 유지하기 위해 증명이 필요한 곳에서, 정밀하고 인내심 있는 시선입니다.

무한은 하나가 아닙니다. 그것이 소식입니다. 그것을 전달하는 논증은 반쪽 페이지에 들어맞습니다.