[컴퓨터의 기원] 2. 괴델의 불완전성 정리

1. 괴델의 아이디어에서 무엇이 혁신인가?

1-1. 이전 내용 요약

컴퓨터의 본질과 기원에 대해 - 1. 힐베르트 프로그램

괴델의 불완전성 정리를 시작하기 전에 잠깐 전에 했던 배경지식을 요약해보자. 

유클리드 기하학으로 대표되는 수학적 사고방식은 참이라고 받아들이는 명제(공리)들과 논리적 추론 과정을 사용해 참인 명제(정리)를 만들어내는 작업이다. 그러나 비유클리드 기하학의 등장으로 인해 우리가 직관적으로 타당하다고 넘기는 공리들이 사실은 거짓일 수도 있다는 것이 드러나고 말았다.

결국 우리는 수학 체계의 기초라 할 수 있는 자연수 체계에도 의문을 품을 수 밖에 없었다. 과연 자연수에 대한 우리의 직관은 참일까? 만약 거짓이라면..?

프레게로 대표되는 논리주의자들은 자연수 산술 체계의 기초를 논리학의 토대 위에 올려놓는 작업을 시도한다. 논리적으로 확고하게 자연수 체계의 공리에 대한 기초를 다지겠다는 것이다.

그러나 러셀에 의해 논리학 즉, 칸토어의 집합론에 모순이 있다는 것이 밝혀진다. 이를 해결하기 위해 러셀은 자신이 제시한 역설을 해소하기 위해 새로운 집합론을 다듬기 시작한다. 그러나 러셀의 역설로 인해 이미 수학계의 멘탈은 흔들렸다. 아무리 탄탄하게 논리적으로 공리 체계를 다듬어도 결국 우리가 생각지도 못한 어떤 모순이 나중에 또 드러나지 않을까 우려하게 만들었던 것이다.

현대수학의 아버지, 다비드 힐베르트는 이 문제를 해결하기 위해 수학에서 논리학이나 기하학, 산술 같은 의미론적 해석을 제거하고 수학을 완전히 형식화한다. 즉, 수학을 기호열과 그 기호열을 다른 기호열로 바꾸는 변환규칙을 갖춘 게임으로 본 것이다. 이렇게 잘 정의된 기호열과 변환규칙을 형식체계라고 부른다. 그리고 수학적으로 올바른 형식체계를 찾으려는 시도를 가리켜 형식주의라고 부른다.

힐베르트로 대표되는 형식주의자들은 무모순하고 완전한 형식체계(게임)를 발견하는 것을 목표로 두어 힐베르트 프로그램을 시작한다.

 

1-2. 메타 명제와 힐베르트 프로그램의 딜레마

러셀의 역설에서 우리가 알 수 있는 것은, 어떤 명제가 자기 자신을 포함하는 명제일 경우, 논리적으로 참과 거짓을 가릴 수 없는 명제가 되기도 한다는 것이다.

예를 들어, "나는 거짓말을 한다." 라는 명제를 보자.

만약 이 명제가 참이면, 나는 거짓말을 하는 사람이다. 그런데 거짓말을 하는 사람이 하는 말은 거짓이므로 원래 내가 한 말(나는 거짓말을 한다)은 거짓일 것이다. 따라서 이 명제를 뒤집으면, 나는 거짓말을 하지 않는 사람이 된다.... 모순이다.

반대로 이 명제가 거짓이라면, 이 명제를 뒤집은, "나는 거짓말을 하지 않는다"가 참이다. (배중률) 나는 거짓말따윈 하지 않는 착한 사람이다. 그런데 정작 "나는 거짓말을 한다"고 말했다. 나는 거짓말을 하지 않는 사람이므로 이 명제는 참이다. 그런데 그 명제는 정작 "나는 거짓말을 한다"고 말한다... 모순이다.

