괴델의 불완전성의 정리

먼저 컴퓨터에 대해 이야기하기 전에 컴퓨터가 할수있는 일. 즉 계산 가능성에 대해 알아야
한다. 이 계산 가능성에 대해선 괴델의 불완전성의 정리에서 잘 나와있다.
읽다보면 알겠지만 힐베르트의 완전성 증명에 대해 괴델의 불완전성 정리가 이를 답변하고
이에 처치 튜링이 계산가능한 것에 대한 이론을 발표함으로서 컴퓨터의 기초가 완성되게
되었다.

먼저 불완전성의 정리에 대해..

Wikipedia : Gödel's incompleteness theorems : 수리논리학에서 불완전성정리는 1930 년에 Kurt Gödel 이 증명하여 두차례에 걸쳐 발표되었다. 단순화 시키면, 첫 번째인 제 1 불완전성 정리는 다음과 같다.

기초적인 산술을 충분히 강력하게 허용하는 어떤 무모순의 수학 형식 시스템에서도, 그 시스템내에서 증명될 수도 없고 반증될 수도 없는 자연수에 대한 문장을 만들 수 있다. (in any consistent formal system of mathematics sufficiently strong to allow one to do basic arithmetic, one can construct a statement about natural numbers that can be neither proven nor disproven within that system.)

이러한 맥락에서, 수학의 형식 시스템은 공리의 recursive set 을 가지는 공리계이다. 마찬가지로 그 시스템의 정리들은 튜링머신에 의해 생성될 수 있다. 그 시스템에서 증명되거나 반증될 수 없는 문장은 실제로 자연수에 대해 주장하는 것을 가진다는 의미에서 더더욱 참이다 (The statement which cannot be proven nor disproven in the system is furthermore true in the sense that what it asserts about the natural numbers in fact holds). 그 시스템이 참인 문장을 증명하는데 실패한다면 그것은 불완전 (incomplete) 이라고 말해진다. 달리 말하면, 괴델의 제 1 불완전성 정리는 어떤 충분히 강력한 수학 형식 시스템도 inconsistent 이거나 incomplete 하다는 것이다.

괴델의 제 2 불완전성 정리는 시스템 자체내에서 최초의 증명을 형식화하여 증명된 (proved by formalizing part of the proof of the first within the system itself) 것으로서 다음과 같다.

어떠한 충분히 강력한 무모순 시스템도 그 자신의 무모순성을 증명할 수는 없다. (any sufficiently strong consistent system cannot prove its own consistency)

이것은 Hilbert 의 두 번째 문제 ("수학은 모든 수학적 진리여부가 유도될 수 있는 공리의 consistent set 으로 환원될 수 있다" 는 것을 증명하는 문제) 에 대한 답변이다. .....

인공지능과 컴퓨터의 한계 : 김도형 : ...... 컴퓨터는 세상의 모든 문제를 풀 수 있다고 생각하십니까? 아마도 당장 부정적인 대답이 돌아올 법 합니다. 그렇습니다. 우리가 일상 생활에서 끊임없이 만나는 정서적 문제가 컴퓨터에 의해 해결될 수 있으리라고는 생각되지 않습니다. (설령 먼 미래라고 하더라도 말이죠.) ...... 그러면 문제의 정의를 다소 제한해 봅시다. 수학적으로 엄밀히 기술되는 문제들은 예외없이 컴퓨터에 의해 풀 수 있을까요? 질문이 이렇게 되면 앞서의 질문보다는 대답하기가 훨씬 신중해질 것 같습니다. ....... 답을 말씀드리지요. "풀 수 없습니다!" 이러한 결론이 내려지기까지의 역사를 살펴보는 것이 아마 도움이 될 것입니다. ...... 컴퓨터 능력의 한계에 관한 많은 연구 결과는 20 세기초에 수리논리학 (mathematical logics) 분야에서 수행된 것입니다. 따라서 우리가 지금 사용하는 컴퓨터의 능력은 컴퓨터가 발명되기 전부터 충분히 예견되고 있었습니다. ..... 20 세기가 시작될 무렵, 수학자 Hilbert 는 어떤 수학적인 명제가 입력으로 주어질 때 이의 참과 거짓을 알아내는 알고리즘을 찾고자 하는 일종의 `수학 자동화' 연구를 시작하였습니다. 그후 1931년에 이 방면의 연구에서의 금자탑이라고 할 수 있는 쿠르트 괴델 (Kurt Godel) 의 논문이 발표되었습니다. 즉 그러한 알고리즘은 존재할 수 없음을 증명한 유명한 `불완전성 정리(Incompleteness Theorem)' 를 발표한 것입니다. 그의 결과를 간단하게 설명하면, 모든 수학적인 논리 체계에는 그 논리 자체로써는 증명할 수 없는 참인 명제들이 존재한다 는 것입니다........

