목록의 대각선을 뒤집으면 왜 반드시 새 항목이 생길까?

칸토어는 왜 이미 얻은 결론에 새 증명을 붙였을까?

칸토어는 1874년에 실수 전체를 자연수와 일대일로 대응시킬 수 없다는 결론을 먼저 발표했다. 그때의 증명은 구간의 완전성과 중첩 구간을 이용했다. 1891년 9월 할레에서 독일수학회 모임을 이끌며 그는 같은 비가산성 결론을 훨씬 짧은 방식으로 다시 제시했다.[3][4]

논문은 『독일수학회 연보』 제1권에 실렸는데 권호는 1890/91로 표시되고 실제 인쇄본은 1892년에 나왔다. 그래서 자료에 따라 1891년 논증, 1892년 논문이라고 적힌다. 여기서는 발표 시점에 맞춰 ‘1891년 대각선 논증’이라 부르되, 인쇄 연대의 차이도 숨기지 않는다.[1][2]

실수의 소수보다 먼저 m과 w의 무한 수열이 있었다

칸토어는 서로 다른 두 기호 m과 w를 정하고, 각 자리가 둘 중 하나인 무한 수열 E=(x₁,x₂,…,xᵥ,…)의 전체 M을 생각했다. 예를 들어 모두 m인 수열, 모두 w인 수열, m과 w가 번갈아 나오는 수열은 모두 M의 원소다.[1][2]

이 설정에는 0.4999…=0.5000… 같은 소수 표현의 중복 문제가 없다. 대상은 숫자의 표기가 아니라 두 기호의 좌표열 자체이기 때문이다. 현대식으로 m을 0, w를 1로 바꾸어도 논증의 구조는 같지만, 그것은 독자의 계산을 돕는 번역이지 원문 첫 표기의 복제는 아니다.[1][2]

n번째 행의 n번째 칸 하나가 n번째 행을 탈락시킨다

모든 수열을 E₁,E₂,E₃,…으로 적었다고 가정하자. 새 수열 E₀의 n번째 기호 bₙ을 Eₙ의 n번째 기호 aₙ,ₙ과 다르게 정한다. 대각선 칸이 m이면 bₙ을 w로, w이면 m으로 둔다.[1][2]

이제 E₀가 목록의 u번째 수열 Eᵤ와 같다고 해 보자. 두 수열이 같으려면 u번째 자리도 같아야 하지만, E₀의 u번째 기호 bᵤ는 정의상 Eᵤ의 u번째 기호 aᵤ,ᵤ와 다르다. 따라서 E₀는 E₁과 첫째 자리에서, E₂와 둘째 자리에서, 일반적으로 Eᵤ와 u번째 자리에서 다르다. 목록에 어떤 행이 오더라도 그 행을 탈락시키는 자리가 하나씩 예약되어 있는 셈이다.[1][2]

다섯 줄짜리 표만으로 무한 목록을 반박한 것은 아니다

다섯 자리 0·1 수열은 2⁵=32개다. 다섯 행만 적어 놓고 대각선을 뒤집으면 그 다섯 행과 다른 수열 하나를 쉽게 만들 수 있다. 이것은 5개 항목이 32개 수열을 모두 담을 수 없다는 유한한 계산이며, 대각선 규칙을 눈으로 확인하는 좋은 모형이다.

그러나 무한 목록의 첫 다섯 행과 첫 다섯 자리만 바꾸면 여섯째 이후의 어떤 행과 우연히 같을 수 있다. 칸토어의 결론은 ‘일부 대각선’이 아니라 모든 자연수 n에 대해 n번째 칸을 바꾼다는 하나의 무한 규칙에서 나온다. 각 행마다 다른 자리가 반드시 하나 존재한다는 전칭 주장이 증명을 완성한다.[1][2]

0·1 함수 하나는 부분집합 하나를 어떻게 기록할까?

논문의 뒤쪽에서 칸토어는 집합 L의 각 원소 x에 0 또는 1을 배정하는 모든 함수 f(x)의 모임을 생각했다. 현대적으로는 값이 1인 원소만 모으면 L의 부분집합 하나가 되고, 반대로 부분집합 하나를 고르면 그 안의 원소에는 1, 밖의 원소에는 0을 배정할 수 있다. 그래서 모든 0·1 함수의 모임은 멱집합 P(L)과 같은 정보를 담는다.[1][3][5]

L의 원소로 모든 함수를 빠짐없이 지목할 수 있다고 가정해 φ(x,z)로 배열하면, g(x)를 φ(x,x)와 반대 값으로 정할 수 있다. g는 허용된 0·1 함수이지만 어떤 z₀가 g를 지목한다고 하면 x=z₀에서 g(z₀)≠φ(z₀,z₀)가 되어 모순이다. 따라서 L에서 모든 0·1 함수로 가는 전사 함수는 없다.[1][3][5]

이 논증은 무엇을 증명하고 무엇은 말하지 않을까?

증명되는 핵심은 어떤 집합 L도 그 모든 부분집합 P(L)과 같은 크기일 수 없다는 것이다. L에서 P(L)로 가는 대응 후보를 무엇으로 내놓든 대각선 구성으로 빠진 부분집합 하나를 만든다. 따라서 멱집합을 거듭 취하면 언제나 더 큰 크기가 생기며 ‘가장 큰 집합 크기’를 마지막 항목으로 세울 수 없다.[3][5]

반면 이 논증이 모든 무한 집합의 크기가 서로 다르다고 말하는 것은 아니다. 자연수와 짝수, 자연수와 유리수처럼 서로 일대일 대응되는 서로 다른 무한 집합도 있다. 또한 대각선 규칙은 목록의 모든 항을 실제로 하나씩 계산한 뒤 멈추는 알고리즘이 아니라, 목록이 완전하다고 가정할 때 각 행마다 다른 좌표를 동시에 지정하는 수학적 정의다.[3][4]

실수의 비가산성으로 옮길 때 이진 소수 전개를 쓰면 0.0111…=0.1000… 같은 중복 표현을 별도로 처리해야 한다. 그러나 원문의 두 기호 수열 논증과 0·1 함수 일반화는 그런 소수 표기 문제에 기대지 않는다. 표기상의 반론과 논증의 논리 구조를 분리해야 한다.[1][2]

‘목록에 없다’는 결론의 양화사를 직접 확인해 보자

답을 가리고 각 문제에서 ‘어느 행과 어느 자리에서 다른가’를 먼저 적어 보자. 대각선 논증은 수가 아주 많다는 직관보다 모든 행을 하나씩 배제하는 관계에 달려 있다.

기록 질문: 내가 ‘모두 적었다’고 주장하는 목록 하나를 정하고, 각 항목을 반드시 탈락시키는 검사 위치를 어떻게 배정할지 써 보자. 그 검사가 모든 항목에 적용된다는 것을 어떤 양화사로 표현할 수 있을까?