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

한 줄 정의: 모든 항목을 나열해도 빠지는 원소를 만들어 비가산성을 보이는 증명법입니다.

쉽게 풀면

0과 1 사이의 실수를 전부 목록으로 만들었다고 가정해 봅시다. 첫 번째 수의 첫째 자리, 두 번째 수의 둘째 자리를 따라 대각선으로 읽으면서 각 숫자를 다른 숫자로 바꾸면, 목록의 어떤 수와도 최소 한 자리가 다른 새 수가 만들어집니다. 목록에 없는 수가 나왔으므로 애초의 가정이 틀렸다는 결론이 나옵니다.

왜 중요한가

무한에도 등급이 있음을 처음으로 엄밀히 보인 논증으로 집합론의 출발점이 되었습니다. 나아가 같은 자기참조 구조가 괴델의 불완전성 정리와 튜링의 정지문제 증명에 그대로 재사용되어, 논리학과 계산이론의 핵심 기법이 되었습니다.

논문에서는 이렇게 쓰입니다

"대각선 논법을 적용하여 해당 집합이 어떤 열거로도 소진되지 않음을 보였다."

조금 더 깊게 보면

논법의 핵심은 나열을 가정한 뒤 그 나열 자체를 이용해 나열에 없는 대상을 구성하는 자기참조에 있습니다. 같은 방식으로 임의의 집합보다 그 멱집합의 기수가 더 크다는 칸토어 정리가 증명되며, 이는 무한 기수의 계열이 끝없이 이어짐을 함의합니다. 계산이론에서는 프로그램의 목록에 대해 같은 조작을 가해 어떤 프로그램도 계산할 수 없는 함수를 구성합니다.

주의할 점

논법이 보여 주는 것은 어떤 특정 나열이 실패한다는 것이 아니라 모든 나열이 실패한다는 점입니다. 또 이 논증은 귀류법의 형태를 취하지만, 핵심은 반례를 실제로 구성하는 데 있습니다.