대각선 논법

3. 자연수 집합과 실수 집합의 크기 비교

게오르크 칸토어는 1873년에 리하르트 데데킨트에게 보낸 서신에서 처음으로 자연수 집합과 실수 집합의 크기(농도) 비교 문제를 제기했다.^[25] 칸토어는 1874년에 구간 축소법을 이용하여, 그리고 1891년에 대각선 논법을 이용하여 자연수 집합과 실수 집합 사이에 전단사 함수가 존재하지 않음을 증명하였다.^[25] 대각선 논법을 이용한 증명은 이전 증명보다 더 간단하고 오늘날 널리 알려져 있다.

칸토어의 증명에 따르면 자연수 집합과 (0,1) 구간 사이에는 전단사 함수가 존재하지 않으며, 이는 실수 집합이 비가산 집합이라는 명제와 동치이다.

실수의 비가산성은 칸토어의 첫 번째 비가산성 증명에 의해 이미 확립되었지만, 대각선 논법의 결과로부터도 유도될 수 있다. 이를 위해 무한 이진 문자열 집합 ''T''에서 실수 집합 '''R'''로의 단사 함수를 구성한다. ''T''가 비가산 집합이므로, 이 함수의 상은 '''R'''의 부분 집합이고 비가산 집합이다. 따라서 '''R'''은 비가산 집합이다. 또한, 칸토어가 고안한 구성 방법을 사용하여 ''T''와 '''R''' 사이의 전단사 함수를 구성할 수 있다. 따라서 ''T''와 '''R'''은 연속체 농도라고 불리는 동일한 기수를 가진다.

두 집합의 기수의 동등성은 두 집합 사이의 전단사 함수의 존재로 정의되며, 칸토어는 두 집합 간의 단사 함수의 존재를 통해 이진 술어를 정의한다. 자연수를 이진 시퀀스에 임베딩하여 다양한 "단사 함수 존재" 명제를 명시적으로 증명할 수 있으며, 이러한 의미에서 자연수 집합의 크기는 2의 자연수 집합 크기보다 작거나 같다. 그러나 대각선 논법에 따르면 전사 함수 및 전단사 함수는 존재하지 않는다. 즉, 자연수 집합은 가산 집합이 아니다. 이를 통해 자연수보다 무한한 1과 0의 시퀀스가 "더 많다"는 것을 알 수 있다.

칸토어의 결과는 모든 집합의 집합 개념이 모순됨을 의미한다. 만약 모든 집합의 집합이 존재한다면, 그 집합의 멱집합은 동시에 원래 집합보다 크면서 부분 집합이 되어야 하기 때문이다.

3. 1. 증명

다음으로, 수열 ''s''는 첫 번째 숫자를 ''s''_''1''의 첫 번째 숫자와 1의 보수로 선택하고 ('''0'''과 '''1'''을 바꿈), 두 번째 숫자를 ''s''_''2''의 두 번째 숫자와 1의 보수로 선택하고, 세 번째 숫자를 ''s''_''3''의 세 번째 숫자와 1의 보수로 선택하는 방식으로, 일반적으로 모든 ''n''에 대해 ''n''번째 숫자를 ''s''_''n''의 ''n''번째 숫자와 1의 보수로 선택하여 구성한다. 위의 예시에서, 이는 다음을 생성한다.

구성상 ''s''는 각 ''s''_''n''과 다른 ''T''의 구성원이며, 그 이유는 ''s''의 ''n''번째 숫자가 ''s''_''n''의 ''n''번째 숫자와 다르기 때문이다 (예시에서 강조 표시됨). 따라서 ''s''는 열거에 나타날 수 없다.

이 보조정리를 바탕으로 칸토어는 다음을 보여주기 위해 귀류법을 사용한다.

:집합 ''T''는 가산 집합이 아니다.

증명은 ''T''가 가산이라고 가정하는 것으로 시작한다. 그러면 ''T''의 모든 원소는 ''s''₁, ''s''₂, ... , ''s''_''n'', ... 와 같이 열거할 수 있다. 이전 보조정리를 이 열거에 적용하면 ''T''의 원소이지만 열거에는 없는 수열 ''s''가 생성된다. 그러나 ''T''가 열거된다면, ''s''를 포함한 ''T''의 모든 원소가 열거에 있어야 한다. 이는 모순이므로 원래 가정이 거짓임을 의미한다. 따라서 ''T''는 가산 집합이 아니다.^[2]