수학에서 참이란 무엇인가? 수학은 무모순한가? 수학이 무모순하다면 그것은 증명가능한가? 20 세기초 제기된 이같은 일련의 물음에 대해 명쾌한 답을 준 것은 실로 무명의 수학자 Kurt Gödel 이며 그의 나이 불과 25세 때이다. 그가 빈 과학아카데미의 "수학.물리학월보"에 한 편의 논문을 발표한 것은 1931년의 일이다. 빈 대학에 취직 논문으로 제출된 이 논문은 후일 학계와 많은 사상가를 놀라게 한 불완전성 정리(incompleteness theorem)에 관한 것이었다.

그 당시만 해도 그 내용이 난해하여 몇몇 소수의 전문분야의 학자외에는 이해하지 못하였다. 그러나 오늘날에 와서는 수학자 외에도 철학자, 컴퓨터의 전문학자, 인지과학자 등 여러 인접학문 분야 에서도 이 정리가 다양하게 인용되고 있다. 이 연구로 괴델은 1938년 이후 프린스턴 대학교 고급학술연구소의 종신 연구원으로 초대받게 된다. 1952년 하바드 대학교에서 명예학위를 받을 때, "그는 현대논리학에서 가장 중요한 진보를 이루게 하는 데 기여한 사람의 하나다." 라는 찬사를 받았다. 당시 미국 최고의 지성으로 알려진 프린스턴의 연구소장 오펜하이머(J.R. Oppenheimer)도 "괴델의 이 연구는 인간의 이성 일반에 있어서 한계라는 것의 역할을 명확히 한 것이다." 라고 극찬하였다.

괴델이 얻은 정리는 순수수학과 논리학 일반에 있어 가장 심원한 연구업적의 하나가 된다는 평을 받아 마땅하거니와 그 결과는 참으로 학계의 큰 충격이었다. 왜냐하면 그것은 우리 모두가 막연하게나마 믿고 있었던 논리학과 수학의 기본 원리의 절대적인 진리성에 대한 확신을 바꾸게 하였기 때문이다. 1931년 이전까지는 기하학에서 유크리트의 공리와 같이 모든 수학적인 이론체계가 내부에서 모순없이 몇개의 기본 공리를 정하고 이로부터 모든 정리가 도출될 수 있는 연역적 체계화가 가능할 것으로 기대하였다. 그러나 괴델의 불완전성정리는 그같은 우리의 기대에 상반되는 결과를 얻게 되어 이를 수학에서의 패러다임(Paradigm) 또는 유크리트의 패러다임이라 할 수 있다.

다시 우리는 여기서 잠시동안 몇 가지 문제를 생각해 보기로 하자. 수학에서 증명된 명제는 항상 참이라고 할 수 있는가? 수학의 이론은 모순이 없다는 보장은 할수 있는가? 앞으로 우리 인간은 수학에 관한 어떠한 문제도 언젠가는 반드시 풀 수있을 것인가? 수학자 중에는 수학에 관한 이같은 물음에 대한 답을 구하기 위해 노력하는 학자들이 있다. 이 물음은 수학의 기초에 관한 문제다. 이러한 과제를 연구하는 분야를 수학기초론(Foundation of mathematics)이라 하며 이는 괴델의 불완전성정리를 기초로 하여 1950년대에 새로이 형성되었다. 따라서 이는 수학적 진리의 기초인 근거를 규명하려는 학문이라고도 볼 수 있다. 그러면 괴델의 불완전성 정리의 내용이 무엇인가에 대해 알아보기로 하자.

▶ 괴델의 불완전성정리의 내용

수학을 몇 가지의 다양한 분야로 분류할 때 각 분야에는 각기 고유한 개념과 용어가 쓰인다. 우리가 잘 알고 있는 기하학을 보면, 공리란 그 분야에서 쓰이는 원시개념에 관한 기본되는 성질임을 알 수 있다. 현대 수학의 모든 분야가 집합론으로부터 구성할 수 있다는 사실은 이미 우리의 상식이다. 이는 집합론이 수학에 있어 가장 기초가 되는 이론이라는 뜻으로도 이해할 수 있다. 여기서 다시 다음 문제를 잠시 생각해 보기로 하자.

