이성이란 무엇인가?

괴델 : 불완전성 정리 : 요시나가 요시마사 지음, 임승원 옮김, 전파과학사, 1993, page 163~187

1. 「불완전성 정리」의 아이디어

     (1)「리샤르의 패러독스」가 힌트

     (2) 출중한 착상

     (3) '괴델수' 의 아이디어

     (4) 귀납적 함수

2. 「불완전성 정리」의 원논문을 읽는다.

     (1) "머리말" 에 담겨진 증명의 아이디어

     (2) 「결정 불가능 명제」의 증명

     (3) 증명에 의한 '놀랄만한 결과' 란?

     (4) 「힐베르트의 프로그램」에 대한 "사망선고"

3. 「불완전성 정리」의 쇼크

     (1) 반론할 수 없고 --

     (2) "괴델 쇼크"

     (3) 노병 (베테랑) 은 죽지 않는다 --

     (4) 겐첸의 분투와 죽음

1. 「불완전성 정리」의 아이디어

(1)「리샤르의 패러독스」가 힌트

힐베르트 - 아카만의 문제 제기에 답하여 괴델이 술어논리의 형식적 체계가 완전하다는 것을 증명한 것은 1929 년 가을의 일이었다 (발표는 다음해 1930 년). 그 뒤 괴델은 이 성과에 힘을 얻어 「힐베르트의 프로그램」을 거듭 추진코자 구체적인 수학 이론의 형식적 체계에 대해서 그 무모순성이나 완전성의 증명으로 향했을 것이다.

괴델이 최초로 착수한 것은 해석학의 무모순성의 증명이었다고 일컬어지고 있다. 괴델은 이 문제를 산술 (자연수론) 을 이용해서 풀려고 하였다. 그래서 곧 산술의 공리계를 바탕으로 한 해석학의 형식화에 착수한 것 같으나 그렇게 했더니 산술에 있어서의 "진실" 의 개념이 필요하게 되는 것을 알 게 되었다.

그런데 산술의 형식적 체계에 있어서는 '진실이다라는 것' 을 잘 정의할 수 없는 것이다. 이 사실은 「리샤르의 패러독스」로부터의 직접적 귀결로서 나온다.

이것으로 계호기은 일단 파탄된 것처럼 보였다. 그러나 완전성 정리를 증명하고, 겨를도 없는 괴델의 머리 속에는 형식적 체계에 있어서 무었이 가장 중요한 개념인가 하는 확신이 있었던 것으로 생각한다. 그것이야말로 공리계에서 형식적 추론을 겹쳐 쌓아서 얻어지는 기호의 유한열로서의 '증명 가능성' 의 개념이었다. 그래서 '진실이다라는 것' 을 '증명할 수 있다는 것' 으로 바꿔 놓아 논의를 진행시켜 보면 무언가 재미잇는 결과가 얻어지는 것이 아닌가 하는 아이디어는 완전성 정리에 대한 증명의 연장선상에 자연히 나온 발상이었다고 보아도 될 것이다.

그러면 「리샤르의 패러독스」가 제기하고 시사한 사태란 도대체 무었이었던가. 여기서는 1905 년에 발표된 리샤르 자신의 원안 바로 그것들은 아니고 다음의 이야기의 전개에 바로 사용될 수 있는 형태로 고쳐 만들어 소개해 보자 (예컨대 문제로 삼는 수의 범위도 리샤프가 그렇게 한 것처럼 실수가 아니고 자연수로 생각하기로 한다).

「리샤르의 패러독스」란 이러하다.

지금의 보통의 말로 표현할 수 있는 자연수의 전체를 생각한다. '보통의 말로 표현할 수 있다' 란 정확히 말하면 '알파벳 26 문자' 를 어떤 순서로 배열한 유한 개의 '문자열' 의 의미이다. 이러한 조건 아래에서 임의의 자연수 n 에 대해서 가능한 표현의 전체를 생각하면 그 수는 고작 가산개밖에 없다. 그래서 이들의 표현에 번호를 붙여서 다음과 같이 일렬로 배열한다.

W₀(n), W₁(n), W₂(n), ……, W_m(n), …

여기서 ￢W_n(n) 을 「n 에 대한 표현으로 n 번째에 오지 않는 것」이라 정의하면 그 표현도 역시 이 리스트 (list) 속에 포함되어 있을 것이다. 즉 어떤 정해진 자연수 n₀ 가 존재하여,

Wn₀(n) = ￢W_n(n)

여기서 n 은 임의였기 때문에 이 n 에 n₀ 를 대입하면

Wn₀(n) = ￢Wn₀(n₀)

즉 「n₀ 의 n₀ 번째의 표현은 동시에 n₀ 번째의 표현이 아니다」로 되어서 모순이 되는 것이다.

이 패러독스에서는 ￢W_n(n) 이 부정적인 자기언급으로 되어 있다. 「크레타인의 패러독스」와 마찬가지 구조이다. 자기 모순에 빠지지 않을 수 없는 이유도 거기에 있다. 결국은 W_n(n) 과 ￢W_n(n) 과는 같은 수준에서 취급할 수 없는 표현인 것이다.

(2) 출중한 착상

