칸토어의 대각선
무한 속에서 새 무한 낚아채기
0과 1 사이의 모든 소수들을 빠짐없이 순서대로 한 줄씩 적은 거대한 표가 있다고 상상해 보세요. 첫째 줄, 둘째 줄, 셋째 줄… 모든 실수가 완벽하게 적혀 있습니다.
이제 표의 대각선을 타고 내려가며 첫째 줄 첫째 자리와 다른 숫자, 둘째 줄 둘째 자리와 다른 숫자를 골라 새 소수를 적어 보세요. 방금 만든 이 숫자는 왜 표의 그 어떤 줄과도 절대로 같을 수 없을까요?
이야기
Unknown authorUnknown author
Public domain · 위키미디어 공용
1891년, 게오르크 칸토어가 이 논법을 발표합니다. 그의 스승이었던 베를린의 크로네커는 그를 「젊은이를 망치는 자」라 불렀고 논문이 실리는 것을 막았습니다. 무한을 크기가 다른 것들로 나누는 일이 그때는 신성모독처럼 받아들여졌습니다.
그런데 정작 오늘 이 대각선은 수학의 뼈대가 되었습니다. 사십 년 뒤 괴델이 「증명할 수 없는 참인 명제가 있다」를 보일 때, 튜링이 「멈출지 알아내는 기계는 없다」를 보일 때 — 둘 다 이 대각선을 그대로 빌려 썼습니다.
왜 새 수가 목록에 없을 수밖에 없을까요. 그 수는 첫째 줄과 첫째 자리에서 다르게, 둘째 줄과 둘째 자리에서 다르게 만든 것입니다.
그러니 목록의 n번째 줄과는 n번째 자리에서 반드시 다릅니다. 한 자리라도 다르면 다른 수이기 때문에, 이 수는 어느 줄과도 같을 수 없습니다. 어떤 목록을 가져와도 마찬가지라서, 줄 세우기 자체가 불가능합니다.
「할 수 없는 일」을 증명하는 무기가 되었습니다. 괴델과 튜링이 이 대각선 논법을 그대로 빌려 썼습니다.
그 결과가 「모든 오류를 잡는 프로그램은 없다」이고, 그것이 지금 소프트웨어를 만드는 사람들의 현실입니다.
계단 넷 — 같은 사실을 네 깊이로
목록에 없는 숫자를 만들어 본다
친구들이 적어 낸 세 자리 숫자 목록을 봅니다. 1등 친구의 첫째 자리와 다르고, 2등 친구의 둘째 자리와 다르고, 3등 친구의 셋째 자리와 다른 숫자를 새로 만듭니다.
이 새로운 숫자는 1등과도, 2등과도, 3등과도 무조건 다릅니다. 목록이 아무리 길어도 그 안에 쏙 빠진 새로운 숫자를 언제나 만들어 낼 수 있습니다.
목록에 없는 수를 만들어 보세요
그 수는 어느 줄과도 다릅니다 — 목록에 없습니다.
⭐ 0 과 1 만 써도 목록에 없는 수를 만들 수 있습니다.
줄 세울 수 있는 무한과 없는 무한
자연수는 1, 2, 3… 하나씩 셀 수 있는 무한(가산무한)입니다. 짝수나 분수(유리수)도 지그재그로 줄을 세우면 자연수와 일대일로 짝을 맞출 수 있습니다.
하지만 0과 1 사이의 실수를 모두 줄 세웠다고 가정하면 대각선 논법에 의해 목록에 없는 새로운 실수가 즉시 탄생합니다. 목록이 전부라는 가정이 깨지므로 실수는 자연수보다 훨씬 거대한 무한입니다.
셀 수 있는 것들
대각선으로 훑으면 하나도 빠뜨리지 않습니다.
대각선으로 새 수 만들기
칸토어의 대각선 논법은 실수의 집합 이 비가산 집합(Uncountable Set)임을 증명합니다. 자연수의 기수를 (알레프 0), 실수의 기수를 (연속체 기수)라 할 때 입니다.
칸토어의 정리는 임의의 집합 에 대해 그 멱집합 의 기수가 항상 원래 집합보다 진대수적으로 큼()을 보여 주어 무한의 위계가 끝없이 이어짐을 입증했습니다.
부분집합은 더 많습니다
칸토어는 이것이 무한에서도 성립함을 보였습니다 — 그래서 무한이 층층입니다.
연속체 가설
이 대각선 구성법은 수리논리학의 괴델 불완전성 정리와 컴퓨터 과학의 튜링 정지 문제(Halting Problem) 증명의 모태가 되었습니다.
또한 가산무한과 연속체 기수 사이에 다른 무한이 존재하는가에 대한 연속체 가설(CH)은 괴델과 코언에 의해 ZFC 공리계에서 증명도 반증도 할 수 없는 독립적 명제임이 밝혀져 현대 집합론의 지평을 넓혔습니다.
무한의 층
그 사이에 다른 무한이 있는지(연속체 가설)는 참도 거짓도 증명할 수 없습니다.
풀어 보기
칸토어 대각선 논법과 무한. 다음 물음에 답하시오.
(1) 세 실수 에 대해 각 자리수 을 번째 실수의 번째 소수 자리 숫자와 다르게 골라 과 모두 다른 새로운 실수의 첫 세 자리를 예시로 하나 만드시오.
(2) 자연수 집합, 정수 집합, 유리수 집합, 실수 집합 중 기수(크기)가 다른 하나를 고르시오.
(3) 임의의 집합 와 그 부분집합 전체의 집합인 멱집합 사이의 기수 대소 관계를 부등호로 나타내시오.
(1) 1번째!=1, 2번째!=5, 3번째!=9로 골라 예를 들어 등입니다. (2) 실수 집합입니다. (3) 입니다.
답과 풀이 보기
(1) 보기를 들면 입니다.
· 첫째 자리 — 의 첫째 자리가 1 이므로 1 이 아닌 2 를 고릅니다
· 둘째 자리 — 의 둘째 자리가 5 이므로 5 가 아닌 6 을 고릅니다
· 셋째 자리 — 의 셋째 자리가 9 이므로 9 가 아닌 1 을 고릅니다
이렇게 만든 수는 과는 첫째 자리에서, 와는 둘째 자리에서, 과는 셋째 자리에서 다릅니다.
⭐ 목록에 있는 모든 수와 적어도 한 자리는 다릅니다. 그래서 목록에 없습니다.
(2) 실수 집합입니다.
자연수 · 정수 · 유리수는 모두 크기가 같습니다 () — 번호를 매겨 줄 세울 수 있습니다.
⭐ 유리수도 분자와 분모를 격자로 놓고 대각선으로 훑으면 줄 세워집니다.
그런데 실수는 어떻게 줄을 세워도 (1) 의 방법으로 빠진 수가 나옵니다. 그래서 더 큰 무한입니다.
(3) 입니다 (칸토어 정리).
· 유한하면 이라 당연합니다
· 무한이어도 마찬가지입니다 — 이것이 놀라운 점입니다
⇨ 그러므로 — 가장 큰 무한이란 없습니다. 무한 위에 무한이 끝없이 쌓입니다.
1874 년 칸토어가 이것을 내놓았을 때, 스승 크로네커는 그를 「젊은이를 타락시키는 자」라 부르며 논문을 막았습니다.
칸토어는 우울증으로 여러 번 병원에 들어갔고 정신병원에서 세상을 떠났습니다.
힐베르트는 뒷날 이렇게 말했습니다 — 「누구도 칸토어가 만든 낙원에서 우리를 쫓아낼 수 없다.」
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
이 한 번의 대각선이 수학의 지도를 다시 그렸습니다.
- 가산·비가산 — 줄 세울 수 있는 무한과 없는 무한
- 연속체 가설 — 그 둘 사이에 다른 무한이 있는가? 「있다고 해도 없다고 해도 모순이 없다」가 답이었습니다
- 대각선 논법 — 괴델과 튜링이 그대로 빌려 씁니다
이어지는 장
자연수와 유리수는 무한 호텔의 방에 하나씩 모두 배정할 수 있지만 실수는 호텔 전체를 채우고도 넘쳐납니다 — 제125장 의 무한을 딛고 무한 너머에 더 거대한 무한이 있음을 확인해 보세요.
이어지는 자료
영감을 받은 곳
게오르크 칸토어(Georg Cantor)가 1891년 독일수학회보에 발표한 논문 「집합론의 한 기초적 물음에 관하여」에서 대각선 논법을 통해 실수의 비가산성을 증명했습니다.