괴델의 불완전성 정리에 대한 많은 책들이 시중에 출판되어 있다. 허나 대부분이 역사와 증명의 의미에 치중되어 있고 실제 증명의 아이디어를 설명한 책은 거의 없으며, 있다고 하더라도 외국 서적을 번역하면서 난해한 표현이 많이 나와 이해하기가 어렵다. 이에 본 글에서는 불완전성 정리 증명의 핵심적인 아이디어를 크게 수학(mathematics)과 메타수학(meta-mathematics), 괴델수(Gödel number), 메타수학의 수학화의 3가지로 나누어 설명하겠다. 본 글이 불완전성정리의 아름다움을 느끼는 데 도움이 되길 바란다.
보통 불완전성 정리에 대한 책들에서는 간략하게 증명의 개요만 언급하는데 그것은 아래와 같다. \[G: G는 \:증명불가능하다.\]
만약 \(G\)가 거짓이라면 \(G\)는 증명가능하므로 참이된다. 이는 \(G\)가 거짓이라는 데 모순이다. 따라서 \(G\)는 참인데 \(G\)의 내용은 \(G\)가 증명불가능하다는 것이므로 결국 \(G\)는 참이지만 증명불가능한 명제라는 것이다. 이 설명을 보고 고개를 끄덕 인 후 증명이 끝난 것 아닌가? 라는 생각을 할 수도 있을 것이다. 그러나 명제 내부에 명제 자신을 언급한 순환논리부분을 해결하지 않으면 안되고 사실 불완전성정리의 핵심부분도 이 부분이며 수학의 명제와 메타수학의 명제를 구분하는 것이 이해의 시작이 된다.
아주 간단한 수학 명제 하나를 살펴보자. \[1+1=2\]
이 표현은 수학에 속한 표현이다. 이제 다음 명제를 살펴보면 \[``1+1=2"는 \:수학\: 명제이다.\]
이 진술은 앞에 나온 수학명제에 대해 무엇인가를 주장하고 있으며 따라서 수학이 아니라 메타수학의 명제라고 할 수 있다. 비슷하게 \(x\)는 변수이다, \(``x=1"\)은 방정식이다 들도 수학 명제가 아니라 메타수학의 명제이다. 수학과 메타수학을 구별하는 것은 몇 번을 강조해도 지나치지 않은데 이 구별에 소홀한 것이 수많은 역설이 만들어지는 이유이기 때문이다. 이제 다시 처음 식을 살펴보면 \(G\)는 증명불가능하다 는 명제는 수학의 명제가 아니라 메타수학의 명제가 되고 따라서 수학에서 쓰는 증명방법(귀류법)을 그대로 써서 대충 주장하면 안되는 것이다. 괴델은 이 문제를 해결하기 위해 괴델수라는 독창적인 아이디어를 구사하여 메타수학의 명제를 수학의 명제로 바꾸었는데 괴델수부터 차근차근 알아보도록 하자.
괴델수는 모든 기호, 변수, 명제, 명제묶음(증명)들에 유일한 숫자를 부여하는 것인데 몇가지 예를 들어보면 다음과 같다.
| 기호 | 괴델수 | 의미 |
|---|---|---|
| \(\sim\) | 1 | 아니다 |
| \(\vee\) | 2 | 또는 |
| \(\supset\) | 3 | \(\cdots\)라면 \(\cdots\)다 |
| \(\exists\) | 4 | \(\cdots\)이 존재한다 |
| \(=\) | 5 | 같다 |
| 0 | 6 | 영(0) |
| s | 7 | 바로 다음 수 |
| ( | 8 | 왼쪽 괄호 |
| ) | 9 | 오른쪽 괄호 |
| , | 10 | 쉼표 |
| \(+\) | 11 | 더하기 |
| \(\times\) | 12 | 곱하기 |
위의 표에 나와있는 기호들을 상항기호라고 하며, 이와 대응되는 개념은 변항(variable)기호인데 숫자 변항, 문장 변항, 술어 변항으로 나눌 수 있다. 숫자 변항에는 12보다 큰 소수, 문장 변항에는 12보다 큰 소수의 제곱수, 술어변항에는 12보다 큰 소수의 세제곱수를 부여하게 되며 예는 아래의 표와 같다.
| 변항 | 괴델수 | 대입 예 | |
|---|---|---|---|
| 숫자변항 | \(x\) | 13 | 0 |
| \(y\) | 17 | \(s0\) | |
| \(z\) | 19 | \(y\) | |
| 문장변항 | \(p\) | \(13^2\) | \(0=0\) |
| \(q\) | \(17^2\) | (\(\exists\) x)(\(x=sy\)): \(y\)의 다음 수 \(x\)가 존재한다. | |
| \(r\) | \(19^2\) | \(p\supset q\) | |
| 술어변항 | \(P\) | \(13^3\) | \(13\)은 소수이다. |
| \(Q\) | \(17^3\) | ||
| \(R\) | \(19^3\) |
이제 문장 (\(\exists x\))(\(x=sy\)) 를 살펴보자. 이것은 \(y\) 다음 수가 존재한다고 읽으며, 기본기호 하나하나의 괴델수를 살펴보면 8, 4, 13, 9, 8, 13, 5, 7, 17, 9이고 문장 전체의 괴델수는 다음과 같이 소수를 이용하여 표현한다. \[2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{17} \times 29^9\]
마찬가지로 증명에 대해서도 괴델수를 부여할 수 있는데 예를들어 증명이 두 서술로 되어 있고 각 서술의 괴델수가 \(m\)과 \(n\)이라면 증명의 괴델수는 \(2^m \times 3^n\) 으로 표현한다. 이런식으로 모든 수학적 표현에 대해서 겹치지 않고 유일하게 괴델수를 부여할 수 있다. 한가지 예를 더 들면 괴델수 243,000,000은 \(2^6 \times 3^5 \times 5^6\)으로 소인수분해 되며 지수부분인 6,5,6은 각각 0, \(=\), 0에 대응되므로 결국 \(0=0\)이라는 수학명제를 나타내게 된다.
괴델은 괴델수를 이용하여 메타수학의 명제를 수학의 명제로 바꾸는 데 성공하였는데 간단한 예를 들어보겠다. \(``\sim(0=0)"\) 는 0은 0이 아니다 라는 단순한 수학 명제인 반면 수학 명제 \(``\sim(0=0)"\)의 첫 번째 기호는 틸드(\(\sim\))이다.는 수학명제가 아니라 메타수학의 명제이다. 그런데 이 메타수학의 명제는 적당한 과정을 거치면 수학명제로 바뀌게 되는데, 편의상 \(``\sim(0=0)"\)의 괴델수를 \(a\)라고 하고 위의 상항기호 표에서 \(``\sim"\)의 괴델수가 1임을 기억하자. 그렇다면 첫 번째 기호가 \(``\sim"\)이라는 것은 곧 \(a\)를 소인수분해했을 때 제일 작은 소수인 2의 지수가 1임을 의미하게 되고 메타수학의 명제는 \(2\)는 \(a\)의 인수이지만 \(2^2\)은 \(a\)의 인수가 아니다.와 같이 수학명제로 바뀌게 된다. 기호로 표현하기 위해 표현을 바꾸면 \(y=z\times 2\)인 \(z\)가 존재하고, \(y=z\times 2 \times 2\)인 \(z\)는 존재하지 않는다. 가 되며 실제로 이를 기호로 표현하면 다음과 같다.
\[(\exists z) (sss\cdots sss0=z\times ss0) \cdot \sim(\exists z) (sss\cdots sss0=z\times (ss0 \times ss0)) \] (\(sss\cdots sss0\)에서 \(s\)는 정확히 \(a\)번 나타난다.) 이와 비슷한 방법으로 모든 메타수학의 명제를 괴델수를 이용하여 수학의 명제로 바꿀 수 있다.
이제 불완전성 정리를 천천히 이해해보자. Dem과 Sub/sub의 개념을 정의한 후 증명의 핵심 아이디어로 들어가 보겠다.
Dem은 증명을 뜻하는 demonstration의 약자로 Dem(\(x\), \(z\))은 괴델수 \(x\)를 가진 문장묶음이 괴델수 \(z\)를 가진 명제의 증명이다.의 축약표현으로 정의한다. 예를 들어 피타고라스 정리 증명의 괴델수가 \(m\)이고 피타고라스 정리의 괴델수가 \(n\)이라면 Dem(\(m\), \(n\))이라고 쓸 수 있는 것이다.
Sub은 치환 혹은 대입을 의미하며 소문자로 표현한 sub(\(x\),17,\(x\))는 괴델수 \(x\)를 가진 명제에 등장하는 변수 \(y\)들에 전부 숫자 \(x\)를 대입해서 만들어진 명제의 괴델수로 정의한다(17은 \(y\)의 괴델수임을 기억하자). 한 편, \(s\)를 대문자로 표시한 Sub(\(x\),17,\(x\))는 괴델수가 아닌 명제 그 자체로 정의한다. 이해를 돕기 위해 \(2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{17} \times 29^9\)를 다시 살펴보겠다. (\(\exists x\))(\(x=sy\))는 앞서 설명했듯이 \(y\) 다음 수가 존재한다고 읽을 수 있으며 괴델수를 \(k\)라 하면 \(k=2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{17} \times 29^9\)가 된다. 이제 \(y\)대신 \(k\)를 대입한다면 수정된 명제는 (\(\exists x\))(\(x=sss \cdots sss0\))이 되고(\(s\)는 \(k+1\)번 연속됨) \(s\)의 괴델수가 7임을 고려하면 \(k\)를 대입한 명제의 괴델수는 \(y\)부분에 해당되는 \(23^{17}\)부터 \(s\)로 바뀌어 아래의 식과 같이 된다.
\[2^8 \times 3^4 \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^5 \times 19^7 \times 23^{7} \times 29^7 \times 31^7 \times 37^7 \times \cdots (P_{k+10})^9\] (\(P_{k+10}\): \(k+10\)번 째 소수)
얼핏 보기에 명제의 괴델수를 명제 그 자체에 대입한다는 것이 순환논리같은 느낌을 주는데 이것이 바로 괴델의 핵심적인 아이디어 중 하나이다. 이제부터 본격적인 증명의 내용으로 들어가기로 하자.
불완전성 정리의 증명은 괴델수 \(z\)를 가진 명제는 증명불가능하다라는 메타수학의 명제를 수학의 명제로 바꾼 후, 이 명제의 특별한 경우가 증명될 수 없다는 것을 보이는것으로 이루어진다. 이제 다음의 명제를 살펴보자.
\[\sim(\exists x)\text{Dem}(x,\text{Sub}(y, 17, y))\]
위 명제는 Sub(\(y\) ,17, \(y\)) 의 증명은 존재하지 않는다, 즉 증명불가능하다는 의미를 가지는 메타수학의 명제이며, 앞서 설명했듯이 괴델수를 이용하면 수학의 명제로 바꿀 수 있고 수학 명제는 괴델수를 갖게 된다. 해당되는 괴델수를 \(n\)이라 한 다음 이 명제의 \(y\)를 \(n\)으로 바꾼 명제 \(G\)를 살펴보자.
\[\text{G}: \sim(\exists x)\text{Dem}(x,\text{Sub}(n, 17, n))\]
명제 \(G\)가 바로 우리가 찾는 명제인데 이것의 메타수학적 의미를 살펴보면 괴델수 sub(\(n\), 17, \(n\))을 가진 명제는 증명할 수 없다이다. 이 메타수학 명제와 대응되는 수학명제의 괴델수를 \(g\)라고 하고 \(g\)는 어떤 숫자일지 생각해보자. 놀랍게도 \(g=\text{sub}(n, 17, n)\)임을 알 수 있다. \(G\)는 괴델수 \(n\)을 가진 명제에서 \(y\)에 숫자 \(n\)을 대입하여 만든 명제이므로, 이것의 괴델수 \(g\)는 정확히 sub(\(n\), 17, \(n\))의 정의와 일치하게 된다. 이제 \(G\) 의미를 다시 살펴보면 괴델 수 \(g\)를 가진 명제는 증명불가능하다.이고 즉, \(G\)는 증명불가능하다는 의미가 된다. 이제 맨 처음으로 돌아가자. \(G\)에 대응되는 수학명제는 참이지만 증명불가능한 명제가 되어 불완전성의 정리가 증명된다.
필자는 고등학생때부터 괴델의 불완전성정리를 이해해보려고 괴델의 논문원본도 찾아보고 여러 교양서적을 많이 읽어보았었다. 그러나 논문을 다 보는것은 이해하기가 어렵고 교양서적은 겉핥기식으로만 나와있어서 최근까지도 증명의 핵심을 이해하지 못했었는데 출판사 승산에서 나온 ``괴델의 증명"을 읽으면서 한층 이해수준을 올릴 수 있었다. 이 책은 외국서적을 번역한 것으로 번역하면서 생소한 단어와 표현들이 많이나와 읽기가 어려운 부분이 있어 이번기회에 잘 풀어서 설명해볼 목적으로 글을 쓰게 되었다. 본 글이 논문과 교양서적 사이에서 가교 역할을 하여 불완전성 정리를 이해하는데 도움이 되길 기대한다.
Copyright ©2016 Jinseob Kim