이렇게 자기 자신을 명제의 일부분으로 가지는 명제는 논리적으로 모순을 낳을 위험이 있다. 이것을 우리는 메타 명제라고 부른다. 수학자들은 괴델 이전에도 어렴풋하게나마 메타 명제는 그 진술의 참과 거짓을 가릴 수 없거나, 혹은 그 진술이 참이라고 해도 증명되지 않을 수 있다는 것을 알고 있었다.

따라서 수학자들은 수학적 진술 자체를 명제의 일부로 두는 메타 수학은 수학 체계 내부에서 다뤄져서는 안 된다고 생각했다. 그도 그럴 것이, 메타 수학은 수학이 아니기 때문이다. 적어도 수학의 형식체계 바깥에서 다뤄지는 것이라고 생각했다.

문제는 힐베르트 프로그램을 위해서는 무모순하고 완전한 형식체계를 만들어야 한다는 점, 즉 형식체계의 무모순성과 완전성을 증명해야 하므로 메타 수학의 언어가 필요했다는 것이다. 이것이 당시 수학자들이 처한 딜레마다. 

 

1-3. 괴델의 혁신적 아이디어

아인슈타인과 괴델

결론부터 말하자면, 힐베르트 프로그램이 시작되자마자 거의 3년만에 괴델이라는 천재 수학자가 등장하여 힐베르트 프로그램의 이상을 좌초시킨다. 괴델의 결론은 무모순하면서 완전한 형식체계는 없다는 것이었다. 쉽게 말하면, 참인 명제인데도 증명 불가능한 명제가 그 어떤 산술 형식체계에라도 반드시 포함될 수 밖에 없다.

그러나 참이면서 증명 불가능한 명제가 있다는 것을 밝히는 것이 괴델 논문의 핵심은 아니다. 그건 이미 괴델 이전에 러셀의 역설에서 어렴풋하게 드러나고 있었다. 메타 수학적 명제의 경우, 참이면서 증명 불가능하거나, 참과 거짓 자체를 결정하지 못하는 케이스들이 제시되었다.

다만 괴델 이전 수학자들(ex 러셀), 그리고 논리학자들(ex 타르스키)은 이러한 메타 명제는 그 형식체계 바깥에서 다뤄져야 한다고 여겼다. 메타적 진술은 형식체계의 시스템 내부에서 증명해서는 안 된다는 상식적인 논리였다. 어떤 규칙이 규칙 스스로에 대해 말한다는 것은 차원이 다른 요소를 설명하는 것이므로 옳지 않다. (이렇게 생각하는 것은 합리적으로 들린다.)

이 때문에 힐베르트를 좌시한 형식주의 수학자들에게 관건이었던 사항은 어떻게 메타 수학적 언어와 방법을 마련할 것인가의 문제였다. 이러한 잘 정립된 메타적 언어와 방법론, 그 형식체계 바깥의 담론이 있어야만 특정한 형식체계가 무모순이면서 완전하다는 것을 외부에서 증명할 수 있기 때문이었다.

이 지점에서 괴델의 혁신은 바로 "메타 명제는 그 형식체계 바깥에서 다뤄야 한다"는 믿음을 박살낸 것이다. 괴델은 형식체계 안으로 메타 명제를 내부로 들여와도 형식체계가 그 명제를 다루는데 아무런 문제가 없음을 밝힌 것이다.

정확하게는, 자기 자신을 언급하는 메타 명제를 산술체계의 명제로 바꿀 수 있다는 것이다. 메타 명제는 우리가 생각하는 것과는 다르게 평범한 명제와 별로 다를 것이 없다...! 이것이 괴델의 혁신이다.

이것은 무엇을 의미하는가?? 바로 메타 명제를 그 형식체계의 공리와 변환규칙(추론)으로 증명해볼 기회가 생긴다는 것을 뜻한다. 수학자들이 그렇게 고심하던 딜레마, 즉 형식체계 자체를 수학적 연구 대상으로 둘 수 있는 시스템을 굳이 외부에서 찾을 필요가 없었던 것이다. 그냥 바로 그 형식체계 내부로 들여오면 되므로 해당 형식체계의 방법론을 사용해 메타명제의 진술의 참/거짓을 가리면 되는 것이다!!!

 

 

