현대 수학에서는 보통 두 집합이 서로 크기가 같다는 것은 두 집합 사이에 일대일 대응 함수가 존재한다는 것을 의미한다.
이는 유한 집합과 유한 집합 사이에서도 적용되는 말임은 물론, 무한 집합과 무한 집합 사이에서도 크기를 비교할 수 있게 해 준 새로운 접근법이었다.
하지만, 모든 무한 집합 사이에 일대일 대응 함수가 존재한다면 무슨 의미가 있을 것인가?
여기에, 무한 집합이라도 크기가 다를 수 있다는 예시를 하나 말하고 증명하고자 한다. 수학에서는 매우 고전적인 예시이다.
claim : 실수 집합과 자연수 집합 사이에는 일대일 대응 함수가 존재하지 않는다.
칸토어의 대각선 논법을 소개한다.
pf) 실수 집합을 R, 양의 정수 집합을 N이라고 하자.
R과 N의 크기가 같다고 가정하자. 그러면, N에서 R로 가는 일대일 대응 함수 f 가 존재한다.
이때, f 는 일대일 대응 함수이므로, 임의의 실수 x에 대해, f(n_x)=x인 양의 정수 n_x가 존재해야 한다.
따라서 만약에 모든 자연수 n에 대해, f(n)≠x인 실수 x를 찾을 수 있다면, 모순이 발생하는 것이다.
이러한 실수 x를 찾아보겠다.
f(1), f(2), f(3), .... , f(n), ... 으로 이루어진 수열이 있을 것이다.
여기서 새로운 수열 a_n을 다음과 같이 정의하자.
a_n={ 1 ( f(n)의 소수점 아래 n번째 자리 수가 0인 경우.)
{ 0 ( f(n)의 소수점 아래 n번째 자리 수가 0이 아닌 경우.)
그리고 x=(n=1에서 무한)∑a_n/10^n
그러면, 모든 자연수 n에 대해, x의 소수점 아래 n번째 자리 수는 a_n인 것이다.
그런데, 모든 자연수 n에 대해, f(n)의 소수점 아래 n번째 자리 수는 a_n과 다르다. (a_n의 정의 참조.) 즉, f(n)과 x의 소수점 아래 n번째 자리 수가 다르다는 것이고, x와 f(n)은 서로 다른 실수이다.
이는 함수 f 의 치역과 공역이 같다는 조건에 위배된다. 즉, 모순이다.
따라서, 자연수에서 실수로 가는 일대일 대응 함수는 존재해선 안 된다.
마찬가지로, 임의의 일대일 대응 함수에는 역함수가 존재하며 그 역함수도 일대일 대응 함수이므로 실수에서 자연수에서 가는 일대일 대응 함수도 존재해선 안 된다.
Q.E.D.
