이 글은 고려대학교에서 발간되는 교양잡지 <고대 투데이>의 2012년 봄 호에 실린 서평으로, 필자인 윤태웅 고려대 교수(전기전자전파공학부)가 원고를 사이언스온에도 따로 보내와 이곳에 싣습니다. 글 후반에 있는 ‘괴델의 증명 개요’ 부분은 <고대 투데이>에는 실리지 않은 내용입니다. -사이언스온

괴델의 증명
어니스트 네이글, 제임스 뉴먼, 더글러스 호프스태터 지음, 고중숙, 곽강제 옮김 | 승산

“정합적(무모순)인 공리계는 불완전하다. 즉, 참이지만 증명할 수 없는 명제가 늘 존재한다. 게다가 그 정합성도 증명할 수 없다!” 괴델의 이 정리에 담긴 뜻은 무엇일까? 수학의 한계를 이야기한 걸까? 아니면 수학의 지평을 넓힌 걸까? …이런저런 상상을 하며 <괴델의 증명>이라는 길을 따라 함께 여행에 나서보자. 비록 그 길이 좀 멀고 험할지라도!

과거로 시간여행을 떠날 수만 있다면, 내가 제일 먼저 가보고 싶은 곳은 20세기 초반의 빈이다. 잠시 그 시절 빈의 카페를 떠올려 보자. 카페는 예술가와 지식인들로 가득하다. 하얀 원탁 위에 수식을 써가며 머리를 맞대고 토론하는 사람들도 있다. 여기저기서 비트겐슈타인 이야기를 하는 이들도 눈에 띈다. 구석 자리에 앉아 그들에게 침묵의 시선을 보내는 수학자도 있다. 저 사람, 아무래도 오늘의 주인공인 쿠르트 괴델 같다. 빈은 20세기 지성사를 가장 화려하게 장식한 무대였다. 나치 독일군의 군홧발 소리가 점점 더 크고 가깝게 들려오는 급박함 속에서도 빈의 지식인들은 매력적인 이 도시를 떠나려 하지 않았다. 괴델도 마찬가지였다. 결국은 떠나야 했지만 말이다.

20세기 초반의 빈에서 한참을 더 거슬러 기원전 그리스로 가보자. 유럽에서 성경 다음 가는 베스트셀러라는 유클리드 원론을 만나기 위해서다. 유클리드는 공리[1] 다섯 개에서 수많은 기하학적 명제를 연역적으로 이끌어 내, 13권의 책에 담았다. 유클리드가 위대한 건, 그가 기하학적 명제들을 발견했기 때문이 아니라, 그것들의 진리성을 다섯 개의 공리로 압축했기 때문이다. 전제가 참이면 결론도 참일 수밖에 없는 연역체계의 구성, 이것이 우리가 여전히 원론을 이야기하는 이유다. 기하학처럼 우주마저 공리에 담을 수 있다면, 무한한 우주는 유한한 공리들의 동어반복인 셈이다. 놀랍지 않은가. 수학은 위대한 동어반복(great tautology)이다! 원론에서 제시된 연역 체계는 이후 수학의 전형이 되었고, 과학의 기반이 되었다. 그렇게 서양 과학 문명의 바탕을 이루었다. 뉴턴의 프린키피아는 물론이고, 스피노자의 윤리학, 심지어는 미국의 독립선언문도 유클리드 원론의 구성 방식을 따랐다.

문제는 전제, 즉, 공리의 진리성이었다. 그런데 원론에 나오는 다섯 공리 중 하나가 사람들을 불편하게 했다. “어떤 직선 밖의 한 점을 지나며 그 직선과 평행인 직선은 단 하나다.” 이른바 평행선 공리다. 직관적으로 명백해 보이는 다른 공리들과는 달리, 이 평행선 공리만큼은 그리스 사람들에게도 자명하지 않았던 모양이다. 이후 수학자들은 평행선 공리를 나머지 공리들을 이용해 증명하려고 노력했다. 하지만 아무도 성공하지 못했다. 원래 가능한 일이 아니었기 때문이다. 외려 평행선 공리를 “주어진 직선과 평행인 직선은 하나도 없다.”로 바꾸거나 “주어진 직선과 평행인 직선은 무수히 많다.”로 바꿔도, 유클리드 기하학만큼 옳은 비유클리드 기하학을 얻을 수 있음이 밝혀졌다. 난감한 일이다. 평행선 공리의 부정이 모순을 불러왔다면, 평행선 공리의 진리성에 다가갈 수 있었을 텐데 말이다.