그러나 여기서 만일 논리적인 절차는 바꾸지 않고 이들의 표현의 의미를 바꿔 읽음으로써 양자를 같은 수준에서 취급할 수 있도록 되었다고 하면 어떨까. "그 자신도 그 부정도 '진실' 이 아닌" 명제의 대신에 "그 자신도 그 부정도 '× ×' 가 아닌" 명제가 얻어져야 할 것이다. 이 '× ×' 에 '증명가능' 을 적용시킬 수 있는 것이 아닌가 하는 출중한 착상이 불완전성 정리로의 작은 한 걸음, 그러나 거대한 한 걸음으로 되었다.

'진실이다라는 것' 을 '증명할 수 있는 것이다' 로 바꿔 놓았을 때 어떠한 논의를 할 수 있는가를 「리샤르의 패러독스」에 준거해서 그 의미를 바꿔 읽으면서 구체적으로 살펴 보자 (이하의 실례는 히로세 켄, 요코다 히토마사 두 사람에 따른다).

「리샤르의 패러독스」의 W_m(n) 에서 의미를 빼내고 자연수상의 1 변수 n 에 대한 논리식의 전체를 생각한다. 논리식은 대상기호, 함수기호, 변수기호, 논리기호, 거기에다 자연수에 관한 (공리화된) 기호 등 고작 가산개의 기호를 유한 개 배열한 것에 지나지 않기 때문에 그 수는 고작 가산개밖에는 없다.

그래서 자연수를 범위로 갖는 자유변수 n 에 대한 논리식 전체에는 순번이 붙여지고 이것을 W_m(n) 의 대신에 P_m(n) 이라고 써서 다음과 같이 일렬로 배열한다.

P₀(n), P₁(n), P₂(n), ……, P_m(n), …

거듭 n 에 구체적인 수치를 넣어 이렇게 해서 얻어지는 전논리식을 다음 페이지 그림 1 과 같은 순서로 1 렬로 바꿔 배열하자.

그리고 P₀(0) 를 0 번째로 하여 이것에 번호를 붙인다. 즉

그러면 다음과 같은 간단한 계산에서 P_m(m) 은 2m² + 2m 번째로 등장하는 논리식이라는 것을 알 게 된다.

다음으로 형식적 체계에서는 '증명' 도 기호의 유한열에 지나지 않기 때문에 이들의 논리식 속에는 'n 번째의 논리식은 증명할 수 있다' 는 것을 의미하는 것이 있을 것이다. 이것을 P_rov(n) - P_rov 는 Provable (증명할 수 있는) 의 약기 - 라고 쓰자. 예컨대 어떤 논리식 Q_k 가 k 번째의 것이라 하면 「Q_k 가 증명될 수 있는 것」과 「P_rov(k) 가 증명될 수 있는 것 」과는 같은 값이다. 즉

├Q_k  ⇔  ├P_rov(k)

이제 이 P_rov(n) 의 n 에 2m² + 2m 을 대입하여 P_rov(2m² + 2m) 을 만든다. 2m² + 2m 번째의 논리식 P_m(m) 바로 그것이었기 때문에

├P_m(m)  ⇔  ├P_rov(2m² + 2m)

다음으로 P_rov(2m² + 2m) 의 부정 　￢P_rov(2m² + 2m) 을 만든다. 이것도 1 변수의 논리식이라는 것에는 변함이 없기 때문에 어떤 자연수 m₀ 가 존재하여

├P_m(m)  ⇔  ├￢P_rov(2m² + 2m)

로 되어 있을 것이다. 여기서 m 은 자유변수였기 때문에 이 m 에 m₀ 를 대입하는 것이 허용된다. 그러면

├P_m0(m₀)  ⇔  ├￢P_rov(2m²₀ + 2m₀)

좌측의논리식은 'P_m0(m₀) 가 증명될 수 있다는 것' 을, 우측의 논리식은 '2m₀² + 2m₀ 번째의 논리식 즉 P_m0(m₀) 는 증명될 수 있는 것에 대한 부정이 증명될 수 있다는 것', 바꿔 말하면 P_m0(m₀) 는 증명될 수 없는 것' 을 의미하고 있다.

결국 P_m0(m₀) 는 증명될 수 있다고 가정하면 증명될 수 없고 증명될 수 없다고 가정하면 증명될 수 있는 것으로 된다. 즉 논리식 P_n(n) 속에 '그것 자신도 그 부정도 증명될 수 없는' 것이 존재한다는 것을 보여 준 셈이다.

이와 같이 진위의 관점에서 보는 한 패러독스를 유도하는 같은 논법이 여기서는 증명도 그 부정의 증명도 할 수 없는 즉 '결정불가능' 한 논리식의 구성이라고 하는 적극적인 결과를 얻는 데에 사용되고 있다.

이 논법은 보는 바와 같이 칸토어의 대각선논법의 직접적인 응용으로 되어 있다. 그래서 전제로 된 것은 논리식에 "순번을 붙이는" 것뿐이다. 바꿔 말하면 형식적 체계의 논리식에 자연수를 일의적으로 대응시킬 수 있다면 위의 논법이 적용될 수 있고 결정 불가능한 논리식의 존재가 추론될 수 있다는 것이다.

(3) '괴델수' 의 아이디어