2. 괴델의 정리 증명

2-1. 괴델수 : 메타수학 명제를 수학 명제로 바꾸기

형식체계는 어디까지나 형식일 뿐이다. 따라서 형식체계에 어떤 의미론적 내용을 덧씌워서 이리저리 고심할 필요가 없다. 그저 주어진 기호열과 규칙을 그대로 받아들이면 된다.

따라서 괴델이 착수한 작업은 산술 형식체계 내에서 그 형식체계의 진술 자체를 대상으로 삼을 수 있는 진술을 찾는 것이었다. 메타수학의 명제를 수학 명제로 바꾸는 것! 바로 이것이 괴델의 목적이었고, 괴델은 이 작업을 성공하게 된다.

그렇다면 도대체 이것이 어떻게 가능한 것일까? 어떤 아이디어를 통해 메타수학 명제를 그냥 수학 명제로 둔갑시킬 수 있었던 것일까? 그 비결은 바로 "괴델 수"에 있다. 괴델은 "괴델수" 라는 아이디어를 통해 메타 명제를 묘한 방법으로 산술 명제로 둔갑시켜 버린 것이다. 

프레게나 러셀의 선구적인 연구를 통해 이미 많은 수학 명제들을 기호와 변환 규칙으로 환원시킨 전례가 있었고, 괴델은 이들의 작업을 가져왔다. 아래는 수학 산술체계에서 사용하는 명제들의 기호표이며, 괴델은 각 기호들에 고유한 수를 부여했다.

 

괴델수를 구하는 방법은 다음과 같다. 예를 들어, "x=1"이라는 간단한 수학 산술 명제를 생각해보자. 이 명제를 기호화하고 괴델수를 각각 구하면, x(13), =(5), s0(7, 6)이 된다. 여기서 1은 0의 바로 다음 수라는 의미로서 s0 기호로 사용한다. 

그리고 소수를 일렬로 나열하면 2, 3, 5, 7, 11, ... 이 되는데, 이 각각에 순서대로 괴델수를 제곱한다. 결과적으로 아래와 같은 자연수를 구할 수 있고, 이 자연수는 x=1 이라는 명제에 대응되는 유일한 자연수다.

(2^13) x (3^5) x (5^7) x (7^6) = 18,296,772,480,000,000

소수를 제곱하는 이유는 이렇게 해야 존재할 수 있는 모든 수학적 명제에 대해 각각의 고유한 자연수를 일대일 대응시킬 수 있기 때문이다.

그렇다면 어떻게 각 명제에 대응되는 고유한 자연수 변환이 메타 명제의 명제화를 가능하게 만드는 것일까? 그 비결은 아래와 같다. 알고 나면 사실 너무 간단한 방법이다.

" 'x=1'의 첫 번째 기호는 x다. " 라는 명제는 진술 자체를 대상으로 두고 있으므로 메타 명제다. 그런데 수학 명제 하나는 괴델수로 변환 가능하다. 위에서 x=1 명제의 괴델수는 18,296,772,480,000,000 임을 이미 보인 바 있다.

그렇다면 위 메타 명제는 놀랍게도 아래와 같은 평범한 수학 명제와 내용적으로 동등해진다!

(18,296,772,480,000,000)를 소인수분해 했을 때 2의 지수는 13이다.

 

너무나 명백하게 위 진술은 메타 명제가 아니라 그냥 평범한 산술 체계의 진술이다. 이렇게 괴델은 괴델수를 도입함으로써 모든 메타 명제를 하나의 산술체계 내의 명제로 다룰 수 있게 된 것이다! 메타 명제는 이제 어떤 자연수(명제)에 대한 진술이 되었다. 간단하면서도 너무나 놀라운 발상이 아닌가!

