[include(틀:논리학요]
| 수학기초론 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. 개요
不完全性 定理 / incompleteness theorems모순이 없는 수학 체계에는 반드시 증명할 수 없는 명제가 하나 이상 있다는 정리이다.쿠르트 괴델이 1931년에 발표했다. 19세기 해석학(수학)의 발달 및 비유클리드 기하학의 본격적인 등장으로 촉발된 수학 기초론의 대표적인 성과로서, 현대 논리학의 토대인 동시에 20세기 수학 및 철학, 컴퓨터과학 등 많은 분야에 큰 영향을 미쳤다. 참고로, 이 정리에 자극 받은 앨런 튜링이 본인 방식으로 곧이어 논문을 썼었고, 그 논문에 튜링 머신이란 개념이 등장하게 된다.
다른 학문에서의 결정 불가능성 개념으로 컴퓨터과학에서 앨런 튜링이 증명한 정지 문제, 케네스 애로우가 증명한 경제학의 불가능성 정리, 언어철학에서 뢰벤하임-스콜렘 정리의 함의를 이어 콰인이 제시한 번역 불확정성 논제[1], 그리고 수리논리학에서 타르스키가 증명한 타르스키의 정의 불가능성 정리가 있다.
참고로, 쿠르트 괴델 본인이 1929년에 증명한 완전성 정리와 혼동하지 말 것.
2. 정리
불완전성 정리는 "제1 불완전성 정리"와 "제2 불완전성 정리"라는 두 정리를 아우르는 말이다.제1정리. 페아노 공리계를 포함하는 어떠한 공리계도 무모순인 동시에 완전할 수 없다. 즉 자연수 체계를 포함하는 어떤 체계가 무모순이라면, 그 체계에서는 참이면서도 증명할 수 없는 명제가 적어도 하나 이상 존재한다.
제2정리. 페아노 공리계가 포함된 어떠한 공리계가 무모순일 경우, 그 공리계로부터 그 공리계 자신의 무모순성을 도출할 수 없다.
페아노 공리계란 우리가 사용하고 있는 자연수에 관한 공리를 말한다. [math(1+1=2)]라는 것도 이를 통해 정의된 것이다. 그런데 이 공리를 포함하는 체계가 모순이 없다면, 참인데 증명할 수 없는 명제가 존재한다는 것이다. 제2정리. 페아노 공리계가 포함된 어떠한 공리계가 무모순일 경우, 그 공리계로부터 그 공리계 자신의 무모순성을 도출할 수 없다.
2.1. 주요 개념
수리논리학에서 쓰이는 "참", "증명가능성", "귀결" 등의 개념은 자칫 오해하기 쉽다. 오해를 방지하기 위하여 관련 개념을 약술하자면 다음과 같다:"불완전성 정리"에서 말하는 "완전성(completeness)"이란 "건전성(soundness)"과 대비되는 성질이다.[2] 임의의 형식 체계 [math(P)], 명제 집합 [math(\Gamma)], 그리고 명제 [math(\phi)]에 관하여 이들 개념은 다음과 같이 정의될 수 있다:
* [math(P)]의 건전성: [math(P)]에서 [math(\Gamma)]로부터 [math(\phi)]가 증명가능하다면, [math(P)]에서 [math(\phi)]는 [math(\Gamma)]의 논리적 귀결이다.
* [math(P)]가 건전하면 [math(P)]는 무모순적이다.
* [math(P)]의 완전성: [math(P)]에서 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이라면, [math(\phi)]가 [math(P)]에서 타당하다면, [math(P)]에서 명제 [math(\phi)]는 [math(\Gamma)]로부터 증명가능하다.
이때 "증명가능성"과 "논리적 귀결"은 각각 다음과 같이 정의된다:* [math(P)]가 건전하면 [math(P)]는 무모순적이다.
* [math(P)]의 완전성: [math(P)]에서 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이라면, [math(\phi)]가 [math(P)]에서 타당하다면, [math(P)]에서 명제 [math(\phi)]는 [math(\Gamma)]로부터 증명가능하다.
* [math(P)]에서 [math(\phi)]는 [math(\Gamma)]로부터 증명가능하다 [math(\Leftrightarrow)] [math(\Gamma)]의 원소들 및 [math(P)]의 공리들에 [math(P)]의 도출 규칙을 유한번 적용하여 [math(\phi)]를 얻을 수 있다.
* [math(P)]에서 [math(\phi)]는 [math(\Gamma)]의 논리적 귀결이다 [math(\Leftrightarrow)] [math(P)]에서 [math(\Gamma)]의 모든 원소들이 참인 경우 [math(\phi)]도 반드시 참이다 [math(\Leftrightarrow)] [math(\Gamma)]의 모든 원소들이 참인 임의의 모형에서 [math(\phi)]는 참이다.
명제 논리는 건전하며 완전하다. 더욱이 명제 논리의 경우 임의의 [math(\Gamma)]와 [math(\phi)]에 대하여 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결인지 여부를 유한번 단계 내에 판단할 수 있게끔 해주는 절차가 있으므로 결정가능하다.* [math(P)]에서 [math(\phi)]는 [math(\Gamma)]의 논리적 귀결이다 [math(\Leftrightarrow)] [math(P)]에서 [math(\Gamma)]의 모든 원소들이 참인 경우 [math(\phi)]도 반드시 참이다 [math(\Leftrightarrow)] [math(\Gamma)]의 모든 원소들이 참인 임의의 모형에서 [math(\phi)]는 참이다.
1차 술어 논리는 건전한 동시에 완전하지만, 결정가능하지는 않다. 따라서 만약 [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이라면 그 사실은 유한 번 단계 내에 판단할 수 있지만, [math(\phi)]가 [math(\Gamma)]의 논리적 귀결이 아니라면 그럴 수 없다. 1차 술어 논리의 완전성 또한 괴델이 증명한 것이다.
자연수 산술을 가능케 하는 페아노 공리계를 포함하는 형식 체계는 1차 논리보다 강력하다. 괴델의 불완전성 정리는 이런 논리 체계가 완전성을 띠지 않는다는 점을 보여주는 것이다. 곧 설령 참이라 한들 그에 대한 증명도, 그 부정에 대한 증명도 불가능한 문장들이 있다는 것이다. 밑에서도 나오겠지만 연속체 가설을 비롯한 몇몇 명제들이 바로 그 사례다.
3. 쉬운 증명
괴델이 제시한 원래의 증명 외에도, 불완전성 정리를 증명하는 방법은 여러가지가 있다. 튜링의 방법도 있고, 무한집합을 통해 증명하는 방법도 있다. 이 문단은 괴델의 원래 증명을 4문단보다 훨씬 쉽게 설명한다. 물론 그만큼 논리적 엄밀성은 떨어질 것이나, 그럼에도 비전공자들에겐 이 문단의 설명이 나을 것이다.1. 자기 지시문
'자기 지시문'이란, 말 그대로 자기 자신을 가리키는 문장을 말한다. 예를 들어 "이 문장은 한국어로 쓰여졌다."는 문장은, 자기 자신을 가리키고, 나아가 실제로 한국어로 쓰여졌으므로, '참'인 자기 지시문이다. 또 "이 문장은 영어로 쓰여졌다."는 문장은, 자기 지시문이기는 하나, 영어로 쓰여진건 아니므로, '거짓'인 자기 지시문이다. 반면 "괴델은 천재다."라는 문장은, 문장 자기 자신을 가리키는 것이 아닌, 외부 대상 '괴델'을 가리키므로, 참-거짓을 떠나 애초에 자기 지시문이 아니다.
2. 거짓말쟁이의 역설
'자기 지시문' 가운데 특별한 것이 있다.
명제: 이 문장은 거짓이다.
1. 이 명제가 사실이라고 한다면 이 명제가 주장하고 있는 '이 문장은 거짓이다'라는 것은 사실이다.
1. 즉 '이 문장이 거짓이다'라는 게 사실이므로, '이 명제는 거짓'이라는 결론이 된다. 이는 이 결론을 이끌어낸 '이 명제가 사실이다'라는 전제와 모순된다.
1. 이 명제가 거짓이라고 한다면 이 명제가 주장하고 있는 '이 문장은 거짓이다'라는 것은 거짓이다.
1. 즉 '이 문장은 거짓이다'라는 게 거짓이므로, '이 명제는 사실'이라는 결론이 된다. 이는 이 결론을 이끌어낸 '이 명제가 거짓이다'라는 전제와 모순된다.
괴델이 원래의 증명 논문에서 사용한 핵심 문장이, 본질적으론 위 문장과 같은 성격을 가진다.1. 이 명제가 사실이라고 한다면 이 명제가 주장하고 있는 '이 문장은 거짓이다'라는 것은 사실이다.
1. 즉 '이 문장이 거짓이다'라는 게 사실이므로, '이 명제는 거짓'이라는 결론이 된다. 이는 이 결론을 이끌어낸 '이 명제가 사실이다'라는 전제와 모순된다.
1. 이 명제가 거짓이라고 한다면 이 명제가 주장하고 있는 '이 문장은 거짓이다'라는 것은 거짓이다.
1. 즉 '이 문장은 거짓이다'라는 게 거짓이므로, '이 명제는 사실'이라는 결론이 된다. 이는 이 결론을 이끌어낸 '이 명제가 거짓이다'라는 전제와 모순된다.
3.
다음의 문장이 존재한다고 하자.
A문장 : 이 문장은 형식 체계 B에서 증명 불가능하다.[3]
이제 형식 체계 B가 무모순이라 가정하자. 즉 어떤 경우에도 B를 바탕으로 논리 전개를 할 때, 모순이 도출하지 않는다고 가정하자. 이때, 이 가정하에서 A문장은 참인가, 거짓인가? 나아가 A와 ~A[4]는 각각 증명 가능한가?4. A문장은 참인가, 거짓인가?
거짓이라 가정하자. 그렇다면 A는 B에서 증명 가능하다. 그렇다면 A는 참이다. 왜냐하면 '이 문장은 형식 체계 B에서 증명 불가능하다.'는 것이 증명 가능하다는 의미이기 때문이다. 즉 A가 거짓이라면, A는 참이다. 그러므로 A는 거짓일 수 없고, 따라서 A는 참이다. 그런데 A가 참이라면, A의 의미상 A는 증명 불가능하다. 그렇다면 형식 체계 B에서 참이지만 증명 불가능한 문장이 존재하고, 그것이 바로 A이다.
5. ~A는 증명 가능한가?
~A는 'A가 형식 체계 B에서 증명 가능하다.'이다. 따라서 ~A가 증명 가능하다는 말의 의미는, 'A가 형식 체계 B에서 증명 가능하다.'는 것이 증명 가능하다는 것이다. 이제 ~A가 증명 가능하다고 가정하자. 그렇다면 ~A가 증명가능하다는 말의 의미상, A가 증명 가능하다. 그렇다면 ~A도 증명 가능, A도 증명 가능, 즉 'A and ~A'가 증명 가능하다. 이는 우리가 3에서 형식 체계 B가 무모순이라 가정한 것에 위배된다. 그렇다면 ~A는 형식 체계 B에서 증명 불가능하다.
6. 제1 불완전성 정리
4와 5를 정리하자면, A는 증명 불가능하고, ~A도 증명 불가능하다. 그렇다면 A와 ~A의 참-거짓을 결정할 수 없다. 이런 문장을 '결정 불가능한 문장'이라 부른다. 요약하자면 무모순인 어떤 형식 체계가 있을 때, 그 형식 체계에선 참이지만 결정 불가능한 문장이 존재한다. 이것이 괴델의 제1 불완전성 정리이다.
7. 제2 불완전성 정리
다음의 문장이 존재한다고 하자.
C문장 : 형식 체계 B가 무모순이라면, A이다.
A의 의미를 고려할 때, C의 의미는 다음과 같다. 즉 '형식 체계 B가 무모순이라면, 이 문장은 형식 체계 B에서 증명 불가능하다.' 그러므로 기실 C는 의미상 3과 4를 아울러 합한 결론인 것으로, 우리가 이미 논의한 것이다. 즉 우리는 6에서 무모순인 어떤 형식 체계가 있을 때, 그 형식 체계에선 참이지만 결정 불가능한 문장이 존재한다는 제1 불완전성 정리를 증명했다. 따라서 C문장은 증명 가능하다. 이제 C를 두 부분으로 나누어 생각하자. 앞부분(전건)이 '형식 체계 B가 무모순이라면'이고, 뒷부분(후건)이 'A이다'이다. 그러면 C의 전건 즉 '형식 체계 B가 무모순이다'가 증명 가능한가? 일단 증명 가능하다고 가정하자. 그런데 C문장은 증명 가능하다고 앞서 결론내렸으므로, C의 후건도 증명 가능해야 한다. 허나 C의 후건 즉 'A이다'는 증명 불가능하다는 것을 위에서 확인했다. 그렇다면 C의 전건 역시 증명 불가능하다. 따라서 어떤 형식 체계 B가 있을 때, 그 형식 체계 내부의 논리만으로 B가 무모순이라는 점은 증명 불가능하다. 이것이 괴델의 제2 불완전성 정리이다.
4. 증명 아이디어
아래 증명 아이디어는 어니스트 네이글과 제임스 뉴먼의 고전적인 대중서, 『괴델의 증명』에서 따온 것이다.4.1. 제1정리
제1불완전성 정리 증명의 실질적인 첫 단계는 임의의 식을 자연수로 번역하는 절차를 만드는 것이다.[5] 그 방식은 다양하나, 요체는 모든 식 각각에 고유한 자연수를 부여하는 것이다. 이처럼 그 식과 일대일로 대응하는 자연수를 그 식의 괴델수(Godel number)라고 부른다.산술식 [math(1+0=1)]를 예로 들어보자. 이 식에 등장하는 기호의 유형은 '[math(1)]', '[math(+)]', '[math(0)]', '[math(=)]'로 네 가지다. 이때 각 기호의 유형마다 고유한 자연수를 부여하자. 그 예는 다음과 같다.[6]
| 기호 유형 | 괴델수 |
| '[math(0)]' | 3 |
| '[math(1)]' | 4 |
| '[math(+)]' | 5 |
| '[math(=)]' | 6 |
[math(\displaystyle\text{괴델 수}=\prod^n_{k=1}P_k^{(k\text{번째로 오는 기호 유형에 상응하는 괴델수})}\quad(\text{단, }P_k\text{는 }k\text{번째 소수}))]
예컨대 [math(1+0=1)]의 첫 자리에 나타나는 '1'은 [math(2^4=16)]으로 번역가능하다. 그리고 이렇게 번역된 각 자연수들을 다 곱함으로써 식 전체를 그 괴델수로 번역할 수 있다. 이를테면 [math(1+0=1)]의 괴델수는 [math(2^4\times3^5\times5^3\times7^6\times11^4=837134518374000)]이 된다.
이처럼 임의의 식에 상응하는 괴델수를 계산해낼 수 있다. 그리고 똑같은 원리에 의거하여 여러 식들의 나열, 이를테면 증명에 해당하는 괴델수 또한 계산하는 것이 가능하다.
이를 토대로 다음과 같은 개념을 정의하자:
- 식 '[math(Dem(x, y))]': '괴델수가 [math(y)]인 명제의 증명은 괴델수가 [math(x)]이다'
- 예. '[math(\exists x Dem(x, y))]':' '괴델수가 [math(y)]인 명제의 증명이 존재한다'
- 함수 [math(sub(n, k, n))]: 괴델수가 [math(n)]인 식의 변항 중 괴델수가 [math(k)]인 변항에 ([math(n)]을 나타내는 기호인) '[math(n)]'을 대입해서 얻은 식의 괴델수[주의]
- 예. 식 '[math(\exists x (x=y))]'의 괴델수가 [math(m)]이라고 하고, '[math(y)]'의 괴델수가[math(j)]라고 하자. [math(sub(m, j, m))]는 '[math(\exists x (x=y))]'에서 '[math(y)]'를 '[math(m)]'으로 교체한 식의 괴델수다.[주의]
변항 '[math(y)]'의 괴델수를 17이라고 가정하라. 이때 식 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'의 의미는 정의상 '괴델수가 [math(sub(y, 17, y))]인 식의 증명은 존재하지 않는다'가 될 것이다.[주의] 이때 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'의 괴델수는 [math(n)]이라 하자. 그렇다면 [math(n)]을 나타내는 기호 '[math(n)]'을 포함하는 다음 식 [math(G)] 또한 생각할 수 있다.
- [math(G)]: '[math(\neg ∃xDem(x, sub(n, 17, n)))]'
- 의미: '괴델수가 [math(sub(n, 17, n))]인 식의 증명은 존재하지 않는다'
이때 [math(G)]의 괴델수를 [math(g)]라고 하자. 그런데 [math(g = sub(n, 17, n))]이다. 왜냐면 가정상 괴델수가 [math(n)]인 식은 '[math(\neg ∃xDem(x, sub(y, 17, y)))]'인데, 정의상 [math(sub(n, 17, n))]은 이 식에서 '[math(y)]'를 '[math(n)]'으로 대체한 식의 괴델수이고, '[math(y)]'를 '[math(n)]'으로 대체한 바로 그 식이 [math(G)]이기 때문이다. 그 [math(G)]의 괴델수가 [math(g)]이므로, 곧 [math(g)]는 [math(sub(n, 17, n))]와 같다.
그러므로 [math(G)]의 의미는 '괴델수가 [math(g)]인 식의 증명은 존재하지 않는다'라고도 볼 수 있다. 그런데 괴델수가 [math(g)]인 식은 바로 [math(G)]다. 따라서 [math(G)]의 의미는 '[math(G)]의 증명은 존재하지 않는다'는 것이다. 먼저 [math(G)]의 증명이 존재한다고 가정해보자. 그러면 명제 [math(G)]는 거짓인데, 이로부터 [math(G)]의 부정의 증명 또한 있음을 보일 수 있다. 하지만 이는 무모순성을 위반한다.[10] 역으로 명제 [math(G)]의 부정에 대한 증명이 존재한다고 가정할 경우에도 무모순성이 위반된다.[11]
즉 대우를 취할 경우, 주어진 증명 체계가 무모순적이라면 [math(G)]와 그 부정 둘 중 어느 것도 증명할 수 없으므로 불완전하다는 점이 도출된다. 그리고 [math(G)]의 의미상 [math(G)]는 참이 된다. 따라서 참이지만 증명할 수 없는 명제가 있다.
4.2. 제2정리
모순적인 공리계로부터는 어떠한 명제든지 증명할 수 있으므로, 무모순적인 공리계는 증명불가능한 명제가 있는 공리계다. 따라서 '페아노 공리계는 무모순적이다'라는 문장은 괴델수 번역 등을 통해 페아노 공리계 안에서[12] 다음과 같은 형태로 기술될 수 있다.- '[math(\exists y \neg \exists x Dem(x,y))]'
- 의미: '그 증명에 해당하는 괴델수 [math(x)]가 없는 식의 괴델수 [math(y)]가 존재한다.'
5. 반응 및 영향
5.1. 수학 및 그 사례
현대의 표준적 집합론인 ZFC 공리계는 페아노 공리계의 모형을 제공할 뿐 아니라 뭇 수 체계를 포괄한다는 점에서 표준 수학의 '기초'가 된다. 그런데 페아노 공리계를 해석할 수 있다는 그 점으로 인해 ZFC 또한 불완전성 정리에서 피해갈 수 없다. 결국 ZFC를 기초로 삼는 한 참임에도 불구하고 증명할 수 없는 명제가 존재하며, ZFC의 무모순성은 ZFC에서 증명할 수 없다.관건은 수학적으로 충분히 "흥미로운" 명제 가운데서도 하필이면 증명불가능한 명제가 있느냐는 점. 공교롭게도 힐베르트의 23가지 문제 중 하나로도 꼽혔던 연속체 가설이 ZFC 공리계와 무모순이라는 것을 쿠르트 괴델이, 해당 가설의 부정이 ZFC와 무모순이라는 것을 폴 코언이 증명함으로써 불완전성 정리가 적용되는 흥미로운 사례가 입증되었다. 불행인지 다행인지 힐베르트는 연속체 가설이 무모순이라는 것만 보고 죽었지만...[13]
아래는 그 대표적인 사례들이다.
- 연속체 가설[15]: 모든 무한집합의 원소수(기수)는 [math( \aleph_n )]꼴로 표현 할 수 있다 여기서 [math( 2 ^{\aleph_0} = \aleph_1 )] 이 성립하겠느냐는 것이 연속체 가설이고, 일반화된 것은 [math( 2^{\aleph_N} = \aleph_{N+1} )] 이 성립하지 않을까 하는 일반연속체가설. 좀 더 자세한 것은 연속체 가설과 초한기수 문서 참조.
- Word problem for groups[16]
5.2. 계산 이론
계산 이론에 의해 불완전성 정리는 자연수론을 포함한 임의의 공리계에 대해서 다음과 같은 함축을 갖는다:- 그 공리계 내부의 자료만으론 기계적인 유한한 절차로 참, 거짓을 결정/증명할 수 없는 명제가 반드시 있다. 그렇지 않으면 그 공리계에는 모순이 있다.
핵심은 수학의 경우에는 무모순하다는 것에 대한 증명을 그 체계 자체에서 증명될 수 없다는 것이다. 그보다 상위 체계를 동원한다면 가능할 수 있는 것. 게르하르트 겐첸은 유한한 기계적 절차가 아닌 초한귀납법이라는 방법을 동원해서 수체계의 무모순성 증명을 증명하기도 했다.
증명과정 중 사용한 원시 재귀함수는 컴퓨터과학을 탄생시키는 계기가 되기도 하였다. 하지만, 괴델은 이것을 실제 계산기와 같은 기계 쪽에 응용할 생각은 하지 않았고 후에 앨런 튜링이 원시 재귀함수를 보다 기계친화적인 튜링 머신으로 바꾸어 표현하면서 컴퓨터의 아버지라는 이름은 튜링이 가져가게 되었다.
그리고 위 조건을 만족시키는 다양한 기계적인 유한한 절차들마다[20] 그에 해당하는 튜링 머신이 있으며 그 역 또한 성립함이 증명되었다. 이를 보다 확장하여 모든 계산가능한 함수마다 그에 상응하는 튜링 머신이 존재한다는 주장이 유명한 처치-튜링 명제이다.[21]
5.3. 철학
수학 기초론에 관한 지난 수십 년 동안의 연구 성과는 비단 그 자체로 흥미로울 뿐 아니라, 수학의 본성 같은 전통적인 철학적 문제들에 시사하는 바에 있어서도 흥미롭다고 봅니다.[22]
쿠르트 괴델, 1951년 Gibbs 강연 '수학 기초론의 몇몇 기본적 정리들과 그 함축' 中
불완전성 정리에 대한 잘못된 해석 한 가지는 "참도 거짓도 아닌 수학적 명제가 있다"는 것이 불완전성 정리를 통해 증명되었다는 것이다. 이 해석이 잘못된 이유는 참임에도 불구하고 증명이 불가능한 명제 [math(G)]가 있다는 것이 바로 제1정리이기 때문이다. 논리학에서 완전성이란 어떤 형식체계의 의미론적 귀결인 명제가 구문론적 귀결인 속성을 지칭한다. 괴델의 불완전성 정리는 술어 논리가 이 완전성을 만족시키지 못함을 보일 뿐이다. 이 완전성의 정의에는 위와 같은 해석을 허용할만한 서술이 존재하지 않는다. 참도 거짓도 아닌 명제, 참이면서 동시에 거짓인 명제 등을 인정하는 비고전 논리학이 존재하는 것은 분명하지만, 이는 불완전성 정리로부터 곧장 따라나오는 것이 결코 아니다.쿠르트 괴델, 1951년 Gibbs 강연 '수학 기초론의 몇몇 기본적 정리들과 그 함축' 中
수학철학에서 쿠르트 괴델 본인은 오히려 플라톤의 견해를 그대로 받아들였다고 해도 과언이 아닐 정도의 강경한 실재론을 옹호했다. 즉 우리가 원리적으로 알 수 있건 없건 수학적 명제의 참거짓은 객관적으로 존재한다는 것. 괴델은 오히려 1951년 Gibbs 강연에서 (특정 조건이 만족된다는 가정 하에서) 불완전성 정리는 오히려 수학적 참이 객관적이라는 근거가 된다는 논변을 제안하기도 했다.
제2불완전성 정리가 확실히 직격한 수학 기초론은 다비트 힐베르트의 이른바 '힐베르트 프로그램'이다. 왜냐면 힐베르트 프로그램의 핵심은 형식화된 수학 이론의 무모순성을 유한한 절차에 의거하여 증명하려는데 있었기 때문이다. 괴델은 힐베르트학파 수학자들의 맹렬한 반론을 예상하여 이에 대응하기 위한 후속 논문을 불완전성 정리를 발표하는 논문에서 이미 예고했으나, 힐베르트 및 그 제자들은 불완전성 정리에 아무런 반론을 제기하지 않았으며, 이 때문에 예고했던 후속 논문은 나오지 않았다. 힐베르트는 그 대신 '유한한 절차'에 대한 제한조건을 일부 포기하고 초한귀납법을 받아들임으로써 불완전성 정리의 장벽을 우회하려고 시도했으며, 이러한 무모순성 증명은 힐베르트의 조수였던 게르하르트 겐첸에 의해 달성되었다. 힐베르트 학파 측에서 '유한한 절차'라는 말을 엄밀하게 정의한 적이 없기에 겐첸의 무모순성 증명이 갖는 의의에 대해서는 철학사적 논쟁이 분분하지만, 당대의 많은 논리학자들은 초한귀납법을 통한 증명으로는 힐베르트 프로그램의 철학적 목표를 달성할 수 없다고 진단했다.
고틀로프 프레게와 버트런드 러셀, 그리고 논리 실증주의자들이 개진했던 논리주의 프로그램 또한 불완전성 정리 등장 이후 대대적인 수정이 불가피하게 되었다. 루돌프 카르납은 괴델 본인이 제안한 철학적 비판에 맞서 1930년대 이후 많은 이론적 수정을 가해야했으며, 1980년대 이후 진행되는 신논리주의 프로그램은 아예 고전적 논리주의의 여러 전제들을 포기하고 진행중이다.
심리철학에서 불완전성 정리가 언급되는 유명한 떡밥은 다음과 같다:
불완전성 정리에 따르면 기계적인 절차에 근거하여 참을 보일 수 없는 명제가 있다. 그런데 우리 인간은 그 참을 보일 수 있다. 따라서 인간의 마음은 계산 기계가 아니다.
괴델 자신 또한 그 가능성을 지나가면서 언급한 적은 있으나, 현대에도 이런 떡밥을 꾸준히 대중적으로 미는 학자로는 로저 펜로즈가 있다.6. 대중적 인식
- 당시에는 증명이 난해하다기보다는, 논리체계를 '이용하는' 수학이 그런 논리체계 자체를 수학적 대상으로 환원하여 연구한다는 부분을 잘 이해하지 못하여 대부분의 비수학자들은 그저 논리와 이성으로 이 세상을 완전히 설명할 수는 없다는 정도로 받아들일 수도 있을 것 같다, 는 식으로 이해했고, 지금도 비전공자들은 막연히 그 정도로만 이해한다.[23]
- 몇몇 철학자들은 '우리가 진리에 결코 도달할 수 없다'는 뜻으로 해석하기도 한다. 미셸 드 몽테뉴, 프리드리히 니체가 했던 주장의 개정판인 셈인데, 물론 잘못된 해석이다. 수학의 위치를 생각해 보았을 때 철학적으로 중요한 기획 하나가 실패를 겪었다는 것은 사실이지만, 그 이외의 영역에서까지 이를 확장하는 것은 주의해야 한다. 대부분 이런 주장들은, 불완전성 정리를 제대로 이해해서 확장했다기보다는 그냥 좋은 소재(같은 예로는 상대성 이론, 양자역학)를 물었을 뿐이다. 불완전성 정리를 이용해서 개드립을 치던 사람들은 나중에 앨런 소칼에게 걸려서 박살이 났다. 원래 진리에 결코 도달할 수 없다는 주장의 기원은 소피스트가 자기네끼리 투닥투닥하던 시절까지 거슬러 올라간다. 진리에 결코 도달할 수 없다는 것이 아니라 진짜 진리에 도달한다해도 그게 진리가 맞는지 증명할 수 없을 수도 있다고 이해하면 빠를 것이다.
- 문학에서는 어쨌거나 뜻의 난해함과 불완전성이라는 단어가 주는 포스트모던적인 강렬함 덕분에 억지를 진실로 진실을 억지로도 재정리 할 수 있는 논리체계라고 오해를 받는데, 괴델의 정리는 '참으로 증명된 정리'의 존재를 부정하지도 않고, 참인 명제를 거짓이라고 선언하지도 않는다.
- 조금 더 일찍 나온 불확정성 원리가 주는, 세상은 확률론적으로 이루어져 '참과 동시에 거짓이다'라는 식의 오해가 쓰기 더 편리하기 때문에 더 이상은 등장하지 않을 듯하다.
- 사실 오일러-가우스 시절까지의 수학에서는 단순히 주어진 수식의 연산 정도만이 관심사였고, 해당 '체계' 및 '시스템 자체'의 엄밀함에 신경쓰기 시작한 것은 코시라는 수학자가 등장한 이후부터였다.[24] 희한하게도 수학의 전체적인 시스템을 엄밀하게 증명하는 과정을 보면 뭔가가 안 된다는 결론들이 많았다. 갈루아는 5차 이상의 방정식의 해를 구하는 공식은 없다는 결론을 내었고, 위상수학에서는 조르당-쇤플리스 정리[25]가 3차원 이상의 공간에서는 성립되지 않음이 밝혀졌다. 측도론에서는 3차원 이상 실수공간의 임의의 부분집합의 넓이를 구하는 함수는 존재하지 않음[26]을 보이고, 더해서[27], 바나흐-타르스키 역설에서는 선택공리[28]를 이용해 순수하게 집합의 분할과 공간이동[29] 만의 방법을 사용해서 3차원 실수공간의 서로 다른 부피를 가진 공 2개의 조각들이 모두 서로 대응함을 보여준다.[30] 위에서 언급한 wording problem도 그 한 예시로 볼 수 있겠다. 그래도 대수학에서의 다양한 분류(classification) 문제들이 풀렸고 측도론을 기반으로 해석학이 함수해석학 등 세부 분야를 통하여 눈부신 발전을 이루어 냈으며 위상수학 등을 통하여 호모토피, 호몰로지, 더 나아가 대수기하학 등이 융성한 것을 보면 이러한 방법론이 꽤 유용하면서도 아직 할 일이 많다는
즉 돈줄이 아직 안 끊겼다는것을 짐작할 수 있을 것이다. - 괴델의 불완전성 정리 역시 이 연장선상에서 수학 그 자체의 불완전성을 보인 것이다. 현대수학은 매우 확고한 기초를 가진듯 보이지만, 사실 내부사정을 조금 들여다보면 이래저래 '의미적'으로도 위의 바나흐-타르스키 역설 같은 여러 가지 역설이 존재하기 때문에 공격받는 부분이 많고, 그 외에도 철학적으로 비구성적 오브젝트를 허용한데 대한 입장차이 등으로 인하여 공격받는 부분이 많아 '물 바깥에서 보기엔 우아하고 아름답지만, 안에서는 열심히 다리를 허우적대는 백조'와 같은 모양새를 띠고 있다. 괜히 러셀이 '수학의 원리'같은 책을 낸 것이 아니다.
- 골드바흐 추측과 얽혀서 "어쩌면 골드바흐의 추측도 저 "참이면서도 증명할 수 없는 명제"(참 거짓을 증명할 수 없는 문제)가 아닐까?" 하는 것을 써먹은 소설 <사람들이 모두 미쳤다고 말한 외로운 수학 천재 이야기>가 있다. 아직까지 증명도 반증도 안 되니 참으로 간주하는 것. 페르마의 마지막 정리도 증명되기 전에는 비슷한 의심을 하는 사람들이 있었다.
- 읽어보면 좋은 책으로 <괴델, 에셔, 바흐>, <불완전성> 등이 있다. 참고로 <괴델, 에셔, 바흐>는 구판 한국어 번역본의 퀄리티는 악명이 높았지만, 2017년에 나온 개정판은 역자가 바뀌면서 번역의 질이 압도적으로 높아졌다.
[1] 어떤 두 언어가 주어졌을 때 한 언어에서의 일반적인 표현을 다른 언어로 올바르게 번역되었는지를 판정하는 일반적인 방법은 존재하지 않는다는 논제.[2] 비슷한 맥락에서 중요한 성질로 콤팩트성 정리가 있다. 이는 위상수학의 compact 개념을 적용한 것으로, "[math(\phi)]가 명제들의 집합 [math(\Gamma)]의 귀결이면, [math(\Gamma)]의 유한한 부분집합 [math(\Gamma')]이 존재해서 [math(\phi)]가 [math(\Gamma')]의 귀결이다"가 성립한다는 것이다.[3] A문장은 당연히 자기 지시문이며, 상술하였듯 거짓말쟁이의 역설과도 긴밀한 연관이 있다.[4] A의 부정[5] 나중에 앨런 튜링도 이 방법을 차용하여 튜링 머신을 만들었다.[6] 서로 다른 기호들에는 다른 양의 정수가 부여되면 되니까 산술명제들과 그것들을 이루는 기호들의 집합에서 양의 정수로 가는 단사함수(injection)로 이해해도 상관 없다. 또한 굳이 괴델이 보인 방식만 있는건 아니고 다른 방식들을 얼마든지 정할 수 있다. 위키백과에서는 기초적인 10개의 '불변부호', 즉 '('나 '0', 's' 같은 것들에 미리 1~10을 할당하고, 나머지 경우에는 변수마다 종류를 나눠 [math(n)]번째 종류의 [math(k)]번째 변수에 해당하는 괴델수를 [math((10\text{이후의 }k\text{번째 소수})^n)]으로 제시했다. 이렇게 하면 모든 기호들마다 동일한 수가 겹칠 일이 없다. 영어가 된다면 직접 영어 위키백과에서 괴델 수 항목을 읽어봐도 도움이 된다.[주의] [math(n)]을 나타내는 기호를 '[math(n)]'라고 적기하는 것은 엄밀하지 않다. 변수 [math(n)]을 나타내는 기호는 변항이 아닌 [math(n)]을 나타내는 숫자일 것이기 때문이다. 마찬가지로 '[math(Dem(x, sub(n, 17, n)))]'라는 표현은 엄밀하지 않다. [math(sub(y, 17, y))]는 함수값이며, [math(Dem)]의 두번째 변항은 기호가 되어야 하기 때문이다.[주의] [주의] [10] 그냥 모순을 받아들이면 안 되나 싶을 수도 있지만 모순을 받아들이는 순간 모든 게 참으로 귀결되는 쓸모없는 공리계가 되어버린다. 이를 폭발 원리(Principle of Explosion)라고 하는데, 직관주의 논리체계에서는 추론규칙으로 사용하며, 스탠다드 논리체계에서는 다른 공리들에 의해 연역된다. 이 논리학 법칙에 대해 자세히 알고 싶다면 위키백과 영문판 참조. 나무위키의 명제 논리 문서에도 간략한 설명과 증명이 실려 있다.[11] 괴델의 최초의 증명에서는 [math(\neg G)]의 부정으로부터 ω-모순성, 즉 산술을 해석하는 이론 [math(T)] 안에 자연수에 대한 논리식 [math(P)]가 있을 때, [math(T)]로부터 논리식 [math(P(0),\,P(1),\,P(2),\dots)] 라는 식으로 [math(P(n))]의 성립을 모두 증명가능한 동시에 [math(\exists n:\neg P(n))]도 증명가능하다는 것을 보였다. 보다 일반적인 모순성을 도출시킨 것은 존 버클리 로써(John Barkley Rosser)이며, 이때문에 제1불완전성 정리는 괴델-로써 정리라고도 한다.[12] 보다 엄밀하게 말하자면 페아노 공리계를 포괄할 수 있는 증명 체계 하에서[13] 어떻게 보면 이렇게라도 밝혀지는 것 자체가 다행인 게, '이 문제는 증명 불가능하다'라는 명제가 증명 불가능할 수도 있다.[14] Zermelo-Fraenkel Set Theory + Axiom of Choice[15] 선택 공리와 연속체 가설이 증명 불가능하다는 것은 모두 폴 코언(Paul Cohen)이 증명했고 반증이 불가능하다는 것은 괴델이 증명했다.[16] 공리계에 관한 내용은 아니지만, Undecidability 에 관한 문제라, 불완전성 정리와 가까운 문제라 볼 수 있다. 유한집합인 임의의 알파벳 A 의 문자로 생성된 group G 가 있다고 하자. 역시 A 의 문자들로 구성된 임의의 word 2개를 만들어, 그것이 G 에서 같은 원소인지 아닌지 구분하는 알고리듬이 존재하는가 하는 문제인데, Higman 에 의하여 불가능하다고 증명되었다.[17] 러셀과 수학 원리를 공동 집필한 앨프리드 노스 화이트헤드가 아니라 그 조카인 존 헨리 콘스턴틴 화이트헤드다.[18] ZFC 에서 증명도 반증도 불가능하다. ZFC에 V=L(이 역시 괴델이 제시한것으로, 괴델 공리라고도 불린다.) 공리를 추가하면 free 가 맞고, MA(Martin's axiom) 와 연속체가설의 부정을 추가하면 free 가 아니다.[19] 불완전성 정리를 증명하는 방법 중에 정지 문제로 환원하여 증명하는 방법도 존재한다.[20] μ-연산자가 추가된 class of recursive functions, λ-대수, unlimited register machine(URM), while-programming 등과 같은 여러 가지 다른 공리계들이 존재한다.[21] 알고리즘이 수학적 혹은 논리적으로 명확히 정의된 개념이 아니라서 이 공리체계들이 모든 알고리즘을 포함하는지는 증명 불가능하다. Church's thesis는 사실 수학보다 철학이나 물리학, 인공지능 분야에서 '인간의 사고를 알고리즘으로 표현이 가능한가'와 같은 문제와 관련이 깊다.(사실 집합론과 카테고리 이론 정도를 제외한 대부분의 수리논리학 분야는 일반적으로 대학교 수학과에서 다루는 내용과는 큰 관련이 없다.)[22] Research in the foundations of mathematics during the past few decades has produced some results which seem to me of interest, not only in themselves, but also with regard to their implications for the traditional philosophical problems about the nature of mathematics.[23] 그러나, 사실 그렇게 난해하지만은 않으며, 이해하기 위해 필요한 사전지식도 그나마 적은 편이다. 실질적으로 가장 어려운 내용은 산술의 기본정리이다. 실제로, 복잡한 정도로만 따지자면 완전성 정리가 더 복잡하다. 관련학과를 들어가면 대학원도 아니고 학부 때 수리논리를 택하면 배울 수 있다. 사실, 수리논리 전공에서 불완전성 정리는 입문정도에 해당한다. 외국대학교들에서 쓰는 논리학 교재들에서는 거의 끄트머리에 나오기는 하지만…[24] 그래서, 오일러 이후로 수학은 끝난 줄 알았는데 가우스가 등장했고, 오일러-가우스 이후로 수학이 끝난 줄 알았는데 코시가 등장했다라는 말도 있다.[25] 간단하게 말하자면 닫힌 곡선에서는 안과 밖이 구분된다고 하는 직관적으로는 너무 자명해 보이는 정리이다. 다만 프랙탈 곡선까지 등장해버리면 골치가 아프기 때문에 실제 증명에는 대수적 위상수학을 동원해야 한다.[26] 바나흐는 n-공간에서 임의의 부분집합에 대해 "부피"(1, 2차원에서는 각각 길이, 넓이와 같다)라는 값을 주는 함수가 만족해야 할 성질을 만족하는 함수를 찾고자 했고, 1,2차원에서 그러한 함수가 존재한다는 것을 발견했지만, 하우스도르프라는 수학자는 3차원 이상에서는 그러한 함수는 존재할 수 없음을 보였다.[27] 대신에 이러한 탐험 중에 얻은 르베그 적분은 리만 적분보다 수렴성 등에 있어서 훨씬 더 좋은 성질을 많이 가지기에 수학자들에게는 나름 해피한 결과를 얻었다고 볼 수 있다.[28] 요약하자면 공집합이 아닌 어떤 집합들을 원소로 갖는 집합족에 대하여, 원소인 집합에서 원소를 하나씩 골라 새로운 집합을 만들 수 있다는 것이다. 언뜻 보면 자명해 보이지만, 사실 무한개의 원소를 가진 무한개의 집합들에서 원소를 하나씩 골라낸다는 것은 아주 자명하지는 않다. 또, 이 공리를 받아들이면 반직관적인 정리들을 여럿 얻게 된다.[29] 물론 공간을 왜곡하는 이동이 아니라 유클리드 운동이다.(즉, 평행이동, 회전, 반사 등 거리를 보존하는 이동이다)[30] 다만 이는 모순은 아닌데, 위에서 말했듯이 모든 집합에 대해서 부피가 정의되지는 않기 때문이다. 그래서 부피를 가지는 집합을 정의하여 그 집합에 대해서만 부피를 다루게 되는데, 바나흐-타르스키 역설에서는 부피를 가지지 못하는 집합으로 분할하는 과정을 거쳤기 때문이다. 그리고 부피를 가지지 못하는 집합들로 분할한다는 점에서 그냥 자르는 것만으로는 불가능하다.