괴델의 불완전성 정리(Gödel's incompleteness theorems)

먼저 낱말 몇 개를 정해 둡시다. 형식 체계⁠(formal system)⁠는 출발점으로 받아들이는 문장인 공리들과, 이미 얻은 문장에서 새 문장을 끌어내는 추론 규칙(예를 들어 'A'와 'A이면 B'에서 'B'를 얻는 규칙)이 분명하게 정해져 있어서, 주어진 증명이 맞는지를 기계가 검사할 수 있는 체계입니다. 대표적인 예가 0, '다음 수', 덧셈, 곱셈에 관한 몇 가지 공리와 수학적 귀납법⁠(mathematical induction)⁠으로 자연수를 다루는 페아노 산술입니다(주세페 페아노의 이름을 땄습니다). 체계가 무모순⁠(consistent)⁠이라는 것은 어떤 문장과 그 부정을 함께 증명하는 일이 없다는 뜻입니다. 모든 문장에 대해 그 문장이나 그 부정 가운데 하나를 반드시 증명하는 체계는 완전하다고 합니다. 정리의 이름은 여기서 왔습니다.

1931년 쿠르트 괴델은 두 가지를 증명했습니다. 자연수의 덧셈과 곱셈에 관한 기본 사실을 증명할 수 있는 무모순 형식 체계에는 참이지만 그 체계 안에서 증명할 수 없는 문장이 있다(제1 정리). 그리고 페아노 산술처럼 '증명할 수 있다'에 관한 기본 추론을 스스로 따라 할 수 있는 그런 체계는 자기 자신이 무모순이라는 것을 스스로 증명할 수 없다(제2 정리). 여기서 '참'은 실제 자연수 0, 1, 2, …에 대해 그 문장이 말하는 바가 성립한다는 뜻이고, '증명할 수 없다'는 그 체계의 공리에서 추론 규칙만으로는 끌어낼 수 없다는 뜻입니다. 흔히 '아무도 영원히 알 수 없는 진리가 있다'는 말로 옮기지만, 정리가 말하는 것은 어느 한 체계의 한계입니다. 괴델은 제1 정리를 1930년 9월 쾨니히스베르크 학회에서 처음 알렸습니다. 이 무렵 힐베르트는 수학 전체를 하나의 완전한 공리 체계에 담고, 그 체계에 모순이 없다는 것을 무한을 직접 다루지 않는 유한한 기호 조작만으로 증명하자는 계획을 내걸고 있었습니다. 수학의 바탕을 어떻게 세울지를 두고 벌어진 수학 기초론 논쟁⁠(debate on the foundations of mathematics)⁠에 대한 힐베르트의 답이었지만, 이 계획은 바란 모습 그대로는 이룰 수 없게 되었습니다.

첫 번째 열쇠는 식을 수로 바꾸는 괴델 수입니다. 기호마다 번호를 붙이고, 기호열의 j번째 기호 번호를 j번째 소수⁠(prime number)⁠의 지수로 올려 모두 곱합니다. 위의 기호를 누르면 식 끝에 붙고, 식의 기호를 누르면 지워집니다. 지금 식 “”의 괴델 수⁠(Gödel number)⁠는 = 입니다. 다른 예 한 글자 지우기 비우기

소인수분해⁠(prime factorization)⁠가 오직 한 가지뿐이므로 수에서 기호열을 되찾을 수 있습니다. 수를 끌어 바꿔 보세요: . 증명도 식들을 늘어놓은 기호열이니 수 하나가 됩니다. 그러면 'x는 번호가 y인 식의 증명의 번호다'라는 말은 x와 y 사이의 관계가 되고, 그 관계는 덧셈, 곱셈과 논리 기호('그리고', '아니다', '어떤 수가 있다' 등)만으로 적을 수 있습니다. 걸림돌이 하나 있었습니다. 증명은 길이가 제각각인 식들의 줄인데, 산술의 언어에는 '수열'이라는 낱말이 따로 없습니다. 괴델은 중국인의 나머지 정리⁠(Chinese remainder theorem)⁠로 이를 해결했습니다. 이 정리 덕분에 어떤 유한 수열이든 수 두 개 a, b로 적어 두고, i번째 항을 'a를 $1 + (i+1)b$로 나눈 나머지⁠(remainder)⁠'로 꺼낼 수 있습니다. 나머지는 덧셈과 곱셈만으로 정의되니 수열 전체를 산술 안에서 다룰 수 있게 됩니다. 이렇게 산술이 자기 자신의 증명에 대해 말할 수 있게 됩니다.

두 번째 열쇠는 자기 참조입니다. 괴델은 '번호가 ⌜G⌝인 문장은 증명할 수 없다'를 뜻하는 문장 G를 만들었습니다(⌜G⌝는 G의 괴델 수를 뜻합니다). 그 번호가 바로 G 자신의 번호입니다. 곧 G는 '나는 증명할 수 없다'고 말합니다. 문장이 어떻게 자기 번호를 품을 수 있을까요? 괴델은 '식의 빈자리에 그 식 자신의 번호를 넣은 식의 번호'를 계산하는 연산을 산술로 적고, 이 연산을 자기 자신에게 한 번 적용하는 방법으로 이런 문장을 만들었습니다. 오늘날 대각선 보조정리라 부르는 방법입니다. 가정을 눌러 바꿔 가며 따라가 보세요. 가정: .

G가 증명된다면, 그 증명이 실제로 있으니 체계는 'G는 증명할 수 있다', 곧 $\mathrm{Prov}(\ulcorner G \urcorner)$도 증명합니다. 증명을 확인하는 일은 유한한 계산이고, 체계는 그 계산을 따라 할 수 있기 때문입니다. 그런데 G는 바로 이 문장의 부정과 같은 말이므로, 체계는 G와 그 부정을 함께 증명하게 되어 모순입니다. 그러니 체계가 무모순이라면 G는 증명되지 않고, 그렇다면 G가 말하는 바가 사실이므로 G는 참입니다. 이것은 러셀의 역설⁠(Russell's paradox)⁠이나 거짓말쟁이 역설('이 문장은 거짓이다')과 같은 모양이지만, '참'을 '증명할 수 있음'으로 바꾸었기 때문에 모순 대신 증명의 한계가 나옵니다. 행과 대각선을 뒤집는 대각선 논법⁠(diagonal argument)⁠의 후손이기도 합니다. G의 부정도 증명되지 않음을 보일 때 괴델은 조금 더 강한 가정인 ω-무모순성⁠(ω-consistency)⁠을 썼습니다. 어떤 성질 P에 대해 'P(0)이 아니다', 'P(1)이 아니다', 'P(2)가 아니다', …를 하나하나 모두 증명하면서 동시에 'P를 만족하는 수가 있다'도 증명하는 일은 없다는 조건입니다. 1936년 미국 논리학자 J. 바클리 로서가 문장을 고쳐, 보통의 무모순성⁠(consistency)⁠만으로 충분하게 만들었습니다. 제2 정리는 방금의 추론 '무모순이면 G는 증명되지 않고, 따라서 G이다'를 체계 안에서 따라 하면 나옵니다. 체계가 '나는 무모순이다'를 증명할 수 있다면 G도 증명하게 되는데, 앞에서 본 대로 그러면 모순이기 때문입니다. 스스로 증명할 수 없다는 것이지 누구도 증명할 수 없다는 뜻은 아닙니다. 1936년 독일 논리학자 게르하르트 겐첸은 페아노 산술에 없는 원리(ε₀까지의 초한 귀납법⁠(transfinite induction)⁠)를 써서 페아노 산술의 무모순성을 증명했습니다.

'참이지만 증명할 수 없다'는 늘 특정 체계에 대한 말입니다. G를 공리로 더하면 새 체계에는 새 G′이 생깁니다. 모든 명제가 이렇게 곤란한 것도 아닙니다. 불 대수⁠(Boolean algebra)⁠로 다루는 명제 논리⁠(propositional logic)⁠는 진리표⁠(truth table)⁠로 모든 참인 식을 가려낼 수 있습니다. 실제 수학의 예로는 자연수보다 크고 실수⁠(real number)⁠보다 작은 크기의 무한집합은 없다는 연속체 가설⁠(continuum hypothesis)⁠이 있습니다. 괴델(1940)과 미국 수학자 폴 코언(1963)의 결과를 합치면, ZFC에 모순이 없는 한 이 가설은 오늘날 수학의 표준 바탕인 집합론⁠(set theory)⁠ 공리 체계 ZFC에서 증명도 반증도 할 수 없습니다.

이어지는 곳. 1936년 튜링은 정지 문제⁠(halting problem)⁠를 풀 수 없음을 보였는데, 이것에서도 불완전성이 나옵니다. 참인 산술 문장을 모두, 그리고 참인 것만 증명하는 형식 체계가 있다고 해 봅시다. 그러면 증명을 차례로 늘어놓다 보면 프로그램이 멈춘다는 증명이나 멈추지 않는다는 증명 가운데 하나가 반드시 나오고, 그것으로 정지 문제를 풀 수 있게 되어 모순입니다. '형식 체계'의 정의에 쓰인 '기계가 검사할 수 있다'는 말은 '튜링 기계⁠(Turing machine)⁠로 검사할 수 있다'로 정확히 읽는데, 그렇게 읽어도 된다는 근거가 처치–튜링 논제⁠(Church–Turing thesis)⁠입니다. 페아노 산술의 공리 가운데 '모든 자연수에 대해'를 증명하게 해 주는 것이 수학적 귀납법인데, 불완전성은 이 강력한 공리가 있어도 피할 수 없습니다. 괴델의 문장은 일부러 지어낸 것이지만, 1977년 영국 수학자 제프 파리스와 미국 수학자 레오 해링턴은 자연스러운 수학 명제에서도 불완전성이 나타남을 보였습니다. 램지 이론⁠(Ramsey theory)⁠의 유한 램지 정리는 '원소⁠(element)⁠가 충분히 많은 집합⁠(set)⁠에서 원소 몇 개짜리 모임마다 색을 칠하면, 어떻게 칠해도 그 안의 모임이 모두 같은 색인 큰 부분집합⁠(subset)⁠이 생긴다'는 정리입니다. 여기에 '그 부분집합의 원소 개수가 그 안의 가장 작은 원소보다 크다'는 조건을 덧붙인 명제는 페아노 산술에서는 증명할 수 없습니다. 그래도 참임을 아는 까닭은 더 강한 체계(예: ZFC)에서는 증명되기 때문입니다.