( ※ 바로 이 아이디어를 튜링이 기계적으로 해석하고 구현함으로써 오늘날의 컴퓨터에 대한 아이디어가 태동했다. 형식 시스템 즉, 기호열과 변환규칙의 조합을 오늘날의 컴퓨터로 따지면 기호열은 0과 1로 이루어진 코드, 변환규칙은 명령어로 해석할 수 있다. 그리고 메타명제란 하나의 형식 시스템 조합이며, 이것 또한 괴델이 말한 것처럼 또 하나의 기호열로 해석할 수 있는 것이다. 바로 이것이 소프트웨어다. )

 

 

2. 불완전성 정리 증명 과정

2-1. 증명의 괴델수

단순 명제 하나를 괴델수로 바꿀 수도 있지만, 한편으로 증명 또한 하나의 괴델수로 나타낼 수 있다. 증명은 일련의 명제들의 집합이다. 이 각각의 명제에는 괴델수가 할당되어 있다. 따라서 증명의 괴델수는 명제의 괴델수를 구하는 것과 동일하게 구한다. 예를 들어, 증명에 필요한 명제가 총 두 개가 있고, 각각의 괴델수가 m, n 이면 증명의 괴델수는 (2^m) x (3^n)이다. 이 값도 고유하다. 모든 수학 명제에 고유한 괴델수가 할당되어 있으므로 m과 n은 하나의 고유한 명제다. 따라서 증명 명제 집합도 하나의 고유한 괴델수가 할당된다.

 

2-2. 불완전성 정리 증명

2-2-1. sub(m, 17, m)

sub는 하나의 함수이다. substitute(대체)의 약자로, 그 의미는 m 괴델수를 가지는 어떤 명제에서 y(17)를 괴델수 특정 숫자 m으로 변환한 명제의 괴델수를 말한다. 단순한 계산이므로 산술체계 내부에서 충분히 다뤄질 수 있는 함수다.

예를 들어, "x=y+1을 만족하는 x가 존재한다"는 명제는 아래와 같은 기호로 바꿀 수 있다.

이 기호 또한 하나의 고유한 괴델수를 가진다. 이 괴델수를 m이라고 부르자. (m은 아주 거대한 자연수일 것이다.)

이제 sub(m, 17, m)은 다음과 같다. m 괴델수가 나타내는 명제는 위 명제다. 여기에서 y(17)부분을 m(어떤 자연수)으로 바꾼다. 그러면 아래의 명제가 된다.

우리는 y라는 기호를 m이라는 구체적인 숫자로 변환한 것이다. 숫자를 0의 다음 다음 다음 다음 ... 수라고 기호화할 수 있다. 새롭게 얻은 명제에 s는 m+1 개가 있다. 왜냐하면 원래의 명제 sy에 s가 하나 붙어 있었기 때문이다.

이 명제를 다시 괴델수로 변환한 것이 바로 sub(m, 17, m)이다. 이것도 아주 거대한 숫자일 것이다.

 

2-2-2. Dem(x, z)

함수란?

Dem이란 괴델수가 z인 어떤 명제에 x라는 증명(이것도 괴델수, 즉 자연수)이 있다는 의미의 함수다. 다소 추상적으로 설명했는데, 함수란 구체적으로 보면 한 집합과 다른 집합 사이의 일대일 매핑이다. 만약 괴델수가 z인 어떤 명제가 있고, 그것에 증명할 수 있는 어떤 괴델수 x가 있다고 해보자. (위에서 증명 명제들의 집합도 하나의 고유한 괴델수를 가질 수 있다고 했다)

이렇게 보면 하나의 증명 세트를 상징하는 괴델수(자연수)와 하나의 최종 결론을 상징하는 명제의 괴델수(자연수)는 일대일 매핑이 될 수 있다. 증명 가능하다면 이 함수관계에서는 한 쪽에 증명이 되는 명제들의 괴델수 집합이 있을 것이고, 다른 한 쪽에는 그 괴델수에 매핑되는, 즉 증명될 수 있는 명제의 괴델수가 있을 것이다.