논리식과 자연수와의 대응이라고 하는 과제는 소위 '괴델수' 의 개념에 의해서 해결되었다. '괴델수' 의 아이디어 그 자체는 지극히 단순하다. 요컨대 상이한 논리식 즉 상이한 기호열이 상이한 자연수를 지정하고 특정의 자연수에 대해서는 그 역도 성립되는 대응을 만들어 주면 되는 것이다. 제 1 장의 말을 사용하면 형식적 체계의 논리식 전체의 집합에서 자연수 전체의 집합 속으로의 - 즉 그 부분집합으로의 - '1 대 1 대응' 을 구성한다고 하는 것이 된다.

그를 위해서는 자연수의 두드러진 특징인 '소인수분해의 일의성' 에 주목해서 대응을 구성하면 된다고 생각하는 것은 매우 자연스런 발상이라고 생각한다. 주지하는 것처럼 어떠한 자연수도 소수의 유한 개의 곱으로서 다음과 같이 일의적으로 즉 대강의 쓰는 방법으로 나타낼 수 있다.

n = 2^a3^b5^c … p_k^l … p_N^m (다만 p_k 는 k 번째의 소수)

여기서 각 소수의 지수도 마찬가지로 소인수분해를 할 수 있다.

l = 2^α3^β5^r … p_i^l … p_z^w (다만 p_k 는 k 번째의 소수)

이 소인수분해의 각 요소수의 지수에 대해서도 마찬가지로 소인수분해를 할 수 있고 이하 마찬가지로 계속되나 이 조작도 반드시 유한회로 끝난다.

이 특징에 착안해서 논리식과 자연수와의 구하는 대응을 구성하여 보자. 먼저 형식적 체계의 원시기호에 상이한 소수를 하나씩 대응시킨다. 예컨대

라고 하자 (이것은 괴델이 실제로 할당한 괴델수를 흉내낸 것이다). 기호 X 의 괴델수를 g(X) 로 쓴다면 이렇다.

g(￢) = 5, g(∨) = 7, g(A) = 17, g(B) = 19

다음으로 논리식의 괴델수를 소인수분해의 지수의 단계에 준해서 조립해 간다. 예컨대

A → B (A 이면 B)

라고 하는 논리식은

￢A ∨ B (A 가 아니다. 또는 B)

와 동치라는 것이 알려져 있기 때문에 이것을 원시기호마다 소수열의 어깨에 싣는 것이다.

g(A → B) = g(￢A ∨ B)
             = 2^g(∠)3^g(A)5^g(∨)7^g(B)
                = 2⁵3¹⁷5⁷7¹⁹

추론에 대해서도 마찬가지로 이 "어깨실음" 의 작업을 수행한다. 예컨대 앞에서 소개한 다음의 식과 같은 가장 기본적인 추론 규칙을 예로 들어서 괴델수를 구해 보자.

g(	A     A → B	)	= 2	g(A)	3	g(A→B)5g(B)
	B

			= 2	17	ㆍ	32	5	3	17	5	7	7	19	519

이 수는 만일 실제로 계산해 본다면 도대체 몇 자리 정도의 수로 되는지 상상도 할 수 없을 만큼 터무늬없이 거대한 수이다. 그러나 이 소인수분해는 일의적으로 결정되기 때문에 이 수를 거꾸로 읽음으로써 원래의 논리식을 재현할 수 있다. 그 밖의 더 복잡한 논리식에 대해서도 방법은 전혀 마찬가지다.

이것은 요컨대 암호를 만드는 방법과 같다. 형식적 체계의 정보가 괴델수로서 암호화 (코드화) 된 것이다. 역으로 괴델수로부터 원래의 논리식을 복원하는 작업은 암호의 해독 [탈 코드화] 에 해당된다 (앞 페이지의 선으로 두른 부분 참조).

이 언저리의 이야기는 매우 알기 쉬운데다 일반적으로 흥미도 돋구기 때문에 괴델의 불완전성 정리를 다룬 책이라면 어느 책에도 상세하게 소개되어 있기 때문에 여기서는 이것 이상 깊이 들어가지 않는다.

(4) 귀납적 함수

아이디어는 이것을 전부 갖추어졌다. 그러나 문제는 여기서부터이다. 이 아이디어를 수학적으로 엄밀히 정식화하지 않으면 안된다. 특히 형식적 체계 내에서의 논리식간의 관계와 그것들을 괴델수에 의해서 산술화했을 때의 자연수간의 관계가 같은 구조를 갖고 있는, 즉 그것들이 '동형' 이라는 것을 제대로 확인해 두지 않으면 모처럼의 아이디어도 쓸모없이 끝나 버린다.

괴델은 '귀납적 함수' - 엄밀히는 '원시귀납적 함수' - 의 이론을 창시함으로써 이 사이의 관계를 엄밀히 정의하였다. '귀납적 함수' 란 한마디로 말하면 계산 가능한 엄밀히 정의한다. '귀납적 함수' 란 한마디로 말하면 계산 가능한 알고리듬 (절차) 을 갖는 함수를 말한다. 즉 그 함수값을 확실히 계산하는 방법이 계산하는 방법이 존재하는 함수에 대한 것을 말한다.