수학에서 쓰이는 공리들은 오늘날까지 알려진 것 외에 더 있을 수 없는가? 즉,아직도 발견하지 못한 수학의 원리가 남아 있어서 장차 새로이 발견될 여지가 남아 있을 것인가? 이러한 물음에 대해 생각해 보기로 하자. 집합론이 수학의 기본 이론이기 때문에 앞의 물음은 "집합론의 공리는 지금까지 알려진 것 외에 또 더 없을까?"로 할 수 있다. 이를 다시 집합론과 논리학으로 나누면 다음과 같이 정리할 수 있다. 첫째로, 논리학의 기본 원리 즉, 논리학의 기본 법칙은 현재까지 알려진 것 외에 더 없을까? 둘째로, 집합론의 기본 원리 즉 공리는 지금까지 알려진 것 외에 없을까? 즉, 현재의 집합론은 완전(complete)한가?

이 두 물음 모두에 대해 괴델은 그 답을 우리에게 제시해 주고 있다. 첫번째 물음에 대해 괴델은 24세 때 빈 대학교에 제출한 학위 논문에서 술어논리의 완전성(completeness)정리를 통해 긍정적으로 답하였다. 즉, 그의 완전성 정리에 따르면 "술어논리는 완전하다. 그러므로 술어논리 체계에는 지금 우리가 알고 있는 원리 외에는 장차 더 새로이 발견될 것이 없다." 바꿔 말하면, 앞으로 기본 원리인 술어 논리학에서의 공리는 영원히 새로이 발견될 것이 없다는 뜻이 된다. 여기서 어떤 이론체계가 완전(complete)하다는 뜻은 그 체계에서 참인 명제는 반드시 공리로 부터 연역(증명)된다(즉, 정의가 된다)는 뜻이다. 반대로, 어떤 이론체계가 불완전하다(incomplete)는 뜻은 그 체계에 있어 참인 명제가 그 체계의 공리로부터 연역되지 않은 경우가 있다는 뜻이다. 괴델은 산술을 포함하는 무모순인 어떠한 체계도 완전하지 않다는 결과를 얻었다. 이를 괴델의 불완전성정리(Incompleteness Theorem)이라 한다.

다음 두번째 물음에 대해서는 괴델이 부정적인 답을 얻었다. 그 내용은 "현재의 산술체계가 무모순하면 그 체계는 불완전하다"로 정리할 수 있다. 즉, "그 체계의 어떠한 명제가 참이지만, 그 명제와 그것의 부정명제 모두가 증명되지 않은 명제가 존재한다."는 뜻이다. 사실은 이 정리를 제1불완전성정리 라고 한다. 여기서 어떤 이론체계가 무모순하다는 것은 그 체계에 속하는 어떤 명제에 대해서도 그 명제와 그것의 부정명제 모두가 증명되는 경우가 없다는 뜻이다. 이와 반대일 경우, 즉 한 체계에서 어떤 명제와 그것의 부정명제 모두가 증명이 가능하면, 그 체계는 모순된다고 한다. 한 이론 체계를 이루는 데 있어 그 체계의 무모순성은 가장 기본 되는 요청의 하나다. 산술체계는 집합론으로부터 오직 논리에 의해서만 체계화시킨 것이며 몇 개의 공리로부터 모든 정리를 도출하는 연역체계라고 할 수 있다. 집합론으로부터 현대 수학의 모든 체계가 구성되기 때문에, 제1불완전성정리에서 "…어떠한 명제가 참이지만… 존재한다" 라고 주장하는 바로 그 <어떠한 명제>란 도대체 어떤 명제일까에 대해 설명해 보기로 한다.

가령 그 같은 명제를 P라고 하자. 그러면 명제 P의 실질적인 내용을 "P는 증명되지 않는다"라고 하자. 그러면 P는 그 자신에 대해 언급하는 매우 특이한 속성을 갖는 명제다. 그러면 여기서 이 명제 P가 증명 가능하지 않음을 증명할 수 있다. (지면 관계로 증명과정은 생략한다.) 그런데 일 반적으로 눈(雪)이 흴 때 명제 "눈은 희다"가 참이라 할 수 있다는 대응설적 진리론에 따라, 실제로 명제 P가 증명되지 않음으로 "P는 증명되지 않는다" 라는 내용의 명제 P는 참이라고 할 수 있다. 즉, 앞에서 어떤 명제라고 지칭한 그 명제 P는 "참이지만 증명되지 않은 명제"가 된다는 사실을 알 수 있다.

이 결과는 참으로 충격적이었다. 수학에서 이 정리를 얻기 이전까지는 참인 모든 명제는 당연히 증명된다는 인식이 지배적이었기 때문이다. 우리가 당연시 해온 이같은 인식을 바꿔놓은 괴델의 제1불완전성정리의 결과로, 수학에서의 참이란 무엇이며 그것을 무엇이라고 이해하여야 하는가 라는 의문을 다시 묻게 한다.

