호프스태터가 서문을 쓰고 개정한 '괴델의 증명' 책 내용을 요약해 보았습니다.
이 글은 책 내용을 요약한 것이니 괴델의 불완전성 정리에 대해 더 알고 싶은 부분이 있거나 이해가 되지 않는 부분이 있다면 이 책을 읽어주세요.
I. 머리말
- 괴델의 증명: 진리임에도 불구하고, 증명할 수 없는 수학적 명제가 존재한다
- ‘공리적 방법은 본래부터 어떤 한계를 갖고 있음’을 알려줌
- 수학의 많은 분야가 완벽한 연역 체계에 도달할 수 없음을 시사함
II. 정합성 문제
- 유클리드의 평행선 공리1를 다른 공리로부터 연역할 수 없다는 사실이 19세기에 증명됨
1. 주어진 체계 안에서 어떤 명제의 증명 불가능성을 증명할 수 있다
2. 유클리드 기하학이 유일한 기하학이 아니다
- 유클리드가 채택한 공리와 다르거나 양립할 수 없는 일련의 공리를 사용하여 여러 가지 새로운 기하학 체계를 만들 수 있었기 때문 (비유클리드 기하학의 탄생)
- 기하학을 포함한 모든 수학 분야의 공리가 명백한 자명성에 의해서 확립될 수 있다는 전통적 신념은 근거를 잃게 됨
3. 옛날부터 정통으로 인정되어 온 유클리드 기하학을 성공적으로 수정함으로써 다른 많은 수학적 체계의 공리적 토대를 개정하거나 완성하도록 수학자들을 자극
- 위 사건을 계기로 수학은 훨씬 더 추상적이고, 훨씬 더 형식적인 학문이 됨
- 더 추상적이게 된 까닭
- 공리가 자명한 진술이 아니라 수학자에게 선택의 문제로 받아들여지게 되었기 때문
- 원리적으로 우리가 생각할 수 있는 모든 대상에 대해 수학적 진술을 하게 됨
- 수학적 진술을 할 때 무정의 용어는 관습적 의미는 버리고 단지 공리에 의해 부여된 의미만 갖게 됨으로써, 그 용어들을 사용할 수 있는 영역이 확장됨
- 더 형식적이게 된 까닭
- 수학적 증명의 타당성이 특정한 주제의 본성(자신이 가정한 공준이나 그 공준에서 연역해낸 정리가 옳은가)이 아니라 진술들의 구조(결론이라는 진술이 실제로 최초의 가정에서 필연적으로 연역되는 논리적 귀결인가)에 근거를 두게 되었기 때문
- 수학의 높아진 추상성은 많은 비유클리드 기하학의 발전을 야기함
- 하지만, 비유클리드 기하학에 대해 ‘어떤 수학적 체계의 일련의 공준이 내적 정합성을 갖추고 있다면, 그 일련의 공준에서 연역되는 정리들은 서로 모순될 수 없는가?’라는 문제가 제기됨
- 유클리드 기하학의 공리들은 실재하는 공간에 관한 진술이기 때문에 내적 정합성에 의문이 제기되지 않았음
- 하지만, 비유클리드 기하학의 공리들은 처음부터 실제의 공간에 관해서 명백하게 그른 진술로 간주되었기 때문에 비유클리드 기하학 체계의 내적 정합성 확립에 대한 문제 생김
III. 정합성에 대한 절대적 증명
1. 완벽한 ‘형식적 연역체계(formalized deductive system)’ 만들기 (절대적 증명 위한 힐베르트 프로그램의 첫 단계)
- 연역 체계 속 표현들을 모두 무정의 용어로 바꾸는 것이 필요 (즉, 표현들을 ‘의미 없는 기호’로 간주)
- 이 절차의 목적은 연산 체계(calculus), 즉 ‘기호들의 체계’를 구성하는 것임
- 완벽한 형식적 연역 체계에서 공준과 정리는 ‘기호 열(string)’로 표현되며, 그런 기호 열은 그 체계의 기본 기호들이 연결되며 만들어짐
- 기호들이 더 긴 기호 열로 결합된 형태를 형식문(formula)이라 부름
- 이런 형식문들의 집합을 일컬어 형식 언어(formal language)라고 함
- 이런 방식으로 연역 과정에 ‘공인되지 않은 추론 원리’가 끼어들 위험이 철저히 제거됨
- 상위 수학(meta-mathematics)
- 수학(무의미한 기호들의 체계[형식 언어])에 관하여 언급하는 유의미한 진술
- 수학적 기호와 형식문을 전혀 포함하지 않음 (수학과 명확히 구분해야 함, 서로 다른 것)
2. 상위 수학을 이용한 절대적 증명
- 어떤 연산 체계 속에서 모순되는 두 개의 형식문이 그 연산 체계의 공리들로부터 둘 다 연역될 수 없다는 것을 ‘유한한 단계’를 가진 상위 수학적 절차에 의해 증명하는 것
- 힐베르트는 모든 수학적 연산이 형식문들이 지닌 기하학적 패턴(상위 수학적 절차)으로 밝혀질 수 있으며, 그 기하학적 패턴들은 서로 유한한 구조적 관계를 유지할 것이라고 간주함2
- 따라서, 프로그램 진행에 본질적으로 필요한 조건은 정합성 증명이 오로지 형식문들이 지닌 무한한 구조적 속성이나 형식문들에 적용되는 무한한 연산을 전혀 언급하지 않는 절차만으로 진행되어야 한다는 것
V. 정합성에 대한 절대적 증명의 성공 사례
- 기초 명제 논리학(elementary logic of propositions) 형식적 연역화하기 (『수학원리』 내용)
1. 연산 체계에서 사용될 기호들 정하기
- 변항 기호(variable sign)와 상항 기호(constant sign)로 이루어짐
- 변항 기호에는 문장이 대입될 수 있고, 그래서 문장 변항(sentential variable)이라 부름 (e.g. “p”, “q”, “r”)
- 상항 기호는 문장 연결사(sentential connective)거나 구두점 기호(sign of punctuation)임
- 문장 연결사 e.g. “∼”(부정), “∨”(또는), “⊃”(만일 …라면 …이다)
- 구두점 기호: 두 개의 괄호, 즉 왼쪽 괄호 “(”와 오른쪽 괄호 “)”
2. 구성 규칙 정하기 (어떠한 기호 조합이 형식문으로 인정될 수 있는가를 정하는 규칙)
e.g. “∨”의 양쪽에는 형식문이 놓여야 한다
3. 추리 규칙 정하기 (어떤 형식문으로부터 다른 형식문이 연역될 수 있다는 것을 설명하는 규칙)
1) 대입 규칙: 문장 변항을 포함하고 있는 형식문으로부터 그 변항에 어떤 형식문을 일률적으로 대입하여 다른 형식문을 항상 연역 가능
2) 분리 규칙: “S1”과 “S1⊃S2”의 형식을 가진 두 개의 형식문으로부터 형식문 “S2”를 항상 연역 가능
4. 약간의 형식문을 공리로 선택하기
1) (p∨p)⊃p
2) p⊃(p∨q)
3) (p∨q)⊃(q∨p)
4) (p⊃q)⊃((r∨p)⊃(r∨q))
- 위의 네 공리로부터 형식문 “S”와 그와 모순되는 “∼S”가 둘 다 연역될 수 있다고 가정하자
- “p⊃(∼p⊃q)”는 기초 명제 논리학의 정리 (연역 과정은 생략)
- 정리 속 변항 “p”에 “S”를 대입하고, 분리 규칙을 두 번 적용함으로써 형식문 “q”를 연역할 수 있음
- 가정에 따르면 ‘“q”에 임의의 형식문을 대입함으로써 위의 네 공리로부터 임의의 어떤 형식문이든 연역될 수 있다’는 결론이 도출됨
- 기초 명제 논리학 체계가 정합성을 갖고 있지 않다면 모든 형식문이 정리로 되어버림
- 즉, 기초 명제 논리학의 4개의 공리들로부터 연역될 수 없는 형식문이 적어도 하나는 있다면 정합성을 절대적으로 증명할 수 있음
- 상위 수학적 추론 (아래 조건에 부합하는 속성을 갖지 않는 형식문 발견하기 -> 정합성 절대적 증명)
1. 네 공리가 모두 공유하는 속성
2. 추리 규칙의 적용에 의해서 (공리로부터 정리로) 유전될 수 있는 속성
3. 그 체계의 구성 규칙에 따라 만들어질 수 있는 모든 형식문이 공유하지는 않는 속성 (정리들만 공유)
- 항진성(tautology) (위 세 조건에 부합하는 속성)
- ‘…이거나 …이지 않다’와 같이 필연적으로 옳은 속성을 의미
- 네 공리는 모두 항진성을 가지며, 항진성은 추리 규칙의 적용에 의해 유전되는 속성 (증명은 따로 X)
- 하지만, “p∨q”와 같은 형식문은 항진 형식이 아님 (정합성 절대적 증명 완)
추론 과정 요약
1. 기초 명제 논리학 체계의 모든 공리는 항진 형식이다.
2. 항진성은 유전되는 속성이다.
3. 공리들로부터 올바르게 연역된 모든 형식문 즉 모든 정리도 항진형식이다.
4. 그러므로 항진 형식이 아닌 모든 형식문은 정리가 아니다.
5. 항진 형식이 아닌 형식문(“p∨q”)이 하나 발견되었다.
6. 따라서 이 형식문은 정리가 아니다.
7. 그러나 만일 공리들이 정합성을 갖고 있지 않다면 모든 형식문이 정리이어야 한다.
8. 그러므로 그 공리들은 정합성을 갖고 있다.
- 기초 명제 논리학 체계의 공리들처럼 모든 항진 형식(그 체계 안에서 표현될 수 있는 모든 논리적 진리)을 만들어낼 수 있는 공리들을 완전 체계라고 부름
- 후에 괴델에 의해 밝혀진 것처럼, 어떤 체계는 완전한 공리 체계로 만들 수 없음
VI. 사상 개념과 수학에서의 응용
- 미리 보는 괴델의 불완전성 정리의 결론
- 제1 불완전성 정리: 페아노 공리계3를 포함하는 모든 연산 체계는 본질적으로 불완전 체계임
- 정합성을 갖춘 어떤 형식적 수론 체계를 세우더라도 그 체계 속에서 연역될 수 없는 옳은 수론적 진술이 항상 존재한다는 것
e.g. 골드바흐의 정리: 4 이상의 모든 짝수는 두 소수의 합이다.
- 기존의 공리들을 수정하거나 확장을 하더라도 그 확장된 일련의 공리로부터 형식적으로 연역될 수 없는 산술학적 진리들이 또 존재함
- 제2 불완전성 정리: 페아노 공리계를 포함하는 연산 체계의 정합성에 대한 상위 수학적 증명은 그 연산 체계에서 정리를 연역하는 데 사용된 추리 규칙과 근본적으로 다른 추리 규칙을 사용하지 않는다면 결코 확립될 수 없음
- 사상(mapping): 한 영역의 요소들을 다른 영역의 요소들에 대응시키는 것
- 괴델은 “만일 형식화된 산술학 체계에 관한 복잡한 상위 수학적 진술들이 그 형식화된 산술학 체계 자체 속의 산술학적 진술로 번역될 수 있다면 상위 수학적 증명을 쉽게 할 수 있다”는 것을 증명에 이용
VII. 괴델의 증명
1. 괴델 수 붙이기
- 괴델은 모든 산술학적 표현을 나타낼 수 있는 형식화된 연산체계 “PM”을 만들어냄
- 개개의 기본 기호마다 단 하나의 수(괴델 수)를 붙여줌
| 상항 기호 | 괴델 수 | 일상적 의미 | 상항 기호 | 괴델 수 | 일상적 의미 |
| ∼ | 1 | 아니다 | s | 7 | 바로 다음 수 |
| ∨ | 2 | 또는 | ( | 8 | 구두점(왼쪽 괄호) |
| ⊃ | 3 | 만일 …라면 …이다 | ) | 9 | 구두점(오른쪽 괄호) |
| ∃ | 4 | …이 있다 | , | 10 | 구두점(쉼표) |
| = | 5 | 같다 | + | 11 | 더하기 |
| 0 | 6 | 영(0) | × | 12 | 곱하기 |
- 대응 보조 정리(correspondence lemma)
1. 산술학적 진리 모두를 그 형식적 연산 체계의 기호 두름으로 바뀌면 정리가 됨
2. 형식적 기호들은 제각기 1대1 대응 방식으로 예정된 해석에 따른 의미를 가질 수 있음
| 숫자 변항 | 괴델 수 | 문장 변항 | 괴델 수 | 술어 변항 | 괴델 수 |
| x | 13 | p | 132 | P | 133 |
| y | 17 | q | 172 | Q | 173 |
| z | 19 | r | 192 | R | 193 |
| 숫자 변항에는 12보다 큰 소수를 부여 |
문장 변항에는 12보다 큰 소수의 제곱수를 부여 |
술어 변항에는 12보다 큰 소수의 세제곱수를 부여 |
|||
- 숫자 변항(numerical variable)에는 “ss0”와 같은 숫자나 “x+y”와 같은 숫자 표현 대입 가능
- 문장 변항(sentential variable)에는 “(∃x)(x=sy)”와 같은 형식문 대입 가능
- 술어 변항(predicate variable)에는 “(∃z)(x=y+sz)”와 같은 술어 대입 가능
- 위의 괴델 수를 통해서 형식문에도 ‘단 하나의 괴델 수’를 부여할 수 있음
- “(∃x)(x=sy)”의 형식문이 있다면, 형식문 속 기본 기호가 가지고 있는 괴델 수는 각각 8, 4, 13, 9, 8, 13, 5, 7, 17, 9
- 형식문에 등장하는 기본 기호의 수효만큼 크기 순서로 처음 열 개의 소수를 택한 다음, 기본 기호에 해당하는 괴델 수만큼 거듭제곱하면 단 하나의 괴델 수를 얻을 수 있음
- 위 형식문의 괴델 수는 28×34×513×79×118×1313×175×197×2317×279
- 형식문 두름의 괴델 수도 이와 같은 방법을 이용하면 얻을 수 있음
- 형식문 두름 속 두 개의 형식문의 괴델 수를 각각 m, n이라고 할 때, 형식문 두름의 괴델 수는 "k=2m×3n"으로 표현 가능
- 위의 과정을 통해 괴델은 형식적 연산 체계를 산술학으로 바꾸는 방법을 확립함
- 연산 체계 속의 표현들과 양의 정수의 어떤 부분 집합 사이에 1대1 대응 관계를 설정함4
- 반대로, 어떤 괴델 수가 주어지면 이제 우린 그 수와 대응하는 표현을 확인할 수 있음
e.g. “243000000”은 26×35×76으로 "0=0" 형식문임
2. 상위 수학의 산술학화
- PM 속의 개개의 표현 모두가 특정한 괴델 수와 대응하고 있기 때문에, 형식적 표현들과 그것들 상호간의 관계에 관해 언급하는 상위 수학적 진술은 그에 대응하는 괴델 수들과 그 괴델 수들 강호간의 산술학적 관계에 관해 언급하는 진술로 해석될 수 있음 (즉, 상위 수학을 산술학으로 바꾸는 것)
- dem(x, z)
- ‘괴델 수 x를 가진 형식문 두름은 괴델 수 z를 가진 형식문에 대한 PM 속의 증명’이라는 뜻
- x와 z 사이의 ‘산술학적 관계’를 가리키기 위한 축약 표현 (상위 수학)
- 이를 형식적 표기법으로 번역한 대응 표현은 “Dem(x,z)”로 나타냄 (형식 언어)
e.g. “dem(2,5)” -> “Dem(ss0, sssss0)”
- sub(x, 17, x)
- ‘괴델 수 x를 가진 형식문 속에 등장하는 모든 “y”에 수 x를 가리키는 숫자를 대입해서 만들어진 형식문의 괴델 수’라는 뜻5 (어떤 괴델 수를 가리킴)
- 대응 보조 정리가 적용되는 대상은 대입 함수가 아니라 “z=sub(x, 17, x)”라는 진술6
- “Sub(x, 17, x)”은 PM 속의 어떤 기호 두름을 가리킴 (어떤 수를 다른 수들의 함수로 지시하거나 지칭함)
3. 괴델 논증의 핵심 주장
(1) 형식문 G는 PM의 규칙을 사용해서 증명할 수 없다
[1] ∼(∃x)Dem(x, Sub(y, 17, y))
- 위 형식문은 ‘괴델 수 sub(y, 17, y)을 가진 형식문은 증명할 수 없다’는 상위 수학적 의미를 가짐
- 위 형식문의 괴델 수를 n이라고 하자
- 위 형식문 속 모든 “y”에 수 n을 대입하고, 새로 만들어지는 형식문을 G라고 하자
[G] ∼(∃x)Dem(z, Sub(n, 17, n))
- 위 형식문의 상위 수학적 의미는 ‘괴델 수 sub(n, 17, n)을 가진 형식문은 증명할 수 없다’는 것
- 형식문 G의 괴델 수는 g이며 g의 값은 sub(n, 17, n)임
- 즉, 형식문 G는 PM 속에서 ‘형식문 G는 증명할 수 없다’고 스스로 주장하는 것
(2) 만일 PM이 정합적 연산 체계라면 G는 반드시 형식적으로 증명될 수 없는 형식문이다
- 형식문 G가 증명될 수 있다면, 그 형식적 부정문인 ∼G도 증명될 수 있음 (그 반대도 마찬가지로 가능)
- 따라서, 형식문 G는 ∼G가 증명될 수 있을 경우에만 증명될 수 있음
- 그러나 어떤 형식문과 그 형식적 부정문이 둘 다 어떤 형식적 연산 체계에서 연역될 수 있다면 그 연산 체계는 정합적 체계가 아님
- 따라서, PM이 정합성을 가진 연산 체계라면 형식문 G는 반드시 형식적으로 증명될 수 없다는 결론에 도달함
(3) 형식문 G는 형식적으로 증명될 수 없음에도 불구하고 옳은 산술학적 형식문이다
- 형식문 G에 대한 상위 수학적 해석은 1단계에서 말한 것과 같이 ‘PM 속에서 형식문 G는 증명할 수 없다’임
- 그런데, 우리는 2단계를 통해 (PM이 정합적 체계라는 가정 하에) PM 속에 G에 대한 증명이 없다는 것을 밝힘
- 따라서, G는 옳은 산술학적 형식문임
(4) PM은 본질적으로 불완전 체계다
- 연산 체계가 완전성을 가지려면, 그 체계 속에서 표현될 수 있는 모든 옳은 진술이 그 체계의 공리들로부터 추리 규칙에 의해서 형식적으로 연역될 수 있어야 함
- G는 PM 속에서 형식적으로 연역될 수 없지만, PM의 옳은 형식문이기 때문에 PM은 불완전 체계임
- 설령 G가 PM의 새로운 공리로 추가된다 할지라도 그 확장된 체계 역시 불완전 체계임
- 새로 확장된 체계 속에서 연역될 수 없는 형식문은 괴델이 PM 속에서 옳으면서 연역될 수 없는 형식문을 만들어낸 방법을 모방하여 얼마든지 만들어낼 수 있기 때문
- 이 방법은 페아노 공리계를 포함하는 모든 연산 체계에 적용될 수 있음
(5) 만일 PM이 정합적 체계라면 PM의 정합성은 PM 자체가 반영될 수 있는 어떠한 상위 수학적 추론에 의해서도 확립될 수 없다
- 앞선 단계들을 통해 ‘만일 PM이 정합적 체계라면 PM은 불완전 체계이다’라는 상위 수학적 진술에 도달함
- ‘PM은 정합적 체계이다’라는 상위 수학적 진술은 ‘PM 속에서 증명될 수 없는 PM의 형식문이 적어도 하나 있다’는 진술과 동등함 (5장 참조)
- 위 진술은 형식문 A로 표현이 가능함 (어떤 x도 dem 관계를 맺지 못하는 수 y가 적어도 하나 있다)
[A] (∃y)∼(∃x)Dem(x, y)
- 그럼 ‘PM이 정합적 체계라면 PM은 불완전 체계이다’는 “A⊂G”로 표현할 수 있음
- 이제 형식문 A가 PM 속에서 증명될 수 없다는 것을 밝혀보자
- 일단 형식문 A가 PM 속에서 증명될 수 있다고 가정하자
- 그럼, 형식문 “A⊂G”가 증명될 수 있기에 분리 규칙을 사용하여 형식문 G가 증명될 수 있음
- 하지만, PM이 정합적 체계라면 G는 증명될 수 없음 (모순)
- 따라서, PM이 정합적 체계라면 형식문 A는 PM 속에서 증명될 수 없음
- 다만, 괴델의 결론이 배제하는 것은 PM 속에 반영될 수 있는 정합성 증명뿐이라는 것을 주의해야 함
- PM의 정합성에 대한 상위 수학적 증명은 배제하지 않음
- 실제로, PM과 같은 형식적 체계들의 정합성을 확립하는 상위 수학적 증명은 힐베르트 학파인 겐첸(G. Gentzen)에 의해 이루어짐
- 주어진 선 밖에 있는 한 점을 통과하면서 그 주어진 선에 평행하는 선은 오직 하나만 그릴 수 있다 [본문으로]
- 힐베르트는 어떤 상위 수학적 절차를 ‘유한한 단계를 가진 절차’로 간주할 수 있는가에 대해 명확하게 설명하지 않았음 [본문으로]
- 우리가 사용하고 있는 자연수에 관한 공리 [본문으로]
- 모든 양의 정수가 괴델 수인 것은 아님 (e.g. 100은 22×52로 소수 3이 인수로 나타나지 않음) [본문으로]
- 수는 개념, 숫자는 수를 표현하는 기호 즉 언어적 표현임 [본문으로]
- 만약 괴델 수 x를 가진 형식문이 괴델 수 17을 가진 변항을 포함하고 있지 않다면, ‘수정된 형식문’은 원래의 형식문 바로 그것임. “sub(x, 17, x)”이 가리키는 괴델 수가 바로 x인 것 [본문으로]
'Books' 카테고리의 다른 글
| 뇌의식의 기초 (28) | 2024.03.27 |
|---|---|
| 작은 것들이 만든 거대한 세계 (25) | 2024.03.03 |
| 커넥톰, 뇌의 지도 (31) | 2024.01.15 |
| 인간은 왜 인간이고 초파리는 왜 초파리인가 (57) | 2023.12.18 |
| 도파민네이션 (44) | 2023.08.17 |
댓글