괴델은 이 '귀납적 함수' 의 이론을 전개함으로써 단순히 논리식에서 자연수 속으로의 1 대 1 대응을 구성했을 뿐만 아니고 어떤 괴델 수가 주어졌을 때 그것이 어떠한 논리식에 대응하고 있는가를 알기 위한 알고리듬의 존재도 보여 주었다.

즉 괴델수에 의해서 산술화된 자연수에서의 논의 - 앞에서 본 대각선논법에 의한 결정 불가능한 명제 P_m0(m₀) 의 존재 증명과 같은 - 가 그대로 형식적 체계에서의 논의로 옮길 수 있는 것이 보증된 것이다.

이리하여 출중한 아이디어에 섬세하고 동시에 치밀한 살붙임이 이루어져 불완전성 정리를 증명한 논문이 완성된 것은 완전성 정리의 증명으로부터 1 년 후인 1930 년 10 월경의 일이었다.

2. 「불완전성 정리」의 원논문을 읽는다.

(1) "머리말" 에 담겨진 증명의 아이디어

괴델이 불완전성 정리를 증명한 논문은 1930 년 11 월 17 일에 빈 과학 아카데미의 『수학ㆍ물리학 월보』에 수히되어 다음해 1931 년 1 월 22 일에 그 잡지에 게재되었다. 「『프린키피아 마테마티카』 및 관련되는 여러 체계에 있어서의 형식적으로 결정 불가능한 여러 명제에 대해서 I」이 그것이다.

이 논문에는 상당히 긴 "머리말" 이 붙어 있고 거기서 증명의 주요한 아이디어가 개관되어 있다. 즉 형식적 체계에 있어서의 초수학의 산술화, 「리샤르의 패러독스」에 따른 결정불가능한 명제의 구성, 마지막으로 이 결정 불가능성이 '형식적 체계의 무모순성의 증명에 대한 놀랄 만한 결과를 유도하는 것' 에 대한 시사이다.

이 이야기의 순서는 이제까지 이야기한 것과 역으로 되어 있는데 그것은 이러한 것이다. 즉 이제까지 이 책에서 언급해 온 이야기는 아이디어가 탄생되는 이치, 말하자면 "발생적인" 필연성을 쫓는 것이었다. 그러나 이 논문의 모두에서 언급되고 있는 것은 이론의 "구조적인" 필연성과 그 이치인 것이다.

그러면 당장 원논문을 읽으면서 괴델의 사고를 쫓아서 체험해 가기로 하자 (번역문은 히로세 겐, 요코다 히토마사 두 사람에 따른다).

보다 엄밀하게 진행되고 있는 수학의 발전 방향은 잘 알려져 있는 것처럼 광범위한 형식화로의 길을 걷고 있다. 그 결과 어떠한 정리도 소수의 기계적인 규칙을 사용하는 것만으로 증명할 수 있다. 이제까지 만들어진 것 중 가장 이해하기 쉬운 형식적 체계는 『프린키피아 마테마티카』의 체계 (PM) 와 체르멜로 - 프렌켈의 집합론의 공리계이다. 이 두 가지 체계는 매우 이해하기 쉽고 오늘날의 수학에서 사용하는 증명 방법의 모두가 그 속에 형식화되어 있고 소수의 공리와 추론 규칙으로 환원되어 있다.

여기까지는 이를 테면 "상식" 의 확인이라고나 하는 부분일까. 여기서 괴델은 이야기를 바꿔 이 논문의 제 1 의 결과를 간결하게 언급하여 읽는 사람의 주의를 끈다.

그러므로 이들의 공리와 추론 규칙을 사용하면 그 공리계에서 형식적으로 표현되는 어떠한 수학적 문제도 결정할 수가 있다, 라고 생각하는 사람이 있을지도 모른다. 그러나 아래에 보여주는 것은 그것이 사실이 아니라는 것, 그렇기는 커녕 오히려 이들 두 가지 체계 속에는 공리에 의해서 결정할 수 없는 산술의 비교적 단순한 문제가 존재하는 것이다.

이러한 것은 만들어져 있는 체계의 특수한 성질에 따르는 것은 아니고 형식적 체계의 넓은 범위에서 성립한다. 특히 앞에서 말한 두 가지 체계에 유한 개의 공리를 추가해서 생기는 모든 체계에 대해서도 추가한 공리에 의해서 잘못된 명제가 증명되지 않는 한 역시 성립하는 것이다.

여기서 괴델은 '상세하게 이야기하기 전에 우선 증명의 주된 아이디어를, 물론 완전히 엄밀하게라는 것은 아니나, 개관하자' 라고 언급하여 먼저 형식적 체계의 산술화의 기본적 아이디어를 제출한다.

형식적 체계의 논리식은 외부에서 보면 원시기호 [변수, 논리기호 그리고 괄호나 구독점] 의 유한열이고 원시기호의 열이 의미 있는 논리식인지 아닌지를 완전히 엄밀하게 말하는 것은 간단하다. 마찬가지로 증명도 형식적인 견해로 보면 (어떤 특별한 성질을 가진) 논리식의 유한열 이외의 아무것도 아니다. 물론 초수학적인 고찰을 위해서는 어떠한 대상이 원시기호로서 선정되는가는 문제가 아니다. 그래서 여기서는 원시기호에 대해서 자연수를 사용한다.

