컴퓨터과학이 여는 세계_3.3 멈춤문제를 푸는 튜링기계는 없다_이광근

강좌 동영상

무한의 세계에도 크기 차이가 있다.

 예를들어 자연수의 갯수인 무한보다 자연수의 부분집합의 갯수가 더 많다. 또, 정수의 갯수인 무한보다, 실수의 갯수인 무한개보다 작다. 이를 칸토르(Georg Cantor)라는 수학자가 대각선 논법을 이용해 증명하였다.

먼저 자연수가 모든 자연수의 부분집합과 하나씩 대응할 수 있다고 가정한다.

 그 후 표를 만드는데, 맨 윗줄에 자연수를 쭉 쓴다. 그후 왼쪽에는 자연수의 부분집합이 될 집합들을 쭉 쓴다. 각각의 부분집합 옆에는 부분집합안에 해당 자연수가 들어가면 'O' 아니면 'X'를 쓴다.

 예를들어 위에 표에서, S1 = {2, 5, 6, ... }, S2 = {1, 2, 5, ... }, S3 = {1, 3, 4, 6, ... } .... 인셈이다.

 이제 새로운 부분집합 Z를 만드는데 이 Z의 원소는 Sn이 n을 가지면 n을 가지지 않고, Sn이 n을 가지지 않으면 Sn을 가진다. (n = 1, 2, 3 , ... )

 이 부분집합Z는 다른 모든 부분집합Sn (n = 1, 2, 3 , ... )과 다른 원소를 가진다. 따라서 가정에 모순이 생기는 새로운 자연수의 부분집합이 더 만들어지므로, 자연수의 부분집합의 갯수는 자연수 갯수보다 크다.

 이로 무한도 다같은 무한이 아니라 무한의 크기가 존재함을 알 수 있다.