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

그림에서 무엇을 볼까요?

집합 L의 원소별 0과 1 배정, 값이 1인 원소로 만든 부분집합, 대각선 반전 함수 g의 관계를 세 단계로 보여 주는 도해

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

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