쿠르트 괴델이라는 괴이한 이름을 가진 수학자가 있었어요.

http://www.arithmeum.uni-bonn.de/en/events/285

이렇게 생긴 사람입니다.

귀엽죠?

저 귀여운 괴델은 25살 때, 수학 전체를 통틀어서 가장 중요하다고 말해도 반대할 만한 사람이 그렇게 많지 않은, 그정도로 중요한 정리를 하나 증명합니다.

그게 그 유명한 "불완전성 정리(Incompleteness theorem)"인데요.

도대체 나는 25살때 무엇을 증명하고 있었는지 되새겨 보며, 불완전성 정리가 뭔지 한번 알아 볼게요.

불완전성 정리는, 일반인들의 용어로 나타내자면 "모순이 없는 수학적 체계에는 증명도 할 수 없고 반증도 할 수 없지만 참인 명제가 반드시 존재한다."입니다.

약간 다르게 표현하자면, "모순이 없으면서 동시에 완전한 산술체계는 존재하지 않는다." 즉, "산술체계는 모순이 있거나, 완전하지 못해야 한다"는 뜻입니다.

어렵죠?

저도 어려워요.

괴델이 이 주장을 증명하기 위하여 사용한 방법이 “괴델 수 붙이기”라는 방법입니다.

말 그대로 모든 문장에 수 하나를 대응시키는 방법입니다. 예를 들어, a에는 2, b에는 3, c에는 5, d에는 7, … 이런식으로 문장을 만들기 위하여 필요한 모든 기호에 하나의 수를 붙입니다. =이나 +같은 기호에도 다 다른 수를 붙입니다.

그럼 어떤 문장이든지 하나의 수로 나타낼 수 있습니다. 442132도 하나의 문장이고, 5928313949858828233도 하나의 문장이 됩니다. 지금 쓰고 있는 이 글도 하나의 수로 나타낼 수 있습니다. 이렇게 수를 붙이는 방법은 여러가지가 가능하겠지만, 중요한건 그런게 가능하다는 사실입니다.

자연수는 무한히 많기 때문에, 문장에 수를 대응시키는 방법을 하나 정했다면, 자연수에는 우리가 상상 가능한 모든 문장이 들어 있게 됩니다. 아직 아무도 한번도 말하지 않았더라도, 그것이 문장이기만 하다면 자연수 중 어딘가에는 존재하게 됩니다.

수학자들은 어떤 주장이 참인지 거짓인지 증명하고 싶다면 그 증명에 해당하는 문장을 찾아냅니다. 어차피 모순이 없는 체계이므로, 어떤 명제든지 참이거나 거짓이거나 반드시 둘 중 한가지 경우만 가능하고 참이면서 거짓인 경우는 불가능하죠. 따라서, “A라는 문장이 거짓이다”라는 문장은 “A가 아니다라는 문장이 참이다”를 증명하는 것과 같습니다. 그러므로 모든 증명은 “그 주장은 참이다”를 증명하는 것과 같다고 볼 수 있어요.

어쨌든, 어떤 주장이 참이라는 사실을 증명하는 문장도 자연수에서 잘 찾아보면 반드시 그 문장에 해당하는 수가 있습니다.

그러니까, 주장도 수로 나타낼 수 있고 증명도 수로 나타낼 수 있네요.

1. 우리가 증명하고 싶은 주장에 대한 수를 a라고 하고,

2. 그 사실을 증명하는 문장에 대한 수를 b라고 하죠.

3. 그럼 “b는 a가 참이라는 사실을 증명한다”라는 문장을 쓸 수가 있어요. 그럼 이 문장에 대한 수도 어딘가에 있겠네요?

4. 그 수를 c라고 하죠.

이제 증명은 (형식적으로는) 아주 간단해 지는데, 어떤 주장 a에 대해서 a를 증명하는 수 b를 찾거나, a가 틀렸음을 증명하는 수 b를 찾으면 됩니다.

반대로, 만약 어떤 주장 a에 대해서, b를 절대로 찾을 수 없다면 a는 증명할 수 없을거예요. 맞는지 틀리는지 모른다는 뜻이죠. 하지만 자연수는 무한히 많다고 했으니, 웬만해서는 있을 것 같죠?

사실, 힐베르트가 제시한 "힐베르트 프로그램"이라는 방법이 이 일을 할 수 있는데요, 어떤 주장을 증명하고 싶으면 그 주장을 자연수로 번역합니다. 그 다음, 그 주장을 증명하는 자연수를 찾아요. 1이 증명인지 확인해보고, 2가 증명인지 확인해보고, ... 19283가 증명인지 확인해보고, 19284가 증명인지 확인해보고, ... 이 짓을 증명이 나올 때 까지 해봅니다. 힐베르트는 이 과정이 반드시 끝날 것이라 생각했고, 그게 끝난다는 사실을 증명할 수 있을 것이라고 생각했어요.

괴델은 이 부분을 파고들었어요.

일단, 다음과 같은 수를 만듭니다.

"수 a를 갖는 주장에서, 수 b에 해당하는 부분을 수 c로 바꾼 주장"에 해당하는 수입니다. 이걸 sub(a, b, c)라고 부릅니다. 일단은, sub는 어떤 자연수입니다.

그 다음, "x가 y를 증명하지 않는다"는 주장을 수로 나타냅니다. 이 수를 n이라고 해 봅니다. 여기서 x랑 y는 아무 주장에 관한 수라도 생관 없습니다.

그럼, sub(n, y, n)도 하나의 수가 됩니다.
즉, "x가 y를 증명하지 않는다"는 주장에서 y대신에 n을 썼으므로 "x가 (x가 n을 증명하지 않는다)는 주장을 증명하지 않는다"가 됩니다. 이 주장을 G라고 불러 봅니다.

이제 G는 G를 증명하는 어떤 수 x를 찾아내기만 하면 증명되는데요, 만약 그런 수 x가 있다면, G가 증명되었으므로 x는 "x가 n을 증명하지 않는다"는 주장을 증명하지 않는 사실이 증명됩니다.

네. 방금 뭔가 꼬였죠?

그러나, 만약 그런 수 x가 없고 G를 증명할 수 없다면, G는 증명할 수 없다는 사실이 증명되었으므로 G가 증명됩니다.

...

머릿속에서 뭔가 한번 더 꼬이죠?

제가 위에서 설명한 내용은 쉬운 이해를 위해서 생략되고 대충 건너뛴 부분이 많습니다. 제대로 이해하려면 집합론과 논리학을 좀 더 깊이있게 공부해야겠죠.

중요한건, 모순이 없는 수학 체계에서는 참이지만 그 체계 내의 논리로는 증명할 수 없는 명제가 반드시 존재한다는 사실입니다.

더 중요한건, 따라서 수학자들은 언제나 할일이 많이 남아 있다는 점이죠. 무한히 많이 남아있습니다.