괴델의 제2불완전성정리 또한 우리의 통념과 기대를 벗어나게 하였기 때문에 이것에 의한 충격도 적지 않았다. 일반적으로 우리들 모두는, 수학이라는 학문이 절대적인 진리의 규명만을 추구한다고 인식하고 있으며, 거기서는 "대체로 옳다"와 같은 개연적 판단이 배제되고 절대적인 판단만을 요구한다고 인식하고 있다. 따라서 당연히 수학에서는 모순이 일어나지 않을 것으로 볼 뿐만 아니라, 수학의 무모순성의 증명이 가능할 것으로 기대하게 된다. 그러나 괴델은 그의 제2불완전성정리에서 이같은 기대에 상반되는 결과를 얻었다.

그의 제2불완전성정리에 따르면 "자연수론을 포함하는 공리론적 이론체계(수학의 대부분의 이론체계가 이에 해당됨)가 무모순하면, 그 체계의 무모순성을 그 체계 안에서는 증명할 수 없다." 이 정리를 좀 더 알기 쉽게 통속적인 표현으로 바꾼다면 "자기 자신이 정신적 이상이 없다는 사실을 자기 자신으로서는 그것을 증명해 보일수가 없다."와 같다고나 하겠다. 불완전성정리에 연관되는 제1불완전성정리와 무모순성에 연관되는 제2불완전성 정리의 모두가 수학적 인식의 본질과 매우 깊은 관련성이 있음은 명백하다. 때문에 그것의 의의는 실로 크다 할 수 있다.

▶ 힐베르트의 계획

다음으로는 괴델의 두 정리가 도출되기까지의 배경을 먼저 설명한 후, 역사상 전혀 새로운 수학적인 증명법이라는 평을 받았으며 또한 그의 착상의 관건이 되는 괴델수에 대하여 설명하기로 한다.

약 2000년에 걸쳐 수학이 꾸준하게 발전되어오면서 19세기 말에 이르러 몇 가지 심각한 역설(paradox)이 수학의 이론에서 발견되었다. 이를 극복하기 위한 수학자들의 노력에서 "수학에는 과연 모순이 없는 것일까?"라는 수학 기초에 관계되는 의문이 일어나게 되었으며, 이로부터 수학에 대한 반성이 절실하게 요구되었다. 이 문제를 위해 초기에는 몇 가지 방법이 역설을 극복하기 위한 방안으로 시도되었으나, 모두가 충족되지 못했다. 결국 마지막으로 이 수학의 무모순성이라는 문제의 증명방법론을 학계에 제시한 사람은 힐베르트(David Hilbert) 였다.

그는 무엇보다 먼저 수학을 완전히 형식화해야 한다고 주장하였다. 즉, 수학에 쓰이는 모든 기호, 명제, 식, 증명 등의 표현을 의미가 없는 기호에 의해 어떤 규칙에 따라 나열한 기호의 묶음이나 그러한 묶음의 열로 보자는 태도다. 여기서는 가령, 공리로부터 정리를 연역하는 것도 하나의 기호의 열로부터 다른 기호의 열로 규칙에 따라 변환하는 것으로 본다. 이같은 방법으로 수학을 보는 입장을 형식주의(formalism)라 한다.

수학을 굳이 이와 같이 형식화하는 주된 이유는 무엇보다도 의미나 개념을 떠나서 논리의 연관성을 뚜렷하게 부각시켜 무모순성과 같은 수학체계의 논리적인 특성을 규명할 수 있게 하기 위한 것이다. 의미가 전혀 없는 수학형식체계의 어떤 표현이나 수학체계 자체에 대해 의미있는 어떤 주장을 하였다면, 그 주장은 형식체계에 속하지 않는다. 그러한 경우, 이를 메타수학(metamathematics)에 속한다고 한다.

즉, 메타수학적 주장이란 형식화된 수학체계의 기호나 표현에 관한 어떤 주장이다. 가령, 무의미한 부호나 기호들로 나타낸 표현 "1+2=3" 은 수학의 형식체계에 속하지만, 이 표현에 관한 주장인 "1+2=3은 수학의 한 명제다" 는 메타수학적 표현이다. 힐베르트는 수학과 메타수학을 엄격히 구별하는 이러한 기본적인 생각에서 수학체계 내부의 무모순성을 증명하려고 계획했다. 그는 완전히 형식화한 수학체계의 표현에 대해 순수한 구조적 특성의 분석에 의해 그것의 무모순성을 실질적으로 증명하고자 했으며, 이러한 그의 계획을 힐베르트의 계획(Hilbert program)이라 한 다.

