괴델의 불완전성 증명

By | September 12, 2017

이 글은 한국 『SKEPTIC』 8권 140-157쪽에 실린 이광근 교수님 글 「튜링의 1935년 - 앨런 튜링은 정말로 천재인가」의 일부를 발췌하여 수정한 것입니다.

괴델의 불완전성 정리(Gödel's incompleteness theorem)를 직관적으로 표현하면 다음과 같다.

“참이지만 기계적인 논리체계로는 증명 불가능한 것이 존재한다. 자연수에 대한 명제들의 세계로 국한되더라도 그런 것이 존재한다.”

괴델이 이것을 어떻게 증명했는지 살펴보자.

불완전성 정리를 증명하기 위해서는 다음 등식을 만족시키는 명제 \(X\)가 존재함을 보이면 충분하다. \[ (X \text{ is not provable}) = X \tag{1}\] 그 이유를 살펴보자. 만약 모든 명제가 증명 가능하다면 임의의 명제는 참 또는 거짓, 둘 중 하나의 값을 가져야 한다. \(X\)가 참인 경우, 등식 (1)의 좌변도 참이라는 이야기이므로, \(X\)는 증명 불가능하다. \(X\)가 거짓이라면 그 반대가 참이므로, 등식 (1)에 따라 \(X\)는 증명 가능하다. 그런데 논리체계는 믿을만 해야 하므로[즉 무모순적이므로], 거짓을 증명할 수 있으면 곤란하다. 따라서 ‘\(X\)는 참이고 증명 불가능하다’만 사실일 수밖에 없다. \(X\)는 참인데 증명 불가능하므로 불완전성 정리를 증명한 것이다. 단, 그러한 명제 \(X\)가 있기만 하다면. 그런데 결론부터 말하자면, 그러한 명제가 존재한다. (이 글에서는 ‘명제’라고 표현했지만 사실은 ‘논리식’을 이른다.)

설명을 간결하게 하기 위해서, 이 글에서 사용될 몇 가지 표기법을 소개한다. 명제 ‘\(x\)는 증명 불가능하다’를 \(\mathrm{np}(x)\)로 쓰자. 명제 \(A\)에 밑줄을 그은 \(\underline{A}\)는 그 명제의 괴델수(Gödel number)를 뜻한다. 거꾸로 괴델수 \(Z\)에 윗줄을 그은 \(\overline{Z}\)는 그 괴델수에 해당하는 명제를 뜻한다. \(A[ `x\text{'} \mapsto C]\)는 명제 \(A\)에 있는 변수 \(x\)를 \(C\)로 바꾼 명제를 뜻한다. \([ `x \text{'} \mapsto C]\)에서 \( `x\text{'} \)는 상수기호로서 심벌 \(x\)를 뜻한다. 다른 것으로 바꿀 수 있는 변수가 아니다. 기호 \(:=\)는 그렇게 정의한다는 뜻이다. 양변이 같다는 판단이 아니다.

다시 논의를 이어가자. 이제 확인할 것은 등식 (1)을 만족시키는 명제 \(X\)가 존재하냐는 것이다.

다루는 논리체계는 자연수에 대한 세계이다. 자연수에 대한 논리 안에서 증명 불가능한 명제가 있음을 보여야 한다.

그런데 ‘\(x\)는 증명 불가능하다’는 명제는, 명제 \(x\)에 대한 명제이지 자연수에 대한 명제가 아니다. 그러나 자연수에 대한 명제로 만들 수 있다. 괴델은 명제들을 고유의 자연수로 표현하는 방법을 정의한다. 명제에 해당하는 자연수가 있고, 거꾸로 그런 자연수에서 해당 명제를 정확히 복구할 수 있는 이 형식을 괴델 숫자붙이기(Gödel numbering)라고 부른다.

명제는 기호들이 한 줄로 서 있는 문장이다. 명제를 표현하는 데 사용할 수 있는 기호들이 예를 들어 \(24\)개라고 할 때, 기호마다 \(1\)부터 \(24\)까지 고유번호를 붙인다. 한 명제가 \((7, 15, 1, 19)\)라고 하자. 이 명제는 소수를 차례대로 이용해서 \(2^{7} \times 3^{15} \times 5^{1} \times 7^{19}\)으로 표현할 수 있고, 그 결과 하나의 자연수가 나온다. 이 자연수를 소인수분해하면 원래의 명제를 찾아낼 수 있다.

이 방식을 통해서, 명제에 대한 명제는 모두 자연수에 대한 명제가 된다. 그래서 ‘\(x\)는 증명 불가능하다’는 명제도 명제 \(x\)에 해당하는 괴델수 \(\underline{x}\)를 사용해서 자연수에 대한 명제 ‘\(x\)는 증명 불가능하다’로 만들 수 있다.

그리고 ‘\(x\)는 증명 불가능하다’는 판단도 자연수 사이의 명제이어야 한다. 이것도 괴델 숫자붙이기의 방법으로 자연수에 대한 명제로 표현할 수 있다. 논리체계 안에서 증명이란 추론규칙들로 조립한 구조물이고, 증명한 명제는 그 구조물의 일부이다. 괴델 숫자붙이기를 사용하려면, 증명이라는 구조물의 괴델수는 증명한 명제의 괴델수를 인수로 가지고 있게 된다. 따라서 ‘\(x\)는 증명 불가능하다’는 명제도 자연수에 관한 명제로 다음과 같이 표현된다.

“증명에 해당하는 괴델수들은 \(\underline{x}\)로 나누어지지 않는다.”

그러면 다음을 만족시키는 자연수계의 명제 \(X\)가 존재한다. \[X = \mathrm{np}(\underline{X} )\] 그러한 \(X\)는 다음과 같다. \[\begin{eqnarray} X &:=& G[ ` x \text{'} \mapsto k] \tag{2} \\[8pt] G &:=& \mathrm{np}( \underline{ \overline{x} [ ` x \text{'} \mapsto x ] } ) \tag{3} \\ k &:=& \underline{G} \tag{4} \end{eqnarray}\] 그 이유는 다음과 같다. \[\begin{eqnarray} X &=& G[ ` x \text{'} \mapsto k ] \tag*{\(\because\) (2)} \\[8pt] &=& (\mathrm{np} ( \underline{ \overline{x} [ ` x \text{'} \mapsto x ]} )) [ ` x \text{'} \mapsto k ] \tag*{\(\because\) (3)} \\ &=& \mathrm{np}( \underline{ \overline{k} [ ` x \text{'} \mapsto k ] } ) \\ &=& \mathrm{np}( \underline{ G [ ` x \text{'} \mapsto k ] } ) \tag*{\(\because\) (4)} \\ &=& \mathrm{np}(\underline{X} ) \tag*{\(\because\) (2)} \end{eqnarray}\] 이렇게 괴델의 증명은 명쾌하게 끝난다.

Leave a Reply