쿠르트 괴델(Kurt Gödel)

쿠르트 괴델은 1906년 오스트리아–헝가리 제국 모라비아의 브륀(지금의 체코 브르노)에서 독일어를 쓰는 집안에 태어났습니다. 어릴 때 무엇이든 캐묻는 버릇 때문에 집에서 '왜 씨'라고 불렸다고 합니다. 1924년 빈 대학에 들어가 물리학을 공부하다 수학으로 옮겼고, 스승인 수학자 한스 한을 따라 철학자와 과학자들의 모임인 빈 학파에 드나들었습니다. 그 무렵 수학의 토대를 둘러싼 논쟁은 힐베르트의 계획으로 모이고 있었습니다. 수학 전체를 기호 규칙의 형식 체계⁠(formal system)⁠로 적고, 그 체계가 무모순이고(어떤 명제와 그 부정을 함께 증명하는 일이 없고) 완전하다는 것(참인 문장은 모두 증명된다는 것)을 유한한 방법으로 증명하자는 것이었습니다(수학 기초론 논쟁⁠(debate on the foundations of mathematics)⁠).

나이 세 ·

1929년의 박사 논문에서 그는 그 계획의 한 조각을 이루었습니다. 1차 논리⁠(first-order logic)⁠의 완전성 정리입니다. 1차 논리는 '모든 x에 대해', '어떤 x가 있어서'라는 말을 대상에 대해서만 쓰는 논리이고, 해석은 기호들에 구체적인 뜻(어떤 대상들의 모임과 관계)을 주는 방식입니다. 정리는 모든 해석에서 참인 논리식은 모두 논리의 규칙으로 증명할 수 있다는 것입니다. 논리 자체에는 구멍이 없다는 뜻입니다. 이름이 비슷한 불완전성 정리와 헷갈리기 쉽지만, 완전성 정리⁠(completeness theorem)⁠는 '모든 구조에서 참인가'를 묻고, 불완전성 정리는 '자연수⁠(natural number)⁠라는 하나의 구조에서 참인가'를 묻습니다.

그가 공부하던 1920년대 후반의 빈은 제국의 수도에서 작은 공화국의 수도로 줄어든 도시였습니다. 사회민주당 시 정부가 노동자 주택과 학교를 짓던 '붉은 빈'의 한편에서, 대학에서는 민족주의와 반유대주의 학생 단체들이 세력을 키우고 있었습니다. 그 속에서 철학자 모리츠 슐리크의 목요일 모임, 곧 빈 학파는 과학의 언어를 논리로 정리하면 관찰로 확인할 수 없는 형이상학을 없앨 수 있다고 믿었고, 철학자 루돌프 카르나프가 1928년 빈에서 한 논리학 강의는 괴델을 수리 논리학⁠(mathematical logic)⁠으로 이끈 계기 가운데 하나였습니다. 그는 경제학자의 아들인 수학자 카를 멩거가 이끈 수학 콜로키엄에서도 활발히 활동했습니다. 그의 박사 논문의 주제는 1928년 힐베르트와 아커만이 교과서에서 열린 문제로 남긴 물음, 곧 1차 논리가 완전한가였습니다. 빈의 철학자들이 그에게 논리의 언어를 주었고, 괴팅겐의 수학자들이 그에게 문제를 준 셈입니다.

