| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계(동치관계 · 순서 관계) · 순서쌍(튜플) · 서수(하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC(선택공리) · 기수(초한기수) · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
| 4분 30초 경 대각선 논법이 사용되었다. |
對角線 論法 / diagonal argument
게오르크 칸토어가 자연수의 집합과 실수의 집합의 원소의 개수가 서로 다르다는 것을 증명할 때 사용했던 방법이다. 이전까지 수학계에서 함부로 다루지 않던 무한의 개수를 다루며 한 획을 그은 증명. 이후에 연속체 가설로 이어지며 힐베르트의 23가지 문제에도 포함되었다.
2. 상세
칸토어가 제시한 대각선 논법은 실수 집합의 크기가 자연수 집합의 크기와 같지 않다는 것을 증명하는 데에 쓰인 것이다. 그리고 그 논법이 임의의 집합과 그 멱집합 사이의 크기 비교에도 적용된 것. 순서대로 살펴 보자.2.1. 집합의 크기라는 것의 의미
먼저 직관에서 벗어나 보이는 몇 가지 사실들을 짚고 가자. 자연수 집합과 정수 집합, 그리고 심지어 유리수 집합의 크기는 모두 같다. 이것은 수 체계에서 간단히 언급된 것이다. 유리수 집합이 자연수들을 모조리 포함하면서도 자연수가 아닌 수들을 포함하고 있다는 것을 생각해보면 보면 둘의 크기가 같다는 것을 납득하기가 어려울 수도 있다. 이러한 사실들과 직관 사이의 괴리는 집합의 '크기' 혹은 '크기의 대소 비교'로부터 비롯된다. 두 집합 [math(A, B)] 간의 대소 비교는 다음으로 정의된다.- 한 일대일 대응(bijection) [math(A \to B)]가 존재하면 [math(A)]와 [math(B)]의 크기는 같다고 한다. 즉 [math(A)]와 [math(B)] 사이에 전단사함수가 존재한다.
- 한 일대일 사상(injection) [math(A \to B)]가 존재하면 [math(A)]의 크기는 [math(B)]의 크기보다 작거나 같다고 한다. 즉 [math(A)]에서 [math(B)]로 가는 단사함수가 존재한다.
일대일 사상[1]은 [math(A)]의 각 원소가 [math(B)]의 원소에 겹침 없이 보내진다는 것이다. 즉, [math(A)]의 두 다른 원소 [math(a, a')]에 대해 사상을 취한 결과는 서로 달라야 한다는 것이다. 대표적인 예가 (정의역이 실수 집합의 부분집합일 때) [math(f\left(x\right)=x^3)] 혹은 [math(f\left(x\right)=e^x)]이고, 일대일 사상이 아닌 예로 [math(f\left(x\right) = x^2)]로 정의된 실수 전체에서 실수 전체로 보내지는 사상이다. 일대일 대응은 일대일 사상이면서 [math(B)]의 모든 원소가 [math(A)]의 한 원소에 대응되는 것인데, 말 그대로 [math(A)]와 [math(B)]의 각 원소들이 일대일로 매칭이 되는 상황이다. 예컨대 정의역과 공역을 실수 집합 전체로 잡았을 때 [math(f\left(x\right)=e^x)]로 정의된 함수는 0보다 작거나 같은 값으로 보내지는 [math(x)] 값이 없기에 이 함수는 일대일 대응이 아니다. 하지만 [math(f\left(x\right)=x^3)]는 일대일 대응이 된다. 다만, 모든 일대일 사상은 공역을 치역으로 제한한 새로운 사상을 만드는 것으로 일대일 대응을 만들 수 있다. 비록 원래 공역의 한 부분집합과 일대일 대응될 뿐이지만. 예컨대 [math(f\left(x\right)=e^x)]의 경우는 공역을 양의 실수 집합으로 제한하는 것으로 일대일 대응으로 만들 수 있다.
이 개념을 가지고 집합의 크기를 이해할 수 있다. 유한한 집합이라고 하는 것은 사실 원소 하나하나 세는 것으로 그 크기를 잴 수 있었다. 예를 들어 집합 [math(\left\{a, b, c, d, e, f, g\right\})] 같은 경우 우리는 손가락으로 하나하나 카리키면서 하나(a), 둘(b), 셋(c), ..., 일곱(g) 끝 하는 식으로 헤아려서 그 집합의 '크기'가 7이라고 말한다. 그런데 이렇게 하나하나 헤아린다는 것은 원소 하나하나에 양의 정수를 하나 씩 대응시키는 작업과 같다. 그리고 방금 든 예의 경우 하나 씩 대응시키면서 남거나 모자르는 일 없이 대응이 될 수 있는 경우는 [math(\left\{1, 2, 3, 4, 5, 6\right\})]도 아니고 [math(\left\{1, 2, 3, 4, 5, 6, 7, 8\right\})]도 아닌 [math(\left\{1, 2, 3, 4, 5, 6, 7\right\})]인 경우였다. 그런데 사실 세는 방법은 하나만 있는 것이 아니다. g부터 거꾸로 셀 수도 있고 b부터 셀 수도 있고... 아무튼 많다. 다만 어떻게 세든 간에 결국 그런 일대일 대응이 최소 하나는 존재한다는 것만 확인하면 된다. 이러한 점을 고려해보면 결국 집합의 크기를 센다는 것은 어떤 양의 정수 [math(n)]보다 작거나 같은 양의 정수들의 집합 [math(\left\{1, 2, 3, \cdots, n\right\})]와 그 집합을 일대일 대응을 시키는 작업으로 보면 될 것 같다.
하지만 다음과 같은 문제가 있다. 어떤 사람은 [math(\left\{1, 3, 5, 7, 9, 11, 13\right\})]도 되지 않느냐고 따질 수도 있다. 또한 자연수 집합 전체나 유리수 집합의 경우 아무리 큰 양의 정수 [math(n)]이 주어지든 [math(\left\{1, 2, 3, \cdots, n\right\})] 같은 집합과는 일대일 대응이 존재하지 않는다. 이런 점들을 봤을 때 집합의 크기를 정함에 있어 [math(\left\{1, 2, 3, \cdots, n\right\})] 같은 것에 벗어나야 좀 더 일반적인 '크기'를 말할 수 있을 것 같아 보인다. 사실 위의 예에서 중요한 건 일대일 대응이 하나라도 존재하는가 하는 것이었다.
결국 집합의 크기 혹은 그 대소 비교는 위와 같이 일대일 대응의 존재 유무만 남게 되었다. 그야말로 '하나하나 헤아린다'를 추상화시킨 것이다. 한편, [math(\left\{1, 2, 3, \cdots, n\right\})] 같은 집합과 자연수 전체 집합 사이에는 일대일 대응이 존재하지 않지만 일대일 사상은 만들 수 있다는 것으로부터 같냐 안 같냐만 말할 수 있는 것이 아니라 대소 비교도 정의할 수 있게 되는 것이다. 부분집합과 일대일 대응이 가능해도 전체와 대응이 안 될 때 정의역 집합이 공역 집합보다 더 작다고 말하는 것은 자연스러워 보이기 때문이다. 그래서 위와 같은 정의가 가능해진 것이다.
다시 맨 처음의 자연수 집합과 정수 집합, 유리수 집합으로 돌아가자. 거칠게 설명하자면 지그재그로 정수 집합과 유리수 집합을 헤아리는 것으로 가능하다. 자세한 것은 여기서 다루지 않겠지만 어쨌든 세 집합들 사이에는 일대일 대응이 존재하긴 한다.[2] 추상화가 예상치도 못한 결과를 가져다 준다는 좋은 예시로 볼 수 있겠다.
아무튼 칸토어는 이런 작업 이후 어쩌면 모든 무한 집합([math(\left\{1, 2, 3, \cdots, n\right\})] 같은 것과 일대일 대응이 되지 않는 집합[3])이 전부 다 자연수 집합과 같은 크기를 가지지 않을까 하는 추측을 하게 된다. 하지만 이런 기대는 칸토어 본인의 손에 의해 무너지게 된다.
2.2. 대각선 논법 - 실수 집합은 양의 정수의 집합보다 크다
증명은 너무나도 직관적이고 아름다운 나머지 에르되시 팔은 이 증명을 '하느님이 가지고 있는 수학책'에 실려 있을 증명이라고 부를 정도였다.먼저 문제를 간단하게 하기 위해 실수 집합 전체 대신 개구간 [math(\left(0,\,1\right))]을 사용한다. 사실 함수 [math(f : \left(0, 1\right) \to \mathbb{R})]를 [math(f\left(x\right) = \tan{\left( \pi x - \frac{\pi}{2} \right)})]로 정의하면 실수 전체 집합과 구간 [math(\left(0,\,1\right))]의 크기가 같다는 것을 알 수 있고, 따라서 양의 정수의 집합 [math( \mathbb{Z}^+)]과 구간 [math(\left(0,\,1\right))]의 크기만 비교하면 증명은 끝난다.
먼저 양의 정수의 집합에서 구간 [math(\left(0,\,1\right))]로 가는 전단사함수 [math(f)]가 존재한다고 가정하자. 이때 각 [math(f\left(n\right))]는 다음과 같이 무한소수로 표현될 수 있을 것이다.
[math(f\left(1\right) = 0.a_{11} a_{12} a_{13} a_{14} a_{15} \cdots)]
[math(f\left(2\right) = 0.a_{21} a_{22} a_{23} a_{24} a_{25} \cdots)]
[math(f\left(3\right) = 0.a_{31} a_{32} a_{33} a_{34} a_{35} \cdots)]
[math(f\left(4\right) = 0.a_{41} a_{42} a_{43} a_{44} a_{45} \cdots)]
[math(f\left(5\right) = 0.a_{51} a_{52} a_{53} a_{54} a_{55} \cdots)]
[math(\cdots)]
여기서 각 [math(a_{ij})]는 [math(0)]부터 [math(9)]까지의 어떤 정수 숫자들이다. 이런 식으로 [math(0)]과 [math(1)] 사이의 모든 실수들이 하나도 빠짐없이 하나의 양의 정수에 중복없이 대응된다. 참고로 혼돈을 피하기 위해 [math(0\cdots 999\cdots)] 같은 어딘가서부터 9로만 이루어진 표현은 없다고 치자. 어차피 이런 경우는 적당한 유한 소수, 즉 어딘가서부터 0으로만 나타나는 표현으로 쓸 수 있기 때문이다. 즉, [math(0.0999cdots)]같은 것은 어차피 [math(0.10000cdots)]과 같으니 쓰지 않겠다는 말이다. 이렇게 실수들을 무한소수로 표현하면 두 소수들의 어느 한 자리만 달라도 두 실수가 다르다는 것을 쉽게 확인할 수 있다.
가정에 따라 모든 [math(0)]과 [math(1)] 사이의 실수들이 [math(f)]로 인해 하나의 양의 정수에 빠짐 없이 대응된다고 했다. 즉, [math(0)]과 [math(1)] 사이에 어떤 실수를 고르든 어떤 [math(f\left(n\right))] 중 하나와 같아야 한다. 하지만 어떠한 [math(f\left(n\right))]과도 같지 않은 [math(0)]과 [math(1)] 사이의 어떤 실수를 제시할 수 있다.
[math(0)]과 [math(1)] 사이의 다음과 같은 실수 [math(x)]를 생각할 수 있다. [math(x)]의 소수 [math(i)]번째 자리의 수 [math(b_{i})]는, [math(a_{ii})]가 [math(0)]이거나 [math(9)]보다 작은 자연수일 때는 [math(a_{ii} + 1)]이고, [math(9)]일 때는 [math(0)]이다. 즉 [math(x = 0.b_1 b_2 b_3 \cdots)]라고 하자. 예를 들어 [math(a_{ii})]이 다음과 같다면
[math(f\left(1\right) = 0.\; 3 \;\; a_{12} a_{13} a_{14} a_{15} \cdots)]
[math(f\left(2\right) = 0.a_{21} \; 1 \;\; a_{23} a_{24} a_{25} \cdots)]
[math(f\left(3\right) = 0.a_{31} a_{32} \; 9 \;\; a_{34} a_{35} \cdots)]
[math(f\left(4\right) = 0.a_{41} a_{42} a_{43} \; 8 \;\; a_{45} \cdots)]
[math(f\left(5\right) = 0.a_{51} a_{52} a_{53} a_{54} \; 5 \;\; \cdots)]
[math(\cdots)],
즉 [math(a_{11} = 3, a_{22} = 1, a_{33} = 9, a_{44} = 8, a_{55} = 5, \cdots)]이면, [math(x)]는 정의에 따라 다음과 같다.
[math(x=0.42096\cdots)]
그렇다면 모든 양의 정수 [math(n)]에 대하여 [math(f\left(n\right))]과 [math(x)]의 [math(n)]번째 자리 수는 다르게 되고, 따라서 [math(x)]는 모든 [math(f\left(n\right))]과 적어도 한 자리에서 다르다. 위의 소수 표현에 대한 설명으로부터 [math(x)]가 모든 [math(f\left(n\right))]와 다르다는 것이 따라 나오고 이는 위에 강조 처리한 문장 바로 전의 말과 모순이다. 결국 처음에 했던 가정은 거짓이 된다. 즉, [math( \mathbb{Z}^+)]과 [math( \mathbb{R})] 간에는 일대일 대응이 존재하지 않는다는 것이다. 반면 [math( \mathbb{Z}^+)]은 [math( \mathbb{R})]의 부분집합이므로 [math( \mathbb{R})]의 크기는 [math( \mathbb{Z}^+)]의 크기보다 크거나 같다. 따라서 [math( \mathbb{R})]의 크기는 [math( \mathbb{Z}^+)]보다 크다.
위와 같은 방식 덕분에 칸토어의 논증 방법은 대각선 논법이라는 이름을 얻게 되었다.[4] 이와 비슷한 방식을 일반적인 집합에 적용시킬 수 있다.
2.3. 대각선 논법 - 모든 집합은 자신의 멱집합(power set)보다 작다
멱집합(power set)은 주어진 집합의 부분집합을 모두 모은 집합이다. 주어진 집합이 [math(A)]로 표기될 경우 기호로는 [math(\mathcal{P}\left(A\right))]로 표기된다. 이제 할 일은 임의의 [math(A)]에 대해 [math(A)]와 [math(\mathcal{P}\left(A\right))] 간에 일대일 대응은 존재하지 않는다는 것을 보이는 것이다.논리적인 어려움을 피하기 위해 먼저 [math(A)]가 공집합인 경우를 따로 살펴 보자. [math(\mathcal{P}\left(A\right)= \left\{\emptyset\right\} )] 이므로 [math(A = \emptyset\ )]과 일대일 대응이 존재하지 않는다.
이제 [math(A)]가 공집합이 아닌 경우를 살펴 보자. 위에서 그랬듯이 일대일 대응 [math(f : A \to \mathcal{P}\left(A\right))]가 존재한다고 가정하자. 그러면 [math(\mathcal{P}\left(A\right))]의 모든 원소들, 즉 [math(A)]의 모든 부분집합들은 [math(f\left(a\right))] ([math(a \in A)])와 일대일 대응된다. 이제 할 일은 [math(f\left(a\right))]들 중 어느 것과도 같지 않은 [math(A)]의 부분집합을 찾아내는 것이다.
실수의 경우에는 [math(f\left(n\right))]와 다르게 하기 위해 [math(n)]번째 자리가 다르도록 해서 새로운 수를 정의했었다. 집합의 경우면 뭘까? 이걸 그대로 적용시킨다면 아무래도 집합 [math(A)]의 어떤 부분집합 [math(X)]는 [math(f\left(a\right))]와 [math(a)] 때문에 달라야 할 것이다. 집합론의 언어에서 이걸 가지고 생각할 만한 것은 딱 하나. 원소 [math(a)]가 속하느냐 아니냐는 것이다. 따라서 가장 좋은 방법은 [math(f\left(a\right))]가 [math(a)]를 원소로 가지느냐 아니냐에 대해서 [math(X)]는 그 반대가 되게 하는 것이다.
그러므로 [math(X)]를 다음과 같이 정의하자.
[math(X = \left\{a \in A \; | \; a \notin f\left(a\right)\right\})].
[math(X)]는 [math(A)]의 원소로만 이루어져 있으므로 [math(A)]의 부분집합이고, 그렇다면 [math(X = f\left(e\right))]가 되게 하는 어떤 [math(e \in A)]가 존재할 것이다. 그런데
- [math(e \in f\left(e\right))]인 경우 : 정의에 의해 [math(e \notin X)]이므로 [math(X \ne f\left(e\right))].
- [math(e \notin f\left(e\right))]인 경우 : 정의에 의해 [math(e \in X)]이므로 [math(X \ne f\left(e\right))].
이므로 [math(X = f\left(e\right))]가 되게 하는 [math(e \in A)]는 존재하지 않는다.
결국 [math(X)]는 어느 [math(f\left(a\right))]와도 같지 않다는 결과를 얻을 수 있고, 이는 가정과 모순이다. 따라서 [math(A)]와 [math(\mathcal{P}\left(A\right))] 간에는 일대일 대응이 존재하지 않는다.
한편 [math(g : A \to \mathcal{P}\left(A\right), a \mapsto \left\{a\right\})]와 같이 정의된 사상은 일대일 대응이 아닌 일대일 사상이다. 이것으로부터 모든 집합은 그 power set보다 작다는 것을 알 수 있다.
참고로 [math(Q = \left\{f \;|\; f : A \to \left\{0, 1\right\}\right\})]로 두면 [math(\mathcal{P}\left(A\right))]와 [math(Q)] 간에 일대일 대응이 존재한다는 것을 보일 수 있다.[5]
두 집합 [math(X, Y)]가 주어져 있을 때 [math(Y^X = \left\{f \;|\; f : X \to Y\right\})]로 표기한다. 이 표기대로라면 사실 [math(Q = \left\{0, 1\right\}^A)]인 것이다. 또한 [math(X)], [math(Y)]의 크기[6]를 [math(\left|X\right|)], [math(\left|Y\right|)]라 적는다. [7], [math(\left|X\right|^{\left|Y\right|} = \left|X^Y\right|)]로 정의한다. 따라서 [math(\left|\mathcal{P}\left(A\right)\right| = \left|Q\right| = \left|\left\{0, 1\right\}^A\right| = 2^{\left|A\right|})]가 되는 것이다. 위에서 보인 내용은 다름 아닌
[math(\left|A\right| < 2^{\left|A\right|})]
임을 보인 것이다.
2.4. 대각선 논법 - 어떠한 튜링 기계도 (유한 시간 내에) 풀 수 없는 문제가 존재한다
임의의 (이진 언어) 튜링 머신 M은 그 조작을 어떤 프로그래밍 언어로 기술할 수 있고 (브레인퍽 등) 따라서 (이진) 코드 <M>으로 이것을 나타낼 수 있다. 나아가, (이진 언어) 튜링 머신과 그 입력값의 쌍 (M,w)에 대해, 이것을 돌리면 M은 yes를 뱉으면서 멈추거나, no를 뱉으면서 멈추거나, 그냥 영원히 돌아갈 수 있을 것이다. 이 때 주어진 (이진 언어) 튜링 머신 M에 대해 (이진) 입력값의 모임L(M) = {w | (M,w)를 돌리면 yes를 뱉고 멈춘다}
로 정의하자. (이것을 M이 푸는/결정하는 문제(the problem that M decides)라 부른다.)L(M)은 단순히 (이진) 코드의 모임임에도 문제라는 표현을 쓰는 데에는 약간의 배경이 있다. 임의의 참/거짓을 확실히 가릴 수 있는 문제는, 적절한 데이터 구조 아래에서 이 구조가 이런이런 조건을 만족하느냐는 것으로 말을 바꿀 수 있다. 이 데이터 구조는 항상 이진 코드로 나타낼 수 있고, 따라서 대개의 참/거짓 문제는 이진 코드의 집합 [math( S \subset \{ 0,1 \}^{\ast} )]으로 나타난다. 간단히, 뭔가 답이 필요한 입력이 있으면 입력을 이진코드화 해서 S에 들어가는지 아닌지로 체크해서 들어가면 ㅇㅋ 하고 끝내면 문제 해결 개이득!인 셈.
이제 문제는 임의의 부분집합 [math( S \subset \{ 0,1 \}^{\ast} )]이 튜링 머신이 결정하는 문제로 환원이 되느냐인데...
튜링 머신의 코드의 집합 [math( S = \{ \langle M \rangle \; | \; \langle M \rangle \notin L(M) \} )]을 생각하자.[8] 이 때 [math( S = L(N) )]인 튜링 머신 N이 존재하는지를 여기서 물을 것이다. 그러한 N이 존재한다고 하자. 그러면,
- [math( \langle N \rangle \in S )]인 경우, S의 정의에 의해 [math( \langle N \rangle \notin L(N)=S )]이므로 모순.
- [math( \langle N \rangle \notin S = L(N) )]인 경우, S의 정의에 의해 [math( \langle N \rangle \in S )]이므로 모순.
즉, 위에서 쓴 [math( L \colon \{ \text{Turing machines} \} \to \mathcal{P} ( \{ 0,1 \}^{\ast} ) )]은 모든 [math( \{ 0,1 \}^\ast )]의 부분집합을 커버하지 못한다. 따라서 어떤 튜링 머신이 풀지 못하는 문제가 존재하게 된다.
2.5. 러셀의 역설 - 모든 집합의 집합은 존재하지 않는다
멱집합과 튜링 머신에 대한 대각선 논법은, 둘 다 원소 단계의 객체 a를 집합 단계의 객체 f(a)로 보낸 후, a가 f(a)에 속하지 않는 a의 모임을 찾아내 이것이 f(b) 꼴로 나타날 수 없다는 방법을 쓰고 있다. 실수에 대한 대각선 논법 또한 크게 다르지 않아, 근본적으로는 자연수의 멱집합 [math( \mathcal{P} (\mathbb{N}) )]과 0과 1 사이의 실수와 대응하는 데에서 출발한다.러셀의 역설은 직관적 집합론이 모순이 있다는 것을 밝히는 것 외에도, 임의의 집합의 집합 S에 대해, [math( B = \{ X \in S \; | \; X \notin X \} )]라는 S에서 보이지 않는 새 집합을 만들어내는 수순으로 볼 수 있다. X를 S의 원소 단계의 객체로 볼 수도, (X 자체가 집합이니까) 집합 단계의 객체로 볼 수 있기 때문. 이 B를 만들어내는 과정 자체도 대각선 논법의 일종으로, 그 따름정리로 다음을 얻는다.
어떤 집합의 집합 S에 대해, S보다 더 큰 집합의 집합이 존재한다.
곧, 모든 집합의 모임은 "집합 수준의" 크기로는 도저히 담을 수 없을 정도로 크다는 뜻으로 받아들일 수 있다. 즉, 대각선 논법은 집합을 초월하는 크기에 대해서도 그 크기 비교를 할 수 있는 것.3. 의의
수학사적으로 칸토어 이전에 '무한'이라는 것을 이렇게 체계적으로 다룬 사람은 없었다. 학자들 사이에선 무한이라는 것을 다루는 것이 터부시될 정도였다. 무한의 성질 때문에 제논의 역설이나 힐베르트의 호텔과 같은 기존의 수학으로는 설명할 수 없는 이상한 일들이 벌어졌기 때문이다. 하지만 인류의 집합론이 이 이상의 다음 단계로 발전하기 위해선 무한집합을 제대로 이해할 반석이 필요했고, 칸토어는 최초로 이를 해낸 위인이 되었다. 그 성과 중 하나가 무한의 크기는 다양하다이고 위에서 보인 것이 바로 그 사실이다. 자연수 집합이 무한집합이고 그 어떤 집합보다 커 보였지만 사실 더 큰 집합이 존재하고 사실 그 어떤 (무한)집합을 택해도 그 집합보다 더 큰 집합이 존재한다는 것을 논리적으로 증명해낸 것이다.이런 놀라운 결과는 수학계에서 바로 받아들여지지 못했다. 칸토어의 말년이 불우했던 까닭도 여기서 찾을 수 있다. 하지만 집합의 성질들이 수학의 영역이 성숙해 갈 수록 중요해지면서[9][10] 후대 수학자들은 칸토어의 집합론을 받아들이기 시작했고 더더욱 발전시켰다.
한편 우리는 임의의 집합 [math(A)]에 대해 [math(|A| < 2^{|A|})]임을 봤었다. 사실 모든 무한집합은 자연수와 크기가 같은 부분집합을 포함한다. 이는 자연수 집합이 무한집합들 중에서 제일 작은 집합이라는 것을 의미한다. 수학자들은 자연수 집합의 크기를 흔히 [math(\aleph_0)]로 표기한다.[11] 한편, 우리가 아는 상당 수의 집합들이 사실은 (안 그래 보여도) 자연수 집합과 크기가 같다는 것을 설명했었고, 그러면서도 실수 집합은 그 크기가 [math(2^{\aleph_0})]임을 알았다. 그리고 흔히 [math(c = 2^{\aleph_0})]로 표현한다. 사실 자연수를 포함하거나 혹은 우리가 잘 아는 수 체계로부터 출발하여 얻어진 집합들 중에 [math(\aleph_0)] 혹은 [math(c)]가 아녔던 것은 거의 없었다. 있다 해도 [math(2^{c})]라든가 혹은 이것의 또다른 지수 같은 것이었을 뿐이었다.
여기서 한 가지 질문을 할 수 있다. 그러면 [math(\aleph_0 < |X| < c)]를 만족하는 집합 [math(X)]가 존재하는가? 해봄직한 질문이긴 한데 문제는 어느 누구도 저런 집합을 찾지 못하였고 그러면서도 저런 집합이 없다고 밝힌 사람은 또 없었다는 것이다. 왠지 있을 것 같은데 전혀 안 보이고 그렇다고 없다고 말할 수도 없으니 사람들은 아리송할 수밖에. 저런 집합이 존재하지 않을 거라고 가정하는 것을 가리켜 연속체 가설(Continuum Hypothesis)라고 부른다. 그리고 잘 알려져 있다시피 연속체 가설이 맞느냐 틀리느냐를 밝히라는 게 바로 힐베르트의 23가지 문제 중 첫 번째 문제였다.
결론부터 말하자면 이 문제는 풀렸는데 그 답이 또 골때린다. 맞다고 가정해도 문제 없고 틀렸다고 가정해도 문제 없다가 답이다. 즉, 저 가설의 참과 거짓 어느 것을 주장해도 수학을 모순 없이 잘 전개할 수 있다는 것이다.
4. 관련 문서
[1] 특히 [math(B)]가 수 집합이면 일대일 함수라고도 불린다.[2] 실제로는 주어진 집합이 자연수 집합보다 작거나 같다는 것을 보이는 것으로 증명을 완료하는 경우가 많다. 즉, 일대일 대응은 아니더라도 '크거나 같다'와 '작거나 같다' 둘 다를 보여 결국 크기가 같다고 주장하는 식이다. 하지만 집합 A가 B보다 크거나 같고 B가 A보다 크거나 같다면 당연히 두 집합의 크기가 동일해야 할 것 같지만 이 또한 증명되어야 한다. 이는 '슈뢰더-베른슈타인 정리'라는 이름으로 증명이 되었다.[3] 자기 자신과 일대일 대응이 되는 진부분집합을 갖는 집합이라고 정의되기도 한다. 그런데 이 두 정의는 사실 똑같다는 것을 증명할 수 있다.[4] 사실 칸토어는 대각선 논법 이전에 이미 자연수 집합과 실수 집합 간에 일대일 대응은 있을 수 없다는 것을 다른 방식으로 보였다. 이 방법은 실수의 근본적인 성질에 기초한 것이라 더 어려워 보이지만 그만큼 더 확실해 보인다. 반면 대각선 논법에서 쓰인 실수의 소수 표현은 모호하다는 느낌을 받을 수 있다. 칸토어가 최초로 실수가 비가산임을 증명하는 방법은 실수의 위상적 성질중 하나인 축소구간정리(nested intervals theorem)를 이용한 것이다.증명. 해당 증명은 축소구간정리 문서의 3.1 문단에 소개되어 있다.[5] [math(\chi : \mathcal{P}\left(A\right) \to Q)]를 [math(\chi\left(A\right)\left(x\right):=\begin{cases}1 & \phantom{\cdots}x\in A\\0 & \phantom{\cdots}x\notin A\end{cases})], [math(\overline{\chi} : Q \to \mathcal{P}\left(A\right))]를 [math(\overline{\chi}\left(f\right) = \left\{x \in A \;|\; f\left(x\right) = 1\right\})]로 정의하자. 그러면 (일단 [math(\chi)]가 올바른 사상인지부터 보인 다음) [math(\chi \circ \overline{\chi})]와 [math(\overline{\chi} \circ \chi)] 둘 다 항등 사상임을 금방 알 수 있다. 따라서 두 사상 [math(\overline{\chi})], [math(\chi)]는 서로 역사상 관계이며 이로부터 [math(\overline{\chi})], [math(\chi)]가 일대일 대응임을 알 수 있다.[6] 여기선 이해를 돕기 위해 '크기'라고 썼지만 실제로는 농도(cardinality)라고 흔히 표현한다.[7] 책에 따라서는 [math(\text{card}\left(X\right))], [math(\text{card}\left(Y\right))]로 표기하기도 한다.[8] 즉 S의 원소 <M>은, M에 <M>을 입력값으로 넣으면 영원히 안 멈추거나 no를 뱉는다.[9] 근대 수학에서도 그러한 경향이 있었지만 현대 수학은 대부분, 아니 사실상 전부라고 해도 과언이 아닐 정도로 어떤 특정한 성질을 만족하는 집합들과 그 성질을 보존하는 사상(함수)의 성질들을 연구하는 데에 집중되어 있다. 수학에서 객체와 그 성질에 관한 분석은 대부분 완수되었고, 이젠 카테고라이즈화된 영역들을 집합 단위로 비교 및 연결성을 파악하는 데 힘쓰고 있기 때문이다.[10] 예컨대 대수학의 경우 대수적인 구조를 가진 집합들(군, 환, 체, 모듈, 벡터 공간, 대수 등)의 성질과 연산을 보존하는 사상인 Homomorphism을 연구한다. 또한 위상수학에서는 어떤 특정한 성질을 만족하는 부분집합들을 모아놓고 열린 집합(Open Set)으로 부르며 이들의 성질을 다루고 있으며 특히 연속 사상(Continuous Map)에 의해 어떤 성질들이 보존되는가를 연구한다.[11] 저 희한한 문자는 '알레프'라고 부르며 히브리 문자 중 하나이다. 즉, 자연수 집합의 크기는 '알레프 제로'라고 읽는다.