얼마나 아무렇지도 않은 듯하게 괴델수의 아이디어가 제시되어 있는 것일까! 원주에, 「즉 원시기호와 자연수를 1 대 1 대응시키는 것이다」라고 되어 있다.

이리하여 논리식은 자연수의 유한열로 되고 [원주 : 즉 최초에 대응시킨 자연수로부터 결정되는 산술적 함수이다], 증명도는 자연수의 유한열의 유한열로 된다. 이렇게 해서 초수학적인 개념 (명제) 은 자연수 또는 그 열에 대한 개념 (명제) 으로 된다.

여기서 다시 중요한 긴 원주가 들어간다.

바꿔 말하면 위의 절차는 산술 속에 PM 의 동형상을 만드는 것으로서 모든 초수학적 논의는 이 동형상 속에서 잘 행할 수 있는 것이다. 증명을 개설할 때에 사용하는 "논리식", "명제", "변수" 등의 말에 의해서 동형상이 대응하는 대상을 항상 이해하고 있지 않으면 안된다.

여기서 '동형' 이란 '구조가 같다' 라는 의미이다. 형식적 체계의 동형상이 자연수의 부분집합으로서 받아들여진다는 것이다. 이것은 이상한 느낌도 드나 무한집합이니까 '전체가 부분과 같게 되는' 것도 가능하게 되는 것이다 (1장 참조). 뒤의 전개를 위해서 대략적인 관계를 다음 페이지의 그림 2 에 도시해 둔다.

그림 2  「불완전성 정리」의 증명의 이치

중단 된 부분부터 원논문의 인용을 계속하자.