1930년 9월 쾨니히스베르크 학회의 토론 자리에서 그는 짧게 폭탄 같은 결과를 알렸고, 이듬해 빈에서 논문으로 발표했습니다. 그 제목은 「『수학 원리』와 관련 체계의 형식적으로 결정 불가능한 명제들에 대하여」로, 러셀과 앨프리드 노스 화이트헤드가 수학 전체를 논리에서 이끌어 내려고 쓴 체계를 정면으로 겨냥했습니다. 첫 착상은 기호마다 번호를 붙이고, $k$번째 기호의 번호가 $c_k$이면 $2^{c_1} 3^{c_2} 5^{c_3} \cdots$를 계산해 식 전체를 자연수 하나로 바꾸는 것이었습니다. 소인수분해⁠(prime factorization)⁠는 한 가지뿐이므로 수에서 식을 되찾을 수 있고, '이 수는 어떤 식의 증명의 번호다' 같은 말이 모두 소수⁠(prime number)⁠와 곱셈에 관한 산술의 명제가 됩니다. 이렇게 체계가 자기 자신에 대해 말하게 한 뒤, 그는 위의 식처럼 '나는 증명할 수 없다'는 뜻의 문장 G를 만들었습니다. G가 증명된다면 체계는 거짓을 증명한 것이니, 체계가 무모순이면 G는 증명되지 않고, 바로 그래서 G는 참입니다(불완전성 정리). 이 논증에는 체계가 산술을 담고, 공리⁠(axiom)⁠인지 아닌지를 기계적으로 가려낼 수 있다는 조건이 필요합니다. 자기 자신에 대해 묻고 답을 뒤집는 이 모양은 대각선 논법⁠(diagonal argument)⁠과 러셀의 역설⁠(Russell's paradox)⁠의 모양입니다. 그는 이어 체계가 자기의 무모순성⁠(consistency)⁠을 스스로 증명할 수 없다는 제2 정리도 보였고, 쾨니히스베르크에서 발표를 들은 폰 노이만이 같은 결론에 이르러 편지를 보냈을 때는 이미 논문에 넣은 뒤였습니다. 힐베르트가 바란 방식의 증명은 여기서 막혔습니다.

이 결과가 곧바로 받아들여진 것은 아닙니다. 쾨니히스베르크 학회에서 그의 짧은 발언의 뜻을 바로 알아챈 사람은 폰 노이만 정도였습니다. 집합론⁠(set theory)⁠의 공리를 처음 적은 에른스트 체르멜로는 1931년 학회에서 그를 만난 뒤 편지로 증명에 오류가 있다고 주장했고, 철학자 비트겐슈타인은 끝까지 이 정리의 의미를 낮게 보았습니다. 그러나 1930년대 중반까지 논리학자들 사이에서는 이 정리가 옳고 결정적이라는 데 이견이 없어졌고, 힐베르트 학파의 파울 베르나이스는 증명론⁠(proof theory)⁠의 목표를 바꾸어 나갔습니다. 체계가 자기 자신에 대해 말하게 만드는 괴델 수⁠(Gödel number)⁠의 기법은 표현 바꾸기의 극적인 예이자, 자기 참조⁠(self-reference)⁠와 대각선을 수학의 정밀한 도구로 만든 전환점이었습니다.

1930년대 그는 빈과 프린스턴을 오가며 계산 가능성⁠(computability)⁠의 뜻을 다듬는 데도 참여했습니다. 그가 1934년 프린스턴 강의에서 정리한 재귀 함수⁠(recursive function)⁠, 곧 0과 '다음 수'에서 출발해 이미 만든 함수⁠(function)⁠를 자기 자신에게 되풀이해 적용하는 규칙만으로 만든 함수들은 계산할 수 있는 함수의 한 정의였고, 논리학자 알론조 처치의 람다 계산⁠(lambda calculus)⁠에는 처음에 확신을 보이지 않았던 그도 튜링의 분석은 설득력이 있다고 인정했습니다(처치–튜링 논제⁠(Church–Turing thesis)⁠, 튜링 기계⁠(Turing machine)⁠). 1938년에는 무희였던 아델레 님부르스키와 결혼했고, 같은 해 연속체 가설⁠(continuum hypothesis)⁠, 곧 크기가 자연수 전체보다 크고 실수⁠(real number)⁠ 전체보다 작은 무한집합은 없다는 가설을 표준 집합론의 공리에 더해도, 원래 공리에 모순이 없는 한 새 모순이 생기지 않음을 발표했습니다. 정의할 수 있는 단계만 밟아 층층이 쌓은 집합⁠(set)⁠들만의 세계를 만들어, 그 안에서 연속체 가설이 참임을 보인 것입니다. 1963년 미국의 수학자 폴 코언이 반대쪽도 모순이 없음을 보여, 연속체 가설은 표준 공리로 증명할 수도 반증할 수도 없는 문장이 되었습니다.

1936년 빈 학파의 모리츠 슐리크가 대학 계단에서 옛 학생에게 살해된 일은 이미 신경 쇠약을 겪던 그를 크게 흔들었습니다. 1938년 오스트리아가 독일에 병합되자 대학 강사라는 그의 지위는 없어졌고, 새 제도에서 다시 자격을 받으려면 정치적 심사를 거쳐야 했습니다. 1939년 가을에는 빈 거리에서 그를 유대인으로 여긴 젊은이들에게 습격당해 아내 아델레가 우산으로 막아 냈다는 일화가 전하고, 같은 해 그는 군 복무에 적합하다는 판정까지 받았습니다. 고등연구소의 플렉스너와 베블런이 미국 비자와 독일의 출국 허가를 얻도록 도왔고, 대서양 항로가 전쟁으로 위험해진 탓에 그는 1940년 초 아내와 함께 시베리아 횡단 철도와 일본을 거쳐 배로 샌프란시스코에 닿은 뒤 프린스턴 고등연구소에 자리 잡았습니다. 그곳에서 그는 아인슈타인과 거의 날마다 함께 걸어 출퇴근했습니다. 1949년 아인슈타인의 일흔 살 생일에는, 중력을 시공간⁠(spacetime)⁠의 휘어짐으로 설명하는 일반 상대성 이론⁠(general relativity)⁠의 방정식을 만족하면서 우주 전체가 회전⁠(rotation)⁠하고 앞으로 나아가기만 해도 자기 과거로 돌아오는 길이 있는 해를 찾아 선물했습니다. 1947년 미국 시민권 심사에 아인슈타인, 경제학자 오스카어 모르겐슈테른과 함께 갔는데, 모르겐슈테른의 회고에 따르면 그는 미국 헌법에서 독재가 합법적으로 들어설 수 있는 논리적 허점을 찾았다며 심사관 앞에서 설명하려 했다고 합니다. 수학적 대상이 사람과 독립적으로 있다고 믿은 그는 빈 학파의 실증주의와는 반대편에 섰습니다.

프린스턴에서 그는 점점 철학으로 옮겨 갔습니다. 1946년 종신 연구원이 되었지만 교수가 된 것은 1953년이었는데, 동료들이 그의 까다로운 성격과 행정 능력을 걱정했기 때문이라는 이야기가 전합니다. 1951년 브라운 대학의 깁스 강연에서 그는 불완전성 정리에서 이런 결론을 끌어냈습니다. 사람의 마음이 어떤 기계보다도 수학을 더 많이 알아낼 수 있거나, 아니면 사람이 결코 풀 수 없는 수학 문제가 있거나, 둘 가운데 적어도 하나는 참이라는 것입니다. 그는 라이프니츠의 저작을 깊이 파고들었고, 1959년 무렵부터는 철학자 에드문트 후설의 현상학을 연구했으며, 신의 존재에 대한 라이프니츠 식 존재론적 증명을 '반드시', '가능하다'를 다루는 양상 논리⁠(modal logic)⁠로 다시 쓴 원고를 남겼습니다. 이런 철학적 작업은 대부분 그가 죽은 뒤 전집으로 출판되었습니다.

1956년 그는 암으로 입원한 폰 노이만에게, 길이 n 이하의 증명을 찾는 데 드는 걸음 수가 n이나 n²에 비례할 만큼 줄어들 수 있다면 수학자의 일을 기계가 대신할 수 있을 것이라는 편지를 보냈습니다. 오늘날의 P 대 NP 문제⁠(P versus NP problem)⁠를 가장 먼저 적은 글로 꼽힙니다. 말년의 그는 누군가 음식에 독을 넣을까 두려워해 아내가 만든 음식만 먹었고, 1977년 아내가 병원에 입원하자 먹기를 거의 그만두었습니다. 1978년 1월 프린스턴의 병원에서 굶주림으로 세상을 떠났습니다.

그의 정리는 수학 밖으로도 멀리 퍼졌습니다. 튜링과 처치를 거쳐 계산할 수 없는 문제의 이론이 되었고, 1970년의 힐베르트 10번 문제 해결과 1977년 파리스–해링턴 정리⁠(Paris–Harrington theorem)⁠처럼 자연스러운 수학 문제 안에서도 불완전성이 나타난다는 것이 차례로 밝혀졌습니다. 철학에서는 마음이 기계인지를 둘러싼 논쟁에 끊임없이 불려 나왔고, 1979년 인지과학자 더글러스 호프스태터의 『괴델, 에셔, 바흐』는 그의 자기 참조를 대중의 상상력 속에 심었습니다. 동시에 이 정리는 가장 자주 잘못 인용되는 수학 정리이기도 합니다. 그가 보인 것은 '모든 것을 알 수 없다'는 막연한 주장이 아니라, 산술을 담는 특정한 형식 체계에 대한 정확한 사실입니다.

이어지는 곳. 괴델 수와 G의 구성은 불완전성 정리에서 한 단계씩 볼 수 있고, 같은 대각선이 '어떤 프로그램이 멈출지 판정하는 프로그램은 없다'는 계산의 한계가 되는 이야기는 정지 문제⁠(halting problem)⁠에서 이어집니다. 불완전성은 인공적인 문장에만 있지 않습니다. 램지 이론⁠(Ramsey theory)⁠의 한 명제(파리스–해링턴 정리)는 참이지만 페아노 산술⁠(Peano arithmetic)⁠의 공리로는 증명할 수 없습니다. 문자열을 얼마나 줄일 수 없는지를 재는 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠에서도 같은 일이 생깁니다. 무모순이고 공리를 기계적으로 나열할 수 있는 형식 체계에는 체계마다 정해진 값 L이 있어서, '이 문자열의 복잡도는 L보다 크다'는 문장을 어느 문자열에 대해서도 증명하지 못합니다. 그런 문자열은 거의 모두인데도 말입니다. 그의 정리가 막아선 계획은 수학 전체의 무모순성을 증명하려던 힐베르트의 것이었고, 그 뒤를 이어 '기계적 절차'를 정의하고 결정 문제⁠(decision problem)⁠에 답한 것은 튜링이었습니다.

관계.

• 영향을 받음 다비트 힐베르트 — 힐베르트와 아커만이 던진 1차 논리의 완전성 문제에 박사 논문으로 답했고, 이어 힐베르트 계획이 그 방식으로는 이루어질 수 없음을 보였습니다.
• 영향을 받음 버트런드 러셀 — 불완전성 정리 논문은 러셀과 화이트헤드의 『수학 원리』를 겨냥했고, 1944년에는 러셀의 논리학을 평가하는 긴 글을 썼습니다.
• 영향을 받음 게오르크 칸토어 — 칸토어의 연속체 가설이 표준 집합론과 모순되지 않음을 보였고, 1947년 「칸토어의 연속체⁠(continuum)⁠ 문제란 무엇인가」를 썼습니다.
• 영향을 줌 앨런 튜링 — 그의 대각선 구성이 튜링의 정지 문제로 이어졌고, 그는 계산 가능성의 정의로 튜링의 분석이 가장 설득력 있다고 인정했습니다.
• 영향을 받음 고트프리트 라이프니츠 — 프린스턴 시절 라이프니츠의 저작을 깊이 연구했고, 모든 개념을 기호로 적는 그의 보편 기호법의 꿈을 진지하게 받아들였습니다.

연표.

• 1924년 빈 대학에 들어가다
• 1929년 1차 논리의 완전성 정리로 박사 논문을 쓰다
• 1930년 쾨니히스베르크 학회에서 불완전성 정리를 처음 알리다
• 1931년 불완전성 정리 논문을 발표하다
• 1932년 빈 대학에 교수 자격 논문을 내다
• 1933년 프린스턴 고등연구소를 처음 방문하다
• 1936년 빈 학파의 슐리크가 살해되다
• 1938년 아델레와 결혼하고 연속체 가설의 무모순성을 발표하다
• 1940년 시베리아 횡단 철도로 유럽을 떠나 프린스턴에 자리 잡다
• 1946년 고등연구소의 종신 연구원이 되다
• 1947년 아인슈타인, 모르겐슈테른과 함께 미국 시민권 심사를 받다
• 1949년 아인슈타인의 일흔 살 생일에 회전하는 우주의 해를 선물하다
• 1951년 첫 아인슈타인 상을 받고 깁스 강연을 하다
• 1953년 고등연구소의 교수가 되다
• 1956년 폰 노이만에게 P 대 NP 문제의 원형이 담긴 편지를 보내다
• 1974년 미국 국가 과학 훈장을 받다