이러한 그의 계획을 실현시킨 좋은 실례로는, 논리학의 기초가 되는 명제논리학을 들 수 있다. 그러나 이 체계는 지극히 간단한 기호와 형식규칙만으로 구성되었기 때문에 산술체계조차 그 안에 수용할 수 없었다. 원래의 힐베르트 계획대로라면 그러한 규모의 제한 없이 좀더 포괄적인 넓은 체계에 대해서도 적용할 수 있어야 했다. 수학의 무모순성을 증명하기 위해서는 수학의 가장 기본이 되는 산술체계의 무모순성이 그의 계획대로 실현되어야 했다.

그런데 1910년 화이트헤드(Alfred Whitehead)와 러셀(Bertrand Rursell)은, 수학이 논리학의 일부에 불과하다는 그들 의 철학인 논리주의 (logism) 를 제시하기 위해 세기적 명저 수학원리(Principia Mathematica) 를 이미 출판해놓고 있었다. 이 책에서 그들은 논리학이나 산술을 포함한 수학을 기술하는 포괄적인 기호체계를 역사상 최초로 발전시켰으며, 또한 수학 증명에 쓰이는 형식적 추론규칙의 대부분을 명확한 형태로 제시하였기 때문에 필수적인 책이 될 수밖에 없었다. 괴델이 그의 정리를 도출하는데 있어 산술체계로서 이의 체계를 선택한 이유가 바로 여기에 있는 것이다.

▶ 괴델의 착상

괴델의 이 논문은 상당히 난해했다. 그는 이 정리에 이르기 위해 46개의 예비 정의와 여러 개의 예비 정리를 거쳐야 했다. 우리는 여러 가지의 제한으로 이 과정을 여기에 제시하지는 못하고 그의 착상의 요체만 설명하려고 한다.

괴델은 먼저 형식화한 체계 내의 기본적인 기호, 논리식, 증명마다 하나의 고유 번호를 지정한다. 여기서 논리식이라 함은 기호를 규칙에 의해 하나로 묶은 것이다. 일상적으로는 명제도 논리식의 하나다. 그리고 증명은 추론규칙에 따라 이루어지는 논리식의 유한한 열이다. 이때 각 고유번호를 그 표현의 괴델수(G del numbers)라 한다. 모든 정수가 괴델수는 아니지만, 만일 어떤 수가 괴델수이면, 그 괴델수가 어떠한 표현의 괴델수인가를 알 수 있도록 하였다. 따라서 형식체계의 각 기호, 논리식, 증명 등에 하나의 자연수(괴델수)가 대응되고 그 역도 성립한다. 그렇게 한 목적은, 메타수학적 명제가 자연수에 관한 산술적 명제로 바뀔 수 있어서, 그 결과로, 메타수학적인 표현이 간결해질 뿐만 아니라 이를 통한 메타수학적 분석이 용이해지기 때문이다, 즉, 복잡한 논리상의 관계를 직접 분석하기 보다 이를 괴델수에 의해 산술에 관한 문제로 바꾸게 되면 그것의 분석이 명확히 드러나게 된다.

괴델의 증명은 크게 다음의 다섯 단계로 요약할 수 있다.

첫째, "논리식 G는 증명 불가능하다"는 메타 수학적 명제를 나타내는 논리식 G를 형식체계에서 구성한다. 그러면 G는 자기 자신에 관한 명제이므로, 그 내용은 "자기 자신은 증명 불가능하다"는 뜻이 된다. 논리식 G의 괴델수를 n이라 하면, 이 n 이 "괴델수 n에 대응되는 논리식은 증명 불가능하다"라는 명제에 대응하도록 구성한다.

둘째, G는 (형식적으로 G의 부정을 나타내는) ∼G가 증명 가능할 때 그리고 그때에 한해 증명 가능함을 증명한다. 즉, G가 증명 가능한 것과 ∼G가 증명 가능한 것이 논리적으로 동치임을 증명한다. 만일 어떤 논리식과 그것의 부정이 모두 증명 가능하면, 그 체계는 무모순이 아니다, 따라서 산술체계가 무모순하면, G와 ∼G 모두가 증명되는 일이 있어서는 안 된다.

셋째, G가 증명 불가능하지는 않지만 참인 논리식임을 제시한다.

넷째, G가 참이지만 증명 불가능하므로, 산술체계는 불완전하다(제1불완전성정리).

다섯째, 먼저 "산술체계가 무모순하다"는 메타수학적 명제를 나타내는 논리식 J 를 구성한다. 그리고 논리식 "J이면 G이다"가 증명 가능함을 보인다.

끝으로, 논리식 J가 증명 가능하지 않음을 증명한다. 이로부터 괴델의 제2불완전성정리인 "산술
체계의 무모순성은 형식체계 내에서 증명할 수 없다"를 얻는다.

▶ 괴델의 정리와 그 주변