비유클리드 기하학의 출현으로 공리의 진리성을 좇는 건 허망한 일이 돼 버렸다. 이제 연역적으로 얻어낸 결론이 실제로 옳은지 그 여부보다는 공리적 토대 자체에 관심을 돌려야 했다. 핵심 쟁점은 공리계의 내적 정합성(consistency)이었다. 공리계가 정합적이란 말은, 서로 모순되는 정리들이 연역될 수 없다는 뜻이다. 당연히 그래야 하지 않겠는가. 하지만 우리에게 익숙한 자연수 체계에서조차 정합성을 증명할 길은 보이지 않았다. 게다가 수학의 추상성은 점점 커졌고, 그에 따라 정합성을 보이는 일은 그만큼 더 어려워졌다.

수학의 토대는 생각보다 덜 단단해 보였다. 러셀은 화이트헤드와 쓴 <수학원리>를 통해 수론의 정합성을 형식논리학의 정합성 문제로 환원해, 수학의 기초를 마련하려 했다. 그러나 이런 식으로 수론의 정합성을 보일 수는 없었다. 어려운 문제를 또 다른 어려운 문제로 환원한 셈이었기 때문이다. 수학의 토대를 세우는 건 이제 힐베르트의 몫이 되었다. 공리계의 정합성을 확립하기 위해 힐베르트가 기획한 방법은 연역체계의 완벽한 형식화다. 모든 표현을 다 의미 없는 기호로 보고, 이 기호들을 결합하고 조직하는 방법만 명확한 규칙으로 만들자는 이야기다. 그러면 연역 과정에서 ‘공인되지 않는 추론 원리’가 끼어들 가능성을 완전히 없앨 수 있게 된다. 이렇게 형식화한 기호들의 연산체계는 아무것도 주장하지 않는다. 기호들이 의미가 없기 때문이다. 이제 수학은 형식이 되었다. 물론 2에 3을 더하면 5가 된다는 식의 의미는 여전히 존재한다. 하지만 그런 의미는 수학이 아니라 수학 위에서 다루도록 하면 된다. 수학에 대해 말하는 이른바 상위수학(meta-mathematics)은 그렇게 수학(mathematics)과 구별되었다. 힐베르트는 이런 방식으로 공리계를 형식화해 그 정합성을 보일 수 있을 것으로 믿었다.

» 쿠르트 괴델(Kurt Gödel, 1906-1978년). 출처/ Wikimedia Commons

힐베르트의 야심 찬 기획은 열매를 맺을 수 없었다. 처음부터 그건 가능한 일이 아니었다. 괴델은 1931년 ‘불완전성 정리’를 발표해, 수론 전체를 포함하는 포괄적인 공리계의 정합성은 보일 수 없음을 증명했다. 증명 불가능성에 대한 증명이었다. 아울러 괴델은 그 공리계가 본질적으로 ‘불완전(incomplete)’하다는 것도 밝혔다. 공리계가 불완전하다는 말은, 참이지만 그 체계 안에서는 연역될 수 없는 명제가 존재한다는 뜻이다. 정합성(무모순성)과 완전성을 다 보장할 수 없다는 ‘불완전성 정리’, 이것으로 힐베르트는 완전한 좌절을 맛봐야 했다. 러셀의 논리주의에 이어 힐베르트의 형식주의도 수학을 단단하게 떠받치는 토대가 될 수 없었다.[2]

‘불완전성 정리’는, 20세기 지성사를 가장 화려하게 장식했던 무대인 빈에서, 가장 찬란하게 핀 혁명적인 꽃이었다. 하지만 ‘불완전성 정리’가 처음 발표되었을 때는 당대의 수학자들도 그 내용을 바로 이해하기 어려웠다. 괴델 수의 정의로 시작되는 증명 과정이 너무도 기발했던 탓이다. (괴델 수란 수학적 형식문이나 상위수학적 진술에 일대일로 대응되는 자연수를 뜻한다.) ‘불완전성 정리’의 철학적 의미는 수학의 영역을 넘어선다. 그렇기에 누군가가 나서서 수학자들에게도 어려운 이 이야기를 비전공자들도 이해할 수 있도록 풀어주어야 했다. 어니스트 네이글과 제임스 뉴먼은 그 일을 <괴델의 증명>[3]이라는 책을 통해 성공적으로 해냈다. 괴델에 매료됐던 나는 자연스레 이 책을 수학·과학·논리학·철학에 관심이 있는 동료와 학생들에게 추천한다.