따라서 그것들은 체계 PM 자체의 (적어도 부분적으로는) 기호에 의해서 표현할 수 있다. 특히 '논리식' '증명도', 그리고 '증명가능한 논리식' 이라고 하는 개념이 PM 속에서 정의될 수 있는 것을 보여줄 수 있는 것이다. 즉 예컨대 PM 속에 하나의 (수열의 형을 갖는 자유변수 v 를 갖는 논리식 F(v) 를 만들 수 있고 그것을 PM 의 술어의 의미에 따라서 해석하면 F(v) 는 'v 는 증명 가능한 논리식이다' 를 의미할 수 있게 되는 것이다.

여기서 말하는 F(v) 란 우리들이 앞에서 사용한 기호로는 P_rov(n) 을 말한다. 괴델은 이 논리식에 대해서 원주에서 '이 논리식을 실제로 쓰는 것은 (조금 번거롭기는 하나) 매우 쉽다' 라고 말하고 있다.

이상이 형식적 체계의 산술화에 관한 머리말이다.

다음으로 괴델은 결정 불가능한 논리식의 구성법에 대해서 그 개요를 언급하고 있다. 약간 번잡한 논의로 되고 특히 기호의 바꿔 읽음이나 그 의미하는 바를 정확히 추적하는 작업은 익숙지 않으면 조금 큰 일이다. 그러나 기본적 아이디어와 이야기의 흐름은 이미 우리들이 보아 온 「리샤르의 패러독스」의 변형판과 아무런 바뀌는 것은 없다. 세세한 점은 대충 읽고 이야기의 큰 줄거리를 파악하기 바란다.

그러면 PM 의 결정 불가능한 논리식, 즉 A 도 ￢A 도 증명 가능하지 않은 명제 A 를 다음과 같이 해서 만들기로 하자.

변수가 자연수의 형인 것과 같은 하나의 자유변수를 가진 PM 의 논리식을 단항 술어기호라 부르기로 한다. 그 단항 술어기호가 전부 어떤 방법으로 일렬로 배열되어 있다고 가정하고 n 번째의 것을 R(n) 으로 나타내자. (……) α 를 임의의 단항 술어기호라고 하자. 그리고 [α ; n] 에 의해서 단항 술어기호 α 의 자유변수를 자연수 n 을 나타내는 기호에 의해서 바꿔 놓아 만들어진 논리식으로 한다. (……)

이제 다음과 같이 해서 자연수의 집합 K 를 정의한다.

n ∈ K ⇔ ￢Bew [R(n) ; n]    (#)

(여기서 Bew (x) 는 「x 는 증명 가능한 논리식이다」를 의미한다).

Bew 는 독일어로 '증명 가능' 을 의미하는 beweisbar 의 약자이다. 우리들의 예에서는 P_m(n) 이 R(n) 으로, P_rov(x) 에 상당한다.

논리식 [S ; n] 을 PM 의 술어의 의미에 따라서 해석하면

「자연수 n 은 K 에 속해 있다」는 것을 의미하는 것과 같은 단항 술어기호 S 가 존재한다. S 는 단항 술어기호이기 때문에 그것은 어떤 R(q) 와 같은 것으로 된다. 즉 자연수 q 에 대해서

S = R(q)

로 할 수가 있다.

이 q 를 사용하면 [R(q) ; q] 가 결정 가능하게 된다고 하는 시나리오는 이미 낯익은 것이다. 괴델의 증명을 보아 두자.

(2) 「결정 불가능 명제」의 증명

먼저 명제 [R(q) : q] 가 증명 가능하다고 한다. 그러면 이 명제는 참일 것이다. 그러나 정의에 따르면 그 경우에는 q 는 K 에 속해 있고 (#) 로부터 ￢Bew[R(q) : q] 가 성립하게 되나 이것은 가정에 반하고 있다.

또 한편 [R(q) : q] 의 부정이 증명 가능이었다고 하면 ￢(q ∈ K), 즉 Bew[R(q) : q] 가 성립한다. 그러나 [R(q) : q] 가 증명 가능하다는 것은 가정에 의해서 그 부정의 경우와 마찬가지로 또한 불가능하다.

이렇게 해서 개략적인 스케치를 준 후 괴델은 이 증명과 패러독스와의 관계에 언급하여 다음과 같이 말한다.

이 논의는 리샤르의 패러독스로부터 유추하면 알기 쉽다고 생각한다. 또한 「거짓말쟁이의 패러독스」와도 밀접하게 관련이 있다, 라고 하는 것도 (……) 이것은 자신에 대해서 '자신이 증명 가능하지 않다' 라고 주장하고 있는 명제이기 때문이다. [원주 : 겉보기와는 달라 이 명제는 악순환이 생기지 않는다, 라고 하는 것은 이 명제는 우선은 어김없이 정의된 논리식이 증명 불가능하다는 것을 주장하고 있다. 그리고 (말하자면 우연히) 이 논리식은 바로 그 명제 그 자체를 표현하고 있는 것이다, 라고 하는 것뿐이다].

그 뒤 괴델은 이 결정 불가능 명제의 구성법이 '임의의 형식적 체계에 대해서 명확히 적용할 수 있다는' 것, 및 그 증명을 엄밀히 행할 때의 주의사항을 말하고 이 "머리말" 을 다음과 같은 시사적인 말로 맺고 있다.

[R(q) : q] 의 내용이 자기 자신의 증명 불가능성을 언급하고 있다고 하는 것에 주의하면 [R(q) : q] 가 참이라는 것은 즉각 유도할 수 있다, 라고 하는 것은 [R(q) : q] 는 정말 증명 불가능 (결정 불가능) 이기 때문이다.

따라서 PM 으로 결정 불가능한 명제는 초수학적으로 생각하면 결정가능으로 된다. 이 기묘한 입장을 엄밀히 분석하면 형식적 체계의 무모순성의 증명에 대한 놀랄 만한 결과를 유도하는 것으로 되나 상세한 것은 논문의 마지막에서 논의하자.

여기서 "머리말" 은 끝나고 '위에서 개관한 증명을 엄밀히 진행시키게' 된다. 그러나 여기서는 너무 길어지기 때문에 생략하지 않을 수 없다. 다행히 이 증명은 일본어역도 영역도 간단히 입수할 수 있기 때문에 흥미와 시간과 그리고 무엇보다도 인내력이 있는 분은 꼭 도전하여 보기 바란다.

다만 뒤에 원망듣지 않도록 미리 말해 두는데 논문의 태반은 귀납적 함수의 논의에 의한 형식적 체계의 산술화의 엄밀한 정식화로 충당하고 있다. 46 개나 되는 함수의 정의가 연달아 계속되는 것이다.

읽으면서 위가 아프게 될 법한 논술이 계속되는 것인데 사실은 괴델도 이 논문의 집필로 완전히 위가 나빠져 매일 밤 잠을 못이뤄 쇠약해져서 속편을 쓸 형편은 아니었다고 하는 과장된 에피소드도 이야기로 전해지고 있다 (이것은 아마 꾸며낸 이야기겠지만 …).

그래서 일약 논문의 마지막의 '놀랄만한 결과' 와 '속편' 의 화제로 이야기를 진행시킨다.

(3) 증명에 의한 '놀랄만한 결과' 란?

논문의 최종의 제 4 절에서 괴델이 제출한 결과란 「증명의 개요」와 함께 서술한 「정리 XI」를 말하고 그 내용은 요약하면 다음과 같은 것이었다.

정리 XI [산술을 포함하는 귀납적이고 무모순의 체계 P 에 있어서는] P 의 무모순성은 P 가 무모순인 한 P 로는 증명 가능하지 않다 (물론 P 가 모순되어 있으면 모든 명제는 P 로 증명 가능하다).

같은 조건하에서 「결정 불가능한 즉 그 자신도 그 부정도 증명할 수 없는 것과 같은 명제가 그 체계 내에 반드시 존재한다」라고 하는 이 논문의 최초의 주장을 「괴델의 제 1 불완전성 정리」라 부르는 것에 반해서 이 [정리 XI] 즉 「산술을 포함하는 형식적 체계의 무모순성은 그 체계내에서는 증명할 수 없다」라는 주장은 오늘날 「괴델의 제 2 불완전성 정리」라 부르고 있다.

(4) 「힐베르트의 프로그램」에 대한 "사망선고"

「힐베르트의 프로그램」의 궁극적 목표는 온갖 수학이론의 무모순성을 증명하여 전수학에 무모순성이라는 새로운 「절대적 진리」의 확고한 기반을 부여하는 것에 있었다. 그 의미에서 말하면 이 「괴델의 제 2 불완전성 정리」는 "힐베르트의 꿈" 이 영원히 못다 이루는 꿈이라는 것을 알리고 있다. 「힐베르트의 프로그램」에 대한 사망선고와 같은 것이다.

그러나 괴델은 다음과 같이 말하여 힐베르트의 뜻을 옹호하고 있다.

(이 결과는) 힐베르트의 형식주의적 견해를 반박하는 것은 아니다, 라는 것에 주의하기 바란다. 이 견해는 무모순성의 증명을 유한의 입장에서 행한다고 하는 것만을 필요조건으로서 인식하는 것이어서 형식적 체계 (의 내부) 에서는 표현할 수 없는 (확장된) 유한의 입장에서의 증명의 존재는 확신할 수 있기 때문이다.

(  ) 안은 나의 보충이다. 그건 그렇다 하더라도 기묘한 발언이라고는 생각하지 않는지? '유한의 입장' 은 형식적 체계를 그것 자체로 자기완결시키기 위해 요청된 규법이었을 것이다. 체계 밖의 수단을 채용하지 않으면 안되는 것과 같은 무턱댄 확장은 본질적으로 '유한의 입장' 의 야금야금식의 해체로 연결될지도 모른다.

그래서 이 논평은 괴델의 본심이라기보다도 헬베르트와 그 학파를 의식한 상당히 정치적인 것이 아니었는가 라고도 일컬어지고 있다.

「속편」의 문제에 대해서도 마찬가지다. 이 논문의 마지막은 「속편」 - 만일 쓰여져 있다고 하면 「『프린키피아 마테마티카』및 관련되는 여러 체계에 있어서의 형식적으로 결정 불가능한 여러 명제에 대해서 II」라고도 제목을 붙였을 것이나 - 의 예고로 끝나고 있다.

이 논문에서는 전체로서 체계 P (P 란 PM 에 페아노의 공리계를 부가한 형식적 체계를 말함) 에 논의를 한정시켜 그 밖의 체계에 대해서는 그 적용을 지적하였을 뿐이었다. 그 결과가 완전히 일반성을 가진 주장과 증명은 곧 이어서 멀지 않아 출판될 것이다. 그 논문에서는 여기서는 대략적으로 밖에는 행하지 않았던 정리 XI 의 증며에 대해서도 상세히 할 작정이다.

1931 년의 논문은 여기서 끝난다. 그리고 앞에서 말한 것처럼 이 논문은 결국 쓰여지지 않고 끝나 버렸다.

3. 「불완전성 정리」의 쇼크

(1) 반론할 수 없고 --

괴델이 불완전성 정리에 논문의 「속편」을 쓰지 않은 것은 어째서였을까. 다케우치 가이시 교수는 '사실은 다음과 같다' 라고 하여 이렇게 언급하고 있다.

괴델은 힐베르트학파의 맹렬한 반발을 예기하고 있었다. 따라서 괴델의 의도는 힐베르트학파의 반론을 보고 그 반론을 설득하는 형태로 쓰려고 한 것이다. 그런데 괴델은 II 를 쓰지 않고 끝나 버렸다. 실제로는 힐베르트학파는 괴델의 논문을 즉각 이해하여 아무런 반론도 하지 않았던 것이다.

그러면 왜 힐베르트학파로부터는 아무런 반론도 나오지 않았을까. 그 이유는 힐베르트 자신, 이라고 하는 것보다 「힐베르트의 프로그램」바로 그것의 기본 이념에 있었던 것 같다.

힐베르트는 모든 수학이론을 형식화하여 형식적 체계에서의 "산술" 에 의해서 그 무모순성을 증명할 수 있다, 라는 아이디어를 갖고 있었다. 힐베르트에 있어서 초수학이란 산술 이외의 아무것도 아니었던 것이다.

이와 같은 '힐베르트가 평소 말하고 있던 것, 생각하고 있던 것을 가장 정직하게 실행한다' (다케우치 교수) 것이 바로 괴델이었던 것이다. 그리고 '운명의 얄궂은 부분이지만 힐베르트학파의 밖에 있는 괴델이 힐베르트의 의도를 가장 충실하게 수행하여 힐베르트가 목표로 한 것과는 정반대의 것을 증명해 버린 (다케우치 교수) 것이다.

(2) "괴델 쇼크"

힐베르트학파의 사람들의 입장에서 보면 이것은 역시 상당히 충격적이고 억울한 일이었음에 틀림없다.

베르나이스는 '우리들이 하려고 생각은 하면서도 게을러서 하지 않은 것을 부지런한 괴델이 수행하였다' 라고 자기 비판하고 폰 노이만은 무모순성의 증명을 주제로 해서 행하고 있던 강의를 중단해 버린다. '괴델의 결과로 이 강의도 무의미하게 되었으니 그만둔다' 라고 하는 것이다.

그러나 누구보다도 더 절망의 구렁텅이에 빠지게 된 것이 힐베르트 그 사람이었을 것임은 쉽게 상상이 된다. 『기하학의 기초』이래 30 년 동안이나 끊임없는 노력과 투쟁끝에 겨우 스스로의 프로그램이 막 궤도에 오른 것같이 보이던 참에 일어난 "사건" 이었기 때문이다.

한때 프레게는 오랜 세월을 들인 평생사업이 바야흐로 완성되려 던 그때에 러셀로부터 편지를 받았다. 그때의 심경을 프레게는 다음해에 간행한 『산술의 기본법칙 II』의 「후기」에서 이렇게 쓰고 있다.

과학자가 그 일을 마치려고 하는 바로 그때에 그 일의 기초를 놓쳐 버리는 사태에 조우하는 것만큼 바람직스럽지 못한 것은 다시는 없을 것이다. 이 책이 인쇄에 들어가려고 한 바로 그때 나는 러셀씨로부터 한통의 편지를 받은 것이다.

힐베르트도 아마 이때의 프레게와 똑같은 인생의 쓴맛을 보았을 것이다. 괴델의 결과를 알 게 된 힐베르트는 당초 매우 기분이 나빴고 단지 무턱대고 화를 내며 '어떻게 할 수 없는 기분을 억누룰 수 없었던' (C. 리드) 것 같다. 머리로는 이해가 되어도 심정적으로는 인정하기 싫은 사실이라는 것이 누구에게도 하나쯤은 있는 법이다.

'그이 (=힐베르트)' 의 연구 생활에서 마지막의 이 위대한 작업에 그이를 싫증남이 없이 몰아세우고 있던 인간의 사유 능력에 대한 한도를 모르는 신뢰의 마음은 오히려 그이에게 있어서 괴델의 결과를 받아들이는 것을 심리적으로 거의 불가능한 것으로 하였다' 라고 전기 작가는 쓰고 있다.

(3) 노병 (베테랑) 은 죽지 않는다 --

그러나 러셀의 편지 후 새로운 작업에 일체 손을 대는 일이 없었던 프레게와는 달리 늙은 힐베르트는 온힘을 다하여 이 좌절감을 극복하고 '머지 않아 이 문제에 건설적으로 몰두하기 시작' 하였다. 그리고 3년 후인 1934 년에 간행된 베르나이스와의 공저 『수학의 기초 I』의 서문에서 힐베르트는 다음과 같이 써서 스스로의 프로그램에 대한 반성과 집착을 표명하고 있다.

괴델의 정리에 의해서 수학의 기초 부여에 대한 나의 프로그램이 쓸모없게 되었다고 하는 의견은 완전히 잘못이라는 것이 판명되었다. 괴델의 정리는 무모순성의 증명에 유한의 입장을 더 날카롭게 사용하지 않으면 안된다는 것을 말하고 있을 뿐이다.

이렇게 일방적으로 단정함으로써 힐베르트는 다른 사람에게는 이해가 되지 않아도 적어도 늙고 상처 입은 자기의 마음에만은 납득시킬 수 있었는지도 모른다. 다케우치 교수는 '허세를 부린 표현 속에 오히려 힐베르트의 슬픔을 본다' 라고 감상을 말하고 있다.

힐베르트가 가장 빠른 시기에 목표로서 내세운 '산술의 무모순성의 증명' 은 이렇게 해서 엄밀한 의미에서의 '유한의 입장' 으로부터는 원리적으로 증명 불가능한 것이 명백히 되어 버렸으나 "확장된" 형태로서의 증명은 힐베르트의 수정노선에 따른 형태로 1936 년에 겐첸의 손에 의해서 실현되었다.

(4) 겐첸의 분투와 죽음

여기서 겐첸은 「초한귀납법」이라고 부르는 방법을 사용해서 무모순성의 증명에 성공하고 있다. 이것은 자연수보다 훨씬 큰 초한순서수로까지 귀납법을 확장하여 그 수준에서 '유한의 입장' 을 사수하려고 하는 것이다. 물론 괴델의 결과로부터 하는 수 없이 나온 "고육지책" 이기는 하였으나 '괴델 이후' 에 이룩된 '증명론' 의 최초의 큰 성과였음에는 틀림없다.

게하르트 겐첸은 1909 년생으로서 1934 년부터 힐베르트의 조수로 근무하고 있었다. 정기적으로 힐베르트의 집을 방문하여 노대가의 부탁에 따라 독일의 시인 쉴러 (Schiller) 의 시를 큰 소리로 낭독하였다고 한다. 1943 년부터 프라하의 독일대학에서 강의를 맡고 있었으나 거기서는 비극적인 최후가 기다리고 있었다.

'1945 년 5 월 그와 그의 동료들은 새로운 권력자의 관리하에 놓여져 8 월 4 일 당시를 지배하고 있던 혼란 속에서 수개월에 이르는 격심한 육체적 고통을 받은 후 수용소의 딱딱한 나무침대 위에서 영양실조로 비참한 최후를 마치게' (구라다 레이지로 씨) 된 거싱다. 향년 불과 35 세. 한창 일할 나이의 갑작스런 불행이었다.

그런데 우리들의 주인공도 생의 최후는 '영양실조' 로 죽음을 맞이하게 된다. 전대미문의 영광에 싸인 가운데에서의 고독한 '아사' 였다. 그런 그렇다 하더라도 불완전성 정리의 증명이라고 하는 전인미답의 위업을 이룩한 사람이 왜 '아사' 를 선택하지 않으면 안되었던 것일까. 다음장에서는 사적인 면에서 이 천재의 비밀에 다가서 본다.

괴델 불완전성 정리 : 요시나가 요시마사, 임승원 옮김 : 전파과학사