괴델에 의해 얻어진 심원한 사상에 대한 탐구는 오늘날까지도 끊이지 않고 있다. 여기서는 그 결과가 주변 학문에 어떤 영향을 주고 있는가에 대해 그 일단을 소개하려고 한다.

괴델이 얻은 것은 하나의 형식체계의 규칙에 관계되기 때문에 컴퓨터의 기본 원리와 밀접한 연관성이 있다. 가령 인공지능 분야에서 '인간만이 할 수 있는 일'과 '기계가 할 수 있는 일'을 분석하는 데 괴델의 결과가 하나의 기초가 되고 있다. 제5세대 컴퓨터의 개발을 담당하는 신세대 컴퓨터 기술 개발기구의 중요한 과제의 하나에 '수학의 진리를 증명하는 시스템(computer aided proof)이 있다. 흥미로운 것은 그 중에 괴델의 불완전성정리를 컴퓨터로 증명하게 하는 연구가 진행중 이라는 대목이다. 이밖에 사이버네틱스, 전달, 정보이론 등 여러 분야가 괴델의 정리를 전제로 하고있다. 특히 베스(E.W. Beth)는 그의 저서 수학사상 (Mathematical Thought) 에서 괴델의 정리와 연관된 연구 과제를 '초등메타논리'를 비롯하여 14개로 상술하고 있어, 이 분야에 관심 있는 학도들에게 주목받고 있다.

다시 또 다른 면에서 괴델을 분석하면, 그는 논리학, 집합론에서 매우 특유한 문제에 대해 업적을 남겼다고 보아진다. 그는 언어로서의 형식체계 그 자체가 어떤 구조를 갖는가 하는 syntax (구조론)에 관계되는 문제와 존재론적이며 의미론적인 문제를 엄밀히 구별하고, 이 양자의 관계를 종합적으로 고찰하고 있다. 지금은 그것이 당연하게 보이지만, 그 당시, 즉 괴델 이전에는 종합적 관점이라는 시각적인 태도를 갖는다는 것을 전혀 찾아볼 수 없었다. 다시 말하면, 그는 수학의 새 지평을 열었다고 할 수 있다.

이러한 맥락에서 "수학적 진리"에 대해 여기서 잠시 살펴보기로 하자. 수학적 진리가 여타의 진리와 구별되는 특성은 확실성과 보편타당성이라고 할 수 있다. 그러나 괴델의 불완전성 정리와 타르스키(Alferd Tarski)의 진리론은 종래의 진리관을 바꾸게 하였다.

가령 "1+2=3"은 절대적으로 참이라는 인식을 우리 모두가 암암리에 갖고 있다. 그러면 어떻게 그것이 참임을 알 수 있는지에 대해 생각해보자. 명제 "눈은 희다" 에서는 '눈'과 '희다'라는 말이 지시하는 대상을 실제로 우리의 감각기관으로 확인 할 수 있으며, 현실적으로 "눈은 희다"라는 사실이 있기 때문에, 그 명제를 참이라고 할 수 있다. 이는 참과 거짓이 사실과의 대응에 의해 규정된다는 대응설적 진리관이다. 그러나 "1+2=3"에 대해서는 그 성격이 "눈이 희다"와는 근본적으로 다르다. 즉, 우리에게는 "1+2=3"을 확인할 방법이 없다. 뿐만 아니라 '1'이나 '2'나 "1+2=3"이라는 수학적 대상이 정말 존재하는가에 대해서조차도 아직 결말이 나지 않고 있다. 따라서 수학적 진리 문제에 있어서는 대응설적 진리관보다는 정합설적 진리관, 즉 명제 사이의 무모순성에 의해 명제의 진리를 규정하려는 방법이 더 중요시된다. 특히 형식주의에서는 이 진리관이 유력하다. 그러나 괴델의 제2불완전성정리는 이 진리관을 거부한다.

원래 수학적 명제는 그것이 증명될 때에만 참이 되며, 증명 가능한 명제를 수학에서는 정리라 한다. 수학에서 참인 명제는 반드시 정리가 되고, 그 역도 성립한다고 오래도록 인식되어왔다. 즉, '진리'와 '정리'가 논리적으로 같은 뜻으로 이해되어왔다. 그러나 괴델의 제2불완전성정리에 의해 참이지만 정리가 안 되는 명제가 제시됨으로써, 우리의 통념이 무너지고 말았다. 이러한 사실 때문에 수학의 본질에 대한 고찰이 한층 더 심화되고, 증명 가능성이 수학이 참과 거짓이라는 개념으로부터 독립되어야 하며, 수학의 보다 본질적인 문제는 진리가 아니라 '증명 가능성'의 개념이 되어야한다는 이해가 전적으로 지배하게 되었다.