쉽게 말해, 왼쪽에는 증명 명제들의 괴델수가 있고, 이들이 오른쪽의 명제를 하나씩 가리키고 있을 것이다. 이 오른쪽 집합의 명제들이 증명될 수 있는 결과 명제들(모두 괴델수)이다. 이 두 집합 각각 모두 자연수로 구성된다. 즉, Dem은 하나의 산술적인 함수인 것이다. 따라서 산술 체계 내부로 들여올 수 있다. 괴델수 하나를 받을 수 있는 것이다.

 

2-2-3. 증명 완료

아래의 명제를 보자.

괴델수가 n인 어떤 명제

위 명제는 sub(y, 17, y)라는 괴델수를 가진 명제를 증명할 수 있는 x가 없다는 의미다.

흥미로운 것은 위 명제도 단순 산술 명제라는 것이다. 따라서 괴델수를 가지고 있다. 이 명제의 괴델수를 n이라고 하자. (아주 큰 자연수일 것이다.)

이제 또 다른 명제를 보자.

괴델수가 g인 어떤 명제

이 명제는 n 괴델수를 가지는 명제에서 y를 숫자 n으로 바꾼 명제(sub)를 증명할 수 있는 x가 없다는 명제다. 이 명제를 G라고 부르고 괴델수는 g라고 약속하자.

 

오른쪽 식이 명제 G다.

그러면 이 명제 G는 정체가 무엇인가? 바로 왼쪽 식에서 y를 n으로 바꾼 식이 아닌가. 왼쪽 식의 괴델수는 n이다. 따라서 명제 G는 괴델수 n인 명제에서 y부분을 n으로 바꾼 식이다. 즉, sub(n, 17, n)이다.

명제 G의 괴델수는 g라고 약속했다. 따라서 sub(n, 17, n)의 값, 즉 괴델수는 g이다.

다시 원래의 명제 G로 되돌아가자. 원래 명제 G에서 이제 sub(n, 17, n)은 g로 바꿀 수 있다. 즉, Dem(x, g)다.

이제 원래의 명제 G는 괴델수 g인 명제를 증명할 수 있는 x는 없다는 명제가 된다.

즉, 명제 G는 다음과 같은 명제다. "명제 G를 증명할 수 있는 x는 없다" 왜냐하면 괴델수 g인 명제는 G이기 때문이다.

이것은 결론적으로, 명제 G는 참이면서도 증명 불가능하다는 뜻이다.

 

다시 생각해보자. 

우리가 궁극적으로 찾고 싶은 것은 명제가 자기 자신을 언급하면서 다음과 같이 말하는 명제다. 

명제 G : 명제 G는 증명 불가능하다.

 

위 명제는 만약 거짓이라고 했을 경우, 증명 가능하다는 의미가 되므로 논리적 모순이다. 배중률에 의해 명제 G는 참이 되어야 한다. 문제는 이 명제가 자기 자신을 그대로 언급하는 메타 명제이기 때문에 논리주의자들과 형식주의자들에 따르면 이 명제 자체를 원래의 형식체계 시스템 내부에서 증명해서는 안 된다는 것이다.

이때 괴델이 수행한 핵심은 바로 명제 G와 논리적 등가이면서도 자기 언급을 피하는 산술 명제를 찾는 것이었고, 그것이 바로 위에서 괴델이 제시한 산술명제 G였던 것이다.

자기 자신을 언급하는 명제의 참/거짓은 분명히 메타적이므로 그것의 참과 거짓은 외부에서만 확인이 된다. 그리고 명제 G는 참이다. (부정이 모순이므로) 그러나 이 참에 대한 증명은 적어도 형식체계 내에서는 없다고 나온다(Dem 함수를 포함한 위 명제를 보자.)