“정합적(무모순)인 공리계는 불완전하다. 즉, 참이지만 증명할 수 없는 명제가 늘 존재한다. 게다가 그 정합성도 증명할 수 없다!” 괴델의 이 정리에 담긴 뜻은 무엇일까? 수학의 한계를 이야기한 걸까? 아니면 수학의 지평을 넓힌 걸까? 인간의 한계를 지적한 걸까? 아니면 기계(컴퓨터)의 한계를 말한 걸까? 대체 인간이 인간처럼 판단하는 기계를 만드는 게 가능한 일이긴 할까? 만약 그런 기계를 만들 수 있다면, 그건 인간이 그만큼 뛰어난 존재일 거란 뜻이리라. 가만, 혹시 인간이 기계적으로 구성될 정도의 수준밖에 안 된다는 뜻은 아닐까? …이런저런 상상을 하며 <괴델의 증명>이라는 길을 따라 함께 여행에 나서보자. 비록 그 길이 좀 멀고 험할지라도!

■ ‘괴델의 증명’ 개요 ■ [4]

괴델의 ‘불완전성 정리’는 다음과 같다.

"수론 전체를 포함하는 포괄적인 공리계가 정합적(무모순)이면, 그 안에는 참이지만 증명할 수 없는 명제가 존재한다. 즉, 정합적(consistent)인 공리계는 불완전(incomplete)하다. 아울러 공리계가 정합적이면, 그 정합성(무모순성)은 증명할 수 없다."

‘불완전성 정리’의 증명은 괴델 수를 정의하는 것으로 시작된다. 먼저 형식문을 구성하는 모든 기호에 자연수를 순서대로 대응시킨다. 이를테면, ‘~’(부정)에는 1, ‘v’(또는)에는 2, ‘→’(만약 …이면 …이다)에는 3, ‘+’에는 4, ‘=’에는 5, ‘0’에는 6, ‘s’(그다음 수)에는 7, …을 할당하는 식이다. 더불어 숫자변수(numerical variable)에는 아직 배정되지 않은 소수를, 문장변수(sentential variable)에는 그런 소수의 제곱을, ‘크거나 같다’ 같은 서술 표현에는 그 세제곱을 차례대로 대응시킨다. 그리고 기호·변수·서술부로 구성된 형식문의 괴델 수는, 오름차순으로 정렬된 소수들을 문장 구성 성분의 괴델 수만큼 거듭제곱한 다음 서로 곱해서 얻는다. 예컨대 “1 + 2 = 3”(“s0 + ss0 = sss0”)의 괴델 수는 아래와 같다.

2⁷ × 3⁶ × 5⁴ × 7⁷ × 11⁷ × 13⁶ × 17⁵ × 19⁷ × 23⁷ × 29⁷ × 31⁶.

또 “p → q”(“p이면 q다”)의 괴델 수는

2^m × 3³ × 5ⁿ

이 된다. 여기서 m과 n은 (어떤 소수의 제곱으로 정의된) 문장 변수 p와 q의 괴델 수다.

공리계의 모든 형식문에 일대일로 대응하는 괴델 수를 붙이고 나서, 괴델은 한 걸음 더 나아가 형식문에 대한 상위수학적(meta-mathematical) 진술도 모두 수론적 주장으로 대체할 수 있음을 보였다. 이를테면, “괴델 수 a인 형식문이 괴델 수 b인 형식문의 증명이다.”라는 진술을 “a와 b가 f(a,b) = 0이라는 산술적 관계를 만족한다.”처럼 바꿀 수 있다. 상위수학적 진술에도 고유한 괴델 수를 정의할 수 있게 된 것이다. 이제 괴델 수는 모든 것에 대응한다. 불완전성 정리의 증명 과정은 이렇다.

1.    우선 Sub(x,‘y’,x)를 다음과 같이 정의한다.

Sub(x,‘y’,x): 괴델 수가 x인 형식문의 변수 y에 다시 x를 대입하여 만든 형식문.[5]

그리고 아래와 같은 형식문 Q를 생각한다.

Q: “Sub(y,‘y’,y)는 증명할 수 없다.”[6]

변수 y의 값이 괴델 수인 형식문에서 ‘y’라는 기호로 표시된 변수를 y의 값으로 바꾼 게 Sub(y,‘y’,y)인데, 형식문 Q의 내용은 이런 Sub(y,‘y’,y)를 증명할 수 없다는 것이다. 형식문 Q의 괴델 수를 n이라 하자. 그다음 이 숫자 n을 다시 Q의 y에 대입하자. 이렇게 해서 얻은 형식문을 G라 하면, G는 다음과 같이 표현된다.