앞의 설명과 같이, 현대 논리학의 사상은 수학적 진리에 대한 종래의 이해를 크게 바꾸게 하였으며 수학의 내부뿐만 아니라 철학에서도 진리론이 하나의 과제로 제기되고 있다.

▶ 맺음말

앞에서 적은 2절에서와 같이, 수학이 완전하지 않다는 G del의 결과가 수학기초론, 수학의 철학, 인지과학의 발전에서 확고한 초석이 되었다 하겠다.

수학과 논리학의 기초에 관한 문제는 그동안 별다른 진전이 없었으나, 19세기 말에 이르러 급속히 발전하였다. 1860∼1960년의 100년 사이에 수리철학의 논리주의, 형식주의, 직관주의 등과 같이 수학을 보는 철학적인 입장이 각각 정립되었으며, 이들이 수리철학의 주류를 이루어왔다. 이 세 학파 모두가 수학기초론이 요구하는 과제를 충족시켜준 것은 아니지만, 오늘날에도 이들의 사상은 자주 인용되고 있다.

1950년 이후, 수리철학이 새로운 경향의 발전을 보여주는 사상도 있기는 하지만, 앞의 세 학파를 통합하거나 새로운 방향으로 발전하는 사상은 전혀 찾아볼 수 없다. 다만 특기할 것은, 라드리에르(J. Ladrier)가 1923년 스코램(Skolem)이 얻은 결과, 1933년의 타르스키가 얻은 결과, 1963년 처치(Alonzo Church)가 얻은 결과 등과 함께 괴델의 불완전성정리를 합쳐서 이를 '제한정리'로 불렀다는 것이다. 이 일련의 정리들인 '제한정리'가 수학 발전의 흐름에서 볼 때, 하나의 패러다임이 되는 것은 분명하다고 본다.