자연수 전체 집합 $\backslash mathbb\{N\}$에서 [0, 1] 구간(0 이상 1 이하의 실수 전체 집합)으로의 전단사가 존재하지 않음은 다음과 같이 증명할 수 있다. 한편, [0, 1] 구간과 실수 전체 집합 $\backslash mathbb\{R\}$은 농도가 같으므로, 이 사실은 $\backslash mathbb\{N\}$에서 $\backslash mathbb\{R\}$로의 전단사가 존재하지 않음을 의미한다.

만약 $\backslash mathbb\{N\}$에서 [0, 1] 구간으로의 전단사 φ가 존재한다고 가정하고, φ(i)를 a_i로 표기하자. 그러면 [0, 1] 구간의 각 원소를 $a\_\{1\},\; a\_\{2\},\; \backslash cdots$로 번호 매길 수 있다.

a_i를 이진법 전개했을 때의 $j$번째 자릿수를 a_i,j로 하고^[23], b_i를 ￢a_i,i로 하자.

그리고 b를 소수점 전개가 0.b₁b₂…가 되는 실수로 정의하자. 이 때, b는 $a\_\{1\},\; a\_\{2\},\; \backslash cdots$의 어느 것과도 다르다. 실제로 i를 임의로 선택했을 때, a_i의 i번째 자릿수는 a_i,i인 반면, b의 i번째 자릿수는 ￢a_i,i이므로, a_i와 b는 다르다.

가정에 의해 [0, 1] 구간의 모든 원소는 $a\_\{1\},\; a\_\{2\},\; \backslash cdots$로 번호가 매겨져 있어야 하는데, [0, 1] 구간의 원소인 b는 $a\_\{1\},\; a\_\{2\},\; \backslash cdots$의 어느 것과도 다르므로 모순이다. 따라서 $\backslash mathbb\{N\}$에서 [0, 1] 구간으로의 전단사는 존재하지 않는다.

3. 2. 다른 방법의 증명

• 갑과 을은 번갈아 가며 실수를 취한다.
• 우선 갑이 $x\_0=0$을 취하고, 그 뒤 을이 $y\_0=1$을 취한다.
• $x\_\{n-1\},y\_\{n-1\}$이 선택되었을 때, 먼저 갑이 임의의 $x\_n\backslash in(x\_\{n-1\},y\_\{n-1\})$을 취하고, 을은 임의의 $y\_n\backslash in(x\_n,y\_\{n-1\})$를 취한다.
• 이 경우, $(x\_n)\_\{n=0\}^\backslash infty$는 수렴하며, $\backslash textstyle\backslash lim\_\{n\backslash to\backslash infty\}x\_n\backslash in(0,1)$이다. 만약 $\backslash textstyle\backslash lim\_\{n\backslash to\backslash infty\}x\_n\backslash in\; S$라면 갑이 승리하며, 만약 $\backslash textstyle\backslash lim\_\{n\backslash to\backslash infty\}x\_n\backslash not\backslash in\; S$라면 을이 승리한다.

• 만약 $n\backslash le|S|$이며 $s\_n\backslash in(x\_n,y\_\{n-1\})$라면, 을은 $n$번째 실수로 $y\_n=s\_n$을 취한다.
• 만약 $n>|S|$이거나 $s\_n\backslash not\backslash in(x\_n,y\_\{n-1\})$라면, 을은 $n$번째 실수로 임의의 $y\_n\backslash in(x\_n,y\_\{n-1\})$을 취한다.

4. 칸토어의 정리

칸토어의 정리는 임의의 집합과 그 멱집합의 크기가 서로 다르다는 것을 보여주는 정리이다. 이 정리는 대각선 논법을 사용하여 증명할 수 있다. 이 정리에 따르면, 어떤 집합의 멱집합은 항상 원래 집합보다 크기가 크다.

이 정리는 집합의 크기에 대한 무한한 위계질서가 존재함을 의미한다. 즉, 무한 집합에도 여러 종류가 있으며, 그 크기를 비교할 수 있다는 것을 보여준다. 예를 들어, 자연수 집합보다 실수의 집합이 더 크다는 것을 증명할 수 있다.

이와 관련하여, 멱집합의 크기가 원래 집합보다 크다는 것은 알지만, 그 사이에 다른 크기의 집합이 존재하는지에 대한 질문이 제기될 수 있다. 이 문제는 연속체 가설로 알려져 있다.

위의 구성은 러셀의 역설에서 이용되는 자기 자신을 포함하지 않는 집합과 유사하다.