G: “Sub(n,‘y’,n)은 증명할 수 없다.”[6]

여기서 Sub(n,‘y’,n)은 괴델 수가 n인 형식문의 변수 y에 상수 n을 대입한 결과다. 위에서 n을 Q의 괴델 수라 했으므로, Sub(n,‘y’,n)은 Q의 변수 y에 상수 n을 대입해서 얻은 것과 마찬가지다. 그런데 이게 바로 G다. 따라서 Sub(n,‘y’,n) = G가 성립한다. 이제 G를 다음과 같이 다시 쓸 수 있다.

G: “형식문 G는 증명할 수 없다.”

2.    G의 내용은 ‘G를 증명할 수 없다는 것’이다. 그렇기에 G를 증명할 수 있다는 말은 ‘G를 증명할 수 없음’을, 즉, ‘~G(G의 부정)를 증명할 수 있음’을 뜻한다. 곧, G의 증명은, ~G를 증명할 수 있을 때만 가능하다. 그런데 정합적인 공리계에서는 G와 ~G를 함께 증명할 수 없다. 따라서 공리계가 정합적이면, G는 증명할 수 없다.

3.    G를 증명할 수 없다는 건, G가 참이란 이야기다. G의 내용이 바로 그걸 뜻하기 때문이다. 즉, 공리계가 정합적이면, G는 참이지만 (그 추론 규칙으로는) 증명할 수 없는 형식문이 된다.[7] 정합적인 공리계는 불완전하다.

4.    마지막으로 “공리계가 정합적이면 G가 성립한다.”를 증명한다. 이제 공리계의 정합성을 보일 수 있다면, G도 증명할 수 있게 된 것이다. 그런데 2에서 확인했듯이, 정합적인 공리계에서는 G를 증명할 수 없다. 따라서 공리계의 정합성을 증명할 수 있다고 가정하면 모순이 발생한다. 공리계의 정합성은 증명할 수 없다.

이로써 체계 내적 추론 규칙으로는 공리계의 정합성을 증명할 수 없음이 밝혀졌다. 다만, 공리계 밖의 상위수학적 논리로 정합성을 증명할 가능성은 여전히 남아있다. 하지만 설사 그런 상위수학적 증명이 가능하다 하더라도, 그걸 알고리즘 형태로 형식화할 수는 없으리라.

■ 글쓴이

윤태웅 고려대학교 전기전자전파공학부 교수

[1] 여기서는 공리와 공준을 구별하지 않기로 한다.
[2] 이밖에 배중률의 가없는 사용에 반대한 브로우베르의 직관주의도 수학기초론의 한 축이었다. 직관주의적으로 수학을 구성하면 모순이나 역설은 피할 수 있다. 하지만 동시에 수학의 많은 부분을 포기해야만 한다. 배중률이 현대 수학의 핵심 전제기 때문이다. 브로우베르는 힐베르트와 격렬하게 대립했지만, 증명 과정이 유한한 절차여야 한다는 점에서는 직관주의와 형식주의가 다르지 않았다.
[3] E. Nagel (author), J.R. Newman (author), & D.R. Hofstadter (editor, forward), Godel’s Proof, NYU Press (고중숙·곽강제 옮김, 괴델의 증명, 승산). 정합성과 형식주의에 관해 앞에서 이야기한 내용도 이 책에서 빌려 왔다.
[4] 이 내용은 <괴델의 증명> 7장을 짧게 요약한 것이다.
[5] 만약 괴델 수가 x인 형식문에 y라는 변수가 없다면, 아무런 대입도 일어나지 않으므로 Sub(x,‘y’,x)의 괴델 수는 x값과 같다. 예컨대 x = 243,000,000 = 2⁶ × 3⁵ × 5⁶이면, 이 형식문은 “0 = 0”에 해당하기에 어떤 변수도 포함하지 않는다. 따라서 이때 Sub(x,‘y’,x)의 괴델 수는 그대로 243,000,000이 된다.
[6] 형식문 Q는 y라는 변수를 포함하므로, 아직 그 의미가 확정되지 않았다. 하지만 G는 y에 n이라는 값이 대입된 문장이기에, 그 뜻이 명확하다.
[7] 만약 다른 공리를 추가해 G가 증명될 수 있도록 공리계를 수정하면, 이 새로운 공리계에서 다시 1번과 같은 과정을 거쳐 참이지만 증명할 수 없는 명제를 또 구성할 수 있다.