위의 내용을 요약하면 다음과 같다.
힐버트(D. Hilbert, 1862~1943)는 그리스 이래 모든 수학자들이 꿈꾸어 오던 것처럼 유한 개의 공리(법칙, 원리)로 수학을 완성시킬 수 있다고 믿었다. 다시 말해서 수학의 모든 명제를 몇 개 안되는 공리를 바탕으로 증명할 수 있다고 생각한 것이다. 이러한 입장을 '유한주의'라고 부른다. 그러니까 서구의 지성사는 유클리드의 <원론>에서 개화되었던 그리스 이래의 전통을 충실히 지켜온 것이다.
힐버트는 집합론의 패러독스가 자아낸 수학의 위기를 극복하기 위한 작업의 하나로, 먼저 수학체계에 모순이 일어나지 않는다는 것(무모순)을 밝히려고 하였다. 그러기 위해 논리 체계를 비롯하여 자연수 체계, 집합론, 실수론 등의 공리계에 대해서 재검토해 보고 무모순인 공리계를 확립하여, 이들의 '완전성'이 확실히 보장받도록 할 것을 제창하였다. 이것이 이른바 '힐버트의 프로그램'(Hilbert's program)이다. 여기서 '완전성'이란, 어떤 공리계를 바탕으로 이루어지는 수학체계내에서 다루어지는 명제의 참ㆍ거짓 중의 하나가 반드시 증명 가능하다는 것을 말한다. 그 첫 시도로서, 고전적인 명제논리뿐만 아니라 술어논리(술어식 p(x)를 포함하는 논리)의 체계가 '무모순'이자 '완전'하다는 사실이 밝혀졌다.
힐버트의 야심찬 계획은 그의 추종자들에 의해 추진되어 가고 있었다. 이들 중에서 오스트리아 출신의 젊은 수학자 괴델(K. Gödel, 1906~1978)도 있었다. 그는 우선 힐버트의 프로그램이 실현 가능한지의 여부를 알기 위해 수학의 완전성을 증명하려고 시도했다. 이것은 수학자들이 으례 취하는 태도이다. 수학자들은 어떤 문제의 해답을 찾기에 앞서 그러한 해답이 과연 존재하는가를 먼저 확인해 보려고 한다. 그 좋은 예로, 가우스(K. F. Gauss)의 대수방정식에 대한 해의 존재 증명을 들 수 있다. 이것은 마치 보물섬을 찾아나서는 모험가가 먼저 보물섬의 존재를 확인하는 것과 같다.
그러나 그 결과는 수학이 완성될 날을 기다리는 사람들에게 찬물을 끼얹고 말았다. 그는 사람들이 기대했던 것과는 반대로 수학의 완전성이 아니라 불완전성을 증명해 버린 것이다. 즉, '보물섬'은 어디에도 존재하지 않음을 엄밀하게 증명한 것이다. 잔뜩 기대로 부풀은 힐버트는 절규하였다. 가장 완전한 체계를 갖춘 수학에 문제가 있다면, 어디에서 확실한 진리를 얻을 수 있다는 말인가!

괴델(K. Gödel, 1906~1978)이 유명한 '불완전성 정리'로 수학의 한계를 제시했다는 이야기는 앞에서 했다. 이 정리가 지닌 의의는 수학에 국한되지 않고, 널리 인간 지성에 관한 중요한 문제 제기를 한 점에 있다.
논리는 몇 가지 기본적인 공리를 증명 없이 내세워 공리(axiom)로 삼아 출발한다. 각 공리는 한 논리 체계의 기초를 이루고, 이들로부터 이끌어낸 정리는 이 체계의 상부구조를 이룬다. 각 공리는 서로 모순이 있어서는 절대로 안된다. 여기에는 '따라야 할 것은 오직 로고스(logos, 논리)뿐이다'라는 그리스의 사상이 내재되어 있다.
예로부터 수학자들은 어떤 수학의 분야이건 그 체계 안에 적절한 몇 개의 공리만 주어지면, 그것으로부터 모든 참된 명제를 이끌어낼 수 있으리라는 믿음을 확고히 지녀왔다. 20세기초 최대의 수학자 힐버트는 모든 수학은 모순이 없고, 독립적인 공리 위에 세워진 논리적인 체계이며, 이러한 공리의 무모순성과 독립성은 공리 위에 세워진 논리적인 체계이며, 이러한 공리의 무모순성과 독립성은 실제로 증명이 가능한 것으로 예상하였다. 실제로 그는 점, 직선, ... 등의 기하학적인 정의를 대신하여 컵, 책상, ... 등을 사용해도 이들 사이에 훌륭한 기하학, 즉 모순이 없는 수학체계가 성립할 수 있다고 주장했다. 그러나 괴델의 이 논문에 의해 그의 이러한 희망이 결코 실현될 수 없음이 밝혀졌다. 그의 논문은 공리적 방법이 아무리 완벽하다 해도 반드시 한계성을 지니고 있다는 놀라운 결론을 내놓은 것이다.
괴델은 아무리 많은(유한 개의) 공리를 내세우더라도 이 공리계에서는 참이라고도 거짓이라고도 판가름할 수 없는 명제가 존재함을 밝혀냈다. 바꿔 말해서 어떤 수학적 또는 논리 체계에도 그 자체 내에서 완전히 연역해 낼 수 있는(유한 개의) 공리계를 만들 수 없다는 것이다. 즉, 어떤 수학 체계이든 그 내부의 모순성 또는 무모순성이 다른 수학적 체계를 이용해야만 그 증명이 가능하다는 무모순(진리)에 관한 상대성을 그는 증명한 것이다.
괴델의 불완전성 정리에는 다음과 같은 '자기언급(self-reference)'이라는 특징을 갖는 명제가 쓰여지고 있다. 괴델이 만든 명제 G 는 자기 자신에 대해서 언급하는 명제인데, 이것이 곧 괴델의 명제 G 이다.그 내용은 다음과 같다.

G : 명제 G 는 증명 불가능하다.

만약, 자기자신(수학)에 대해서 언급한 명제 G 가 옳다고 증명되었다면 그야말로 모순이다. 왜냐하면, G 가 증명 불가능하다는 것이 증명되었다면, 그것은 G 가 증명 불가능이라는 것을 확인한 것에 지나지 않기 때문이다. 증명이 되면 증명 불가능, 곧 '카오스'라는 모순에 빠진다. 재미있는 것은 이 명제가 다음과 같이 프랙탈적인 구조를 지니고 있다는 점이다.

...명제(명제(명제 G 는 증명 불가능하다.)는 증명 불가능하다.)는 증명 불가능하다. ...

요컨대, 괴델은 수학의 공리화는 불가능하며, 또 수학적 사고가 '절대적 차원'에서 모순의 유무를 확인할 수 없음을 바로 수학적인 방법을 써서 밝힌 것이다. 그것은 수학에 준 충격보다는 오히려 인간의 사고 가능성 전반에 큰 충격을 준 것이다.
괴델의 명제에 등장한 자기언급의 논리적인 구조는 피드백이나 자기조직, 자기닮음 등등에서 볼 수 있는 것들과 같다. 여기에도 '피드백→카오스→프랙탈'의 구조를 볼 수 있는 것이다.

꽤 직관적으로 잘 설명되어있는 글이 있어 추가합니다^^;

Insight..

괴델의 불완전성의 정리

티스토리툴바

괴델의 불완전성의 정리

'Compute' Related Articles

티스토리툴바