두 집합의 기수 동등성은 두 집합의 기본 집합 간의 전단사 함수의 존재로 정의되며, 칸토어는 두 집합 간의 단사 함수의 존재를 통해 이진 술어를 정의한다. 이는 준순서의 속성을 가지며, "$\backslash le$"로 표기한다. 자연수를 이진 시퀀스에 포함시켜 다양한 "단사 함수 존재" 명제를 명시적으로 증명할 수 있으며, 이러한 의미에서 $|\{\backslash mathbb\; N\}|\backslash le|2^\{\backslash mathbb\; N\}|$ 이 성립한다. 여기서 $2^\{\backslash mathbb\; N\}$은 함수 공간 $\{\backslash mathbb\; N\}\backslash to\backslash \{0,1\backslash \}$을 나타낸다. 그러나 앞서 설명한 논증에 따라, "전사 함수"는 존재하지 않으며, 따라서 전단사 함수도 존재하지 않는다. 즉, 집합은 가산 집합이 아니다. 이를 로 표기할 수 있으며, 여기서 ""는 칸토어의 준순서의 부정이 아닌, 할당된 서수를 기준으로 정의된, 단사 함수의 존재와 전단사 함수의 부재를 의미한다. 또한, 앞서 증명했듯이 이 성립하며, 동시에 모든 집합 $S$에 대해 $\backslash neg(|\{\backslash mathcal\; P\}(S)|\backslash le|S|)$ 이 성립한다.

배중률을 가정하면, 특성 함수는 거듭제곱 집합으로 전사하고, 따라서 $|2^S|=|\{\backslash mathcal\; P\}(S)|$가 된다. 따라서 비가산 집합 $2^\{\backslash mathbb\; N\}$은 셀 수 없으며 $\{\backslash mathbb\; N\}$으로 사상될 수도 없다. 고전적으로, 슈뢰더–베른슈타인 정리가 성립하며, 서로의 단사 이미지에 있는 두 집합은 전단사 함수를 갖는다고 말한다. 여기서 $\{\backslash mathbb\; N\}$의 모든 무제한 부분 집합은 $\{\backslash mathbb\; N\}$ 자체와 전단사 함수를 가지며, 모든 가산 부분 집합 (전사 함수에 따른 속성)은 이미 가산 집합, 즉 $\{\backslash mathbb\; N\}$의 전사 이미지에 있다. 이러한 맥락에서 가능성은 모두 소진되어 "$\backslash le$"는 부분 순서 (non-strict partial order)가 되거나, 선택 공리를 가정할 때에는 전순서가 된다. 따라서 대각선 논법은 고려 중인 두 집합이 모두 무한하지만, 실제로 자연수보다 무한한 1과 0의 시퀀스가 "더 많다"는 것을 확립한다.

칸토어의 결과는 또한 모든 집합의 집합의 개념이 모순됨을 의미한다. 만약 $S$가 모든 집합의 집합이라면, $\{\backslash mathcal\; P\}(S)$는 동시에 $S$보다 크면서 $S$의 부분 집합이 될 것이다.

4. 1. 증명

• 임의의 $a\backslash in\; A$에 대하여, $A\backslash ne\; f(a)$이다.
• * 정의에 따라서 $a\backslash not\backslash in\; f(a)$이다. 그러나 $a\backslash in\; A$이므로, $A\backslash ne\; f(a)$이다.
• 임의의 $b\backslash in\; X\backslash setminus\; A$에 대하여, $A\backslash ne\; f(b)$이다.
• * 정의에 따라서 $b\backslash in\; f(b)$이다. 그러나 이 경우 $b\backslash not\backslash in\; A$이므로, $A\backslash ne\; f(b)$이다.

4. 2. 칸토어 역설

5. 연속체 가설

연속체 가설은 자연수 집합의 크기와 실수 집합의 크기 사이에 다른 크기의 집합이 존재하지 않는다는 주장이다. 이 가설은 참인지 거짓인지 증명할 수 없다고 밝혀졌다.

실수의 집합이 자연수의 집합보다 "크다"는 것에서 착안하여, 정수의 기수와 실수의 기수 "사이"에 있는 집합이 있는지 묻는 질문은 연속체 가설로 이어졌다.

5. 1. 일반화된 연속체 가설

6. 정지 문제의 결정 불가능성

