대각선 논법
대각선 논법 (Diagonal Argument)은 게오르크 칸토어가 1891년에 발표한 증명 방법으로, 무한 집합의 크기를 비교하는 데 사용된다. 특히 실수의 집합이 자연수의 집합보다 더 '크다'는 것을 증명하는 데 중요한 역할을 한다. 여기서 '크다'는 개념은 단순히 원소의 개수를 세는 것이 아니라, 두 집합 사이에 일대일 대응이 존재하는지 여부로 정의된다.
핵심 아이디어
대각선 논법의 핵심 아이디어는 다음과 같다. 어떤 집합 S의 모든 원소와 자연수 사이에 일대일 대응이 존재한다고 가정했을 때, 반드시 이 대응에서 빠지는 S의 원소가 존재함을 보여 모순을 이끌어내는 것이다. 이를 위해, 가정된 일대일 대응을 표로 나타내고, 표의 대각선에 위치한 원소들을 변형하여 새로운 원소를 구성한다. 이 새로운 원소는 표의 어떤 행과도 일치하지 않으므로, 처음 가정이 잘못되었음을 증명하게 된다.
증명 방법 (실수 집합의 비가산성)
대각선 논법은 실수의 집합이 자연수의 집합보다 크다는 것을 증명하는 데 자주 사용된다. 이를 증명하는 과정은 다음과 같다.
-
가정: 0과 1 사이의 모든 실수가 자연수와 일대일 대응된다고 가정한다. 즉, 모든 실수를 다음과 같이 나열할 수 있다고 가정한다.
1 -> 0.a11 a12 a13 a14 ... 2 -> 0.a21 a22 a23 a24 ... 3 -> 0.a31 a32 a33 a34 ... 4 -> 0.a41 a42 a43 a44 ... ...여기서 aij는 0부터 9까지의 숫자이다.
-
새로운 실수 구성: 위 표에서 대각선에 위치한 숫자들을 이용하여 새로운 실수 x를 다음과 같이 정의한다.
x = 0.b1 b2 b3 b4 ...여기서 bi는 다음과 같이 결정된다.
- ai i = 5 라면 bi = 6
- ai i ≠ 5 라면 bi = 5
예를 들어, a11 = 3, a22 = 5, a33 = 7, a44 = 1이라면, x = 0.5655... 가 된다.
-
모순 유도: 이렇게 구성된 실수 x는 위 표의 어떤 실수와도 일치할 수 없다. 왜냐하면, x의 첫 번째 자리 숫자는 첫 번째 실수와 다르고, x의 두 번째 자리 숫자는 두 번째 실수와 다르며, 일반적으로 x의 n번째 자리 숫자는 n번째 실수와 다르기 때문이다. 따라서, x는 위 표에 나열된 어떤 실수와도 같지 않으므로, x는 위 표에 빠져있는 새로운 실수이다.
-
결론: 따라서, 0과 1 사이의 모든 실수를 자연수와 일대일 대응시킬 수 있다는 가정이 틀렸음을 알 수 있다. 즉, 실수의 집합은 자연수의 집합보다 더 '크다' (비가산 집합이다).
중요성 및 활용
대각선 논법은 무한 집합론의 기초를 다지는 데 중요한 역할을 했으며, 집합론뿐만 아니라 계산 이론, 논리학 등 다양한 분야에 영향을 미쳤다. 특히, 튜링 기계의 정지 문제와 같은 문제의 해결에 활용되기도 한다.