정지 문제는 주어진 프로그램이 멈출지 여부를 판별하는 문제이다. 앨런 튜링은 대각선 논법을 응용하여 이 문제가 알고리즘적으로 해결 불가능함을 증명했다. 정지 문제 증명 자체가 대각선 논법의 응용으로 볼 수 있다.^[24]

정지 문제의 결정 불가능성은 "유한 시간"과 "무한 시간"이라는 두 개의 시간 계층 사이의 시간 계층 정리로 해석할 수 있다. 따라서 시간 계층 정리의 증명은 정지 문제의 결정 불가능성 증명을 다시 사용한 것으로 볼 수 있으며, 시간 계층 정리의 증명 또한 대각선 논법을 사용하고 있음을 알 수 있다.

6. 1. 증명

6. 2. 괴델의 불완전성 정리와의 관계

7. 콰인의 새 기초(NF)에서의 대각선 논법

W. V. 콰인의 집합론 "새로운 기초"(NF)에서는 기존의 대각선 논법이 성립하지 않는다. NF는 순진한 외연 공리 대신 "국소적" 타입 이론을 도입하여 역설을 피한다. 이 체계에서는 다음 집합이 정의되지 않는다.

:{ ''s'' ∈ ''S'': ''s'' ∉ ''f''(''s'') }

그러나 NF에서도 수정된 대각선 논법을 구성할 수 있다.

:{ ''s'' ∈ ''S'': ''s'' ∉ ''f''({''s''}) }

위 집합은 NF에서 집합으로 정의된다. '''''P'''''₁(''S'')를 ''S''의 원소 하나짜리 부분집합들의 집합, ''f''를 '''''P'''''₁(''S'')에서 '''''P'''''(''S'')로의 전단사 함수라고 할 때, 귀류법을 통해 |'''''P'''''₁(''S'')| < |'''''P'''''(''S'')| 임을 보일 수 있다.

만약 ''f''가 '''''P'''''(''S'')로의 전사라면, 수정된 대각선 집합과 일치하는 ''S''의 원소 ''r''이 존재해야 한다. 그러면 ''r''이 ''f''({''r''})에 속하지 않으면 ''r''은 ''f''({''r''})에 속하고, 그 반대도 성립하는 모순이 발생한다.

'''''P'''''₁(''S'')와 ''S''는 일대일 대응될 수 없다. 둘은 서로 다른 타입을 가지며, 일대일 대응을 정의하려는 시도는 NF의 외연 공리 체계의 타입 규칙을 위반하기 때문이다.

참조

_[1] 문서 the '''diagonalisation argument''', the '''diagonal slash argument''', the '''anti-diagonal argument''', the '''diagonal method''', and '''Cantor's diagonalization proof'''
_[2] 논문 Ueber eine elementare Frage der Mannigfaltigkeitslehre https://www.digizeit[...]
_[3] 서적 Universality and the Liar: An Essay on Truth and the Diagonal Argument https://books.google[...] Cambridge University Press 1993-07-30
_[4] 서적 Principles of Mathematical Analysis https://archive.org/[...] McGraw-Hill 1976
_[5] 간행물 Georg Cantor and Transcendental Numbers http://www.maa.org/s[...]
_[6] 서적 The Real Numbers and Real Analysis https://archive.org/[...] Springer 2011
_[7] 서적 The Logic of Infinity https://books.google[...] Cambridge University Press
_[8] 서적 Russell's paradox http://plato.stanfor[...] Stanford encyclopedia of philosophy
_[9] 서적 Principles of mathematics Norton
_[10] 문서
_[11] 문서
_[12] 문서
_[13] 간행물 Ein Beitrag zur Mannigfaltigkeitslehre http://www.digizeits[...]
_[14] arXiv Cantor-Bernstein implies Excluded Middle
_[15] 간행물 One hundred years of Russell's paradox de Gruyter, Berlin
_[16] 문서 Choice principles in constructive and classical set theories http://www1.maths.le[...]
_[17] 문서 An injection from N^N to N http://math.andrej.c[...]
_[18] 서적 Mathematics and Logic in History and in Contemporary Thought Transaction Publishers
_[19] arXiv The Countable Reals
_[20] 문서 On the Cauchy Completeness of the Constructive Cauchy Reals https://arxiv.org/pd[...] 2015-07
_[21] 논문 Uber ein elementare Frage der Mannigfaltigkeitslehre Deutsche Mathematiker-Vereinigung 1891
_[22] 문서
_[23] 문서
_[24] 문서
_[25] 간행물 Ueber eine elementare Frage der Mannigfaltigkeitslehre https://www.digizeit[...]