불완전성 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

괴델의 불완전성 정리(Gödel's incompleteness theorems)는 1931년 쿠르트 괴델이 증명한 두 개의 정리로, 수론을 포함하는 수학형식화가 가지는 태생적 한계를 증명했다. 정리에 따르면, 산술 체계를 포함하며 모순이 없는 모든 공리계에는 참이지만 참임을 증명할 수 없는 명제가 존재하며, 또한 그 공리계는 자신의 무모순성을 증명할 수 없다.

이 정리는 수학의 체계를 완전하고 모순이 없는 공리계로 형식화하려는 힐베르트의 계획의 실패를 알리는 것으로 인식된다. 보다 구체적으로는, 이는 힐베르트의 두 번째 문제에 대한 부정적인 해답으로 볼 수도 있다.

괴델의 불완전성 정리는 산술화된 형식체계에는 참이지만 참임을 증명할 수 없는 문장이 존재한다는 것을 의미하므로 힐베르트의 신념과는 달리, 참인 수학적 진술이 영원히 증명도 반증도 되지 않을 수 있다는 것을 암시한다. 괴델의 불완전성 정리는 튜링 기계에서의 정지 문제가 해결 불가능하다는 것, 해가 존재하지 않지만 이를 증명할 수 없는 디오판토스 방정식이 존재한다는 것, 그리고 케이틴의 오메가가 존재한다는 것과 동등하며, 20세기 논리학, 수학뿐만 아니라 철학, 언어학, 컴퓨터 과학, 인지과학, 물리학 등의 학문에 깊은 영향을 끼쳤다.

수학사적 배경[편집]

수학은 공리적 방법을 통해 확실성과 엄밀성이 특징인 학문으로 발전해왔다. 수학은 19세기 초에 상식과 동떨어진 새로운 형태의 기하학과 대수학이 출현하면서 스스로의 진리 여부를 검토하게 되었다. 19세기 후반 수학의 엄밀화를 위한 운동이 진행되지만, 새로 구성한 수학에서 역설이 발견되었고 이 모순을 해결하기 위해 수학기초론의 세 가지 접근방식이 발전하였다. 수학적 존재에 대한 인간의 직관에 의해 수학이 도출된다고 하는 직관주의, 수학을 내용이나 의미가 없는 하나의 형식적 조작으로 귀착시키려는 형식주의, 수학의 개념과 정리가 논리학의 공리계에서 연역될 수 있다고 보는 논리주의가 그것이다. 형식주의자 힐베르트는 1925년의 논문 <무한에 관하여>에서 내용이나 의미가 명확한 수학문제는 언젠가는 반드시 풀릴 것이라고 했고, 이어서 1930년에 출판된 논문 <수학의 기초>에서도 초수학적인 방법으로 무모순성과 완전성에 관한 문제가 증명될 것이라고 진술했다 (힐베르트의 두 번째 문제). 그러나 이듬해인 1931년에 괴델은 힐베르트의 두 번째 문제를 주제로 한 논문 <『수학 원리』및 관련 체계에서 형식적으로 결정할 수 없는 명제에 대하여>을 발표한다. “산술을 형식화한 공리체계가 무모순이면 그 체계가 무모순이라는 명제를 증명하는 것은 불가능하다”는 논문의 결과가 괴델의 둘째 불완전성 정리이며 이는 형식주의에 치명적인 타격을 입혔다. (실제로 괴델의 결과가 힐베르트의 두 번째 문제를 해결했는지에 대한 합의는 존재하지 않는다.)

무모순성의 문제[편집]

무모순성의 개념[편집]

논리학에서 모순이 없음(consistency)은 의미론적 또는 구문론적으로 정의될 수 있다. 의미론적인 정의는 어떤 이론이 모델을 가질 때 무모순이라는 것이며, 구문론적인 정의는 그 연역체계의 공리로부터 공식 P와 공식의 부정 ~P가 동시에 증명 가능한 P가 존재하지 않을 때 무모순이라는 것이다.

무모순성 문제의 제기[편집]

19세기에 가우스, 보여이, 로바체프스키, 리만 등의 연구를 통해서, 유클리드 기하학의 다른 공준으로부터 평행선 공준을 유도하는 것은 불가능하다는 사실이 증명되었다.[1] 유클리드 공리체계의 1번~4번 공준을 그대로 사용하면서 5번 공준의 부정을 택한 비유클리드 기하학이 유클리드 기하학과 동등하게 성립했던 것이다. 비유클리드 기하학의 성장으로 인해 사람들은 주어진 체계 내에서 어떤 명제의 증명 불가능을 증명할 수 있다는 메타-증명에 관심을 갖기 시작했다. 괴델의 논문도 산술학에서 몇 가지 중요한 명제의 증명 불가능을 증명한 것이다. 또한 기하학의 공리가 자명성을 가진는 전통적인 믿음이 흔들리게 되면서 수학의 목표는 실제 세계의 표상이라기보다는 공준화된 최초의 가정에서 결론을 필연적으로 도출할 수 있는지를 따지는 추상적이고 형식적인 학문으로 인식되게 되었다. 이렇게 수학이 직관과 상식을 벗어나 형식화, 추상화되면서, 체계의 근거로 사용되는 공준의 집합체가 내적으로 모순되지 않고, 따라서 "공준에서 서로 모순되는 정리가 추론되는 경우는 없는가"라는 무모순성의 문제가 제기되었다. 형식적인 수학에서는 '진리'와 '증명가능성'의 개념이 구별되어 쓰인다. 즉, 한 공리 체계에서 연역적으로 어떤 정리를 도출할 수 있으면 그 정리는 증명가능한 것인데, 그 체계 내에서 거짓임을 증명할 수 없는 어떤 진술이 항상 참임을 증명할 수 있다는 보장은 없는 것이다.

무모순성의 상대적 증명[편집]

어떤 체계의 추상적 공준들을 위한 모델(해석)을 찾아낸다면 무모순성을 해결할 수 있다. 모델에 포함된 모든 원소가 공준을 실제로 만족시키는지, 그리고 모든 공준이 참값이어서 서로 모순되지 않는지 실제의 관찰을 통해 판별하는 것이다. 유클리드 기하학의 경우 모델은 일상적 공간이다. 유클리드의 공리는 일상적 공간에서 언제나 참값이며, 따라서 서로 모순되지 않는다. 리만 평면 기하학의 무모순성도 유클리드 기하학 모델을 사용함으로써 입증할 수 있다. 리만의 공리에서 ‘평면’이란 용어는 유클리드 구면의 표면을, ‘점’이란 용어는 그 표면 위의 한 점을, ‘직선’이란 용어는 그 표면 위의 대원의 호를 의미하는 것으로 해석할 수 있고 리만 기하학의 정리들은 모두 유클리드의 정리로 변환될 수 있다. 그러나 이러한 상대적인 무모순성의 해결은 여기서 가정한 유클리드 체계의 공리들이 서로 모순되지 않는다는 보장이 필요한데, 무모순성의 해결 기준이 엄격해짐에 따라 유클리드 기하학의 모델이 되는 ‘일상적인 공간’ 에 대한 실제 경험 또한 절대적 무모순성을 보장해주지 못하게 되었다. 관찰된 모든 현상이 공리와 일치하더라도, 지금까지 관찰되지 않은 새로운 현상이 공리에 모순될 가능성이 있기 때문이다. 귀납적 증거는 공리가 타당성 있고 참값일 가능성이 크다고 말할 수 있을 뿐이다.

힐베르트는 유클리드의 공준을 데카르트 좌표 기하학의 대수적 참값으로 변환함으로써 유클리드 공준이 대수적 모델로 만족됨을 증명하였지만, 이는 여전히 다른 체계의 무모순성을 근거로 한 상대적 증명에 해당한다. 대수에 모순이 없다면 유클리드 기하학의 무모순성이 입증될 수 있을 것이므로, 산술체계의 무모순성을 확립하는 문제가 중요해진다.

무한모델의 무모순성 문제[편집]

유한모델은 직접 관찰을 통해 무모순성을 입증할 수 있지만, 수학에서 중요한 분야의 기초를 이루는 공준 체계의 대부분은 무한모델이다. 가령 “모든 정수는 바로 다음에 오는 정수가 있으며, 그 정수는 앞에서 사용된 어떤 정수와도 다르다”는 초등산술의 공준은 무한수의 원소를 포함한 집합에 속할 것이 요구된다. 그런데 수학적으로 중요한 위치를 차지하는 대부분의 공준 체계를 해석하는 데 필요한 무한모델은 직관에 의존하는 개략적 용어로 표현될 따름이며, 무한모델의 표현 자체에 모순이 숨어있을 수 있다. 실제로 19세기 게오르크 칸토어가 발전시킨 무한수 이론에서의 모순의 발견으로 인하여, 군 혹은 집합과 같이 가장 명백한 것으로 여겨졌던 기초 개념에서 출발한 체계까지도 무모순성을 보장할 수 없었다. 버트런드 러셀은 기초 논리학을 구축하는 과정에서 칸토어의 무한집합론에서 발견된 모순과 매우 유사한 러셀의 역설을 발견하였다.

무모순성의 절대적 증명[편집]

힐베르트의 연구 계획[편집]

다비트 힐베르트는 한 쪽 끝에 어떤 진술을 집어넣든지 간에, 크랭크를 돌리고 뒤로 물러앉아 있기만 하면 다른 쪽 끝에서 참/거짓이라는 대답이 나오는 진리기계(형식화된 공식체계)를 구상했다. 이는 수학을 형식화된 공식체계로 한 다음 그 체계의 무모순성을 ‘유한한 초수학적 방법’으로 증명함으로써 가능하다. 모든 산술적 진술의 참과 거짓을 결정할 수 있게 해주는 어떤 유한한 기계적 절차가 존재하느냐 하는 힐베르트의 결정문제에 대해, 형식화의 방법은 무한하게 많을 것이다. 괴델의 정리에 따르면 힐베르트 연구 계획의 모든 요구조건을 만족시키는 형식체계는 무한한 형식화의 모든 경우에 대해 존재하지도 않으며, 존재할 수도 없다.

연역 체계의 완전한 형식화[편집]

러셀의 역설 등에서의 역설적인 요소는 그 역설의 진술이 지닌 의미론적인 내용에 기인한다고 믿었던 힐베르트는 본질적으로 ‘무의미한’ 체계, 즉 형식체계를 창조하여 그 안에서 수학적 진술들의 참 또는 거짓에 대해 말하고자 했다. 공준과 공리를 비롯한 모든 식은 의미 없는 부호 체계, 형식화된 표시들의 ‘기호열’(string, 유한한 길이의 연쇄체)로 여겨진다. 공준에서 정리를 유도하는 것은 어떤 기호열의 집합을 다른 기호열의 집합으로 전환하는 것이다. 이렇게 형식화는 체계의 모든 정리들을 공리로부터 유도될 수 있도록 부호 체계를 구축하는 것이고, 여기서 모순되는 두 공식은 정해진 추론법칙으로 공리에서 동시에 유도될 수 없음을 보이면 무모순성이 증명된다.

형식화의 과정은 다음과 같다:

  • 첫째, 계산식에서 사용할 부호의 완전한 목록을 만든다(어휘에 해당).
  • 둘째, ‘공식’(문장)으로 용인 가능한 구성 규칙을 정한다(문법에 해당).
  • 셋째, 공식에서 다른 공식으로 변형시키는 추론규칙을 정한다.
  • 넷째, 어떤 공식을 그 체계의 기초, 토대가 되는 공리(원시공식)로 선별한다.

체계의 ’정리’는 변형 규칙을 연속적으로 적용해서 공리로부터 끌어낼 수 있는 임의의 공식을 뜻한다. 형식적 ‘증명’은 유한수의 공식을 추론규칙에 따라 나열한 것이다.

유클리드 기하학 뿐만 아니라 일반적인 수학 체계는 주세페 페아노 등에 의해 산술화되었고, 프레게, 러셀논리주의자들에 의해 산술체계가 논리학 명제로 표현될 수 있었다. 따라서 수학의 무모순성 문제는 형식논리학 자체의 무모순성 문제로 귀결되었고, 논리주의 진영의 화이트헤드러셀이 <수학 원리>에서 순수 수학(산술)의 모든 진술을 형식화하는 방법을 제공하였다. <수학 원리>에 제시된 포괄적인 표기 체계에 따라 순수 수학(산술)에 속하는 모든 진술이 표준적인 방법에 맞추어 코드화될 수 있었다.

몇 가지 배경 개념들[편집]

수학과 초수학[편집]

힐베르트는 연역적인 체계를 형식화하려고 했다. 여기서 "형식화"란 체계 내의 표현식들의 '의미'를 제거하고 기호들의 연쇄체로 표시하는 것이다. 이 작업을 위해 힐베르트는 "수학"과 "초수학"을 구분했다. "초수학적 진술"이란, 메타 수학, 즉, 수학에 대한, 수학을 설명하는 언어에 속하는 것이다. 체계 안에서 사용된 부호에 대한 진술일 수도 있고, 체계 그 자체에 대한 진술일 수도 있다. 예를 들어 "1+1=2"는 수학에 속하는 것이지만, "'1+1=2'는 산술 공식이다."는 초수학에 속한다. "산술에 대한 이론 체계가 무모순이다." 또는 괴델의 불완전성 정리의 함축 같은 것도 모두 초수학에 속하는 것들이다.

진리와 증명 가능[편집]

수학이 물질 세계의 원형이라고 여겨지던 시대가 지나고 비유클리드 기하학이 유입되면서 수학은 진리를 좇는 학문이 아니라 주어진 전제들로부터 가능한 결과들을 추론해내는 학문으로 성격이 바뀌어갔다. 순수 수학의 목표가 공준화된 몇 가지 가정들에서 정리를 유도하는 것이라는 인식도 점점 확산되었다. 그러나 이런 단계 단계 증명해가는 방식으로는 체계에 대한 우리의 이해를 따라올 수 없었다. 체계 내에서 증명될 수 없으면서도 초수학적으로 참인 명제를 괴델이 찾아냈던 것이다. 어떤 체계 안에서 "참"과 "증명 가능"의 두 개념이 다를 수 있다는 것이 제 1 불완전성 정리의 핵심 내용이다.

완전성과 무모순성[편집]

  • 완전성: 공리들로부터 모든 참인 명제가 정리로 유도됨.
  • 무모순성: 공리들로부터 모순되는 여러 결과를 증명하는 것이 불가능함. 공리들로부터 S가 증명될 수 있으면 S의 부정은 증명될 수 없다.

제1 불완전성 정리[편집]

괴델의 제1 불완전성 정리의 내용은 다음과 같다:

공리적인 방법으로 구성해내어 산술적으로 참인 명제를 증명할 수 있는 임의의 무모순인 이론에 대해, 참이지만 이론 내에서 증명할 수 없는 산술적 명제를 구성할 수 있다. 즉, 산술을 표현할 수 있는 이론은 무모순인 동시에 완전할 수 없다.

여기서 "공리적인 방법" 이란, 증명하지 않고 기본적으로 받아들이는 몇 개의 "공리"와 공리들로부터 유도되는 "정리"들로 이론 체계를 구성하는 방법을 의미한다. "증명할 수 있는" 명제란 공리들에 1차 논리를 적용하여 유도될 수 있는 것을 말한다. 어떤 명제를 체계 내에서 "구성할 수 있다"는 것은 공리로부터 해당 명제를 실질적으로 제시할 수 있는 과정이 존재함을 뜻한다. 여기서의 "산술"은 자연수의 덧셈과 곱셈으로만 이루어져 있으며, 이론이 "무모순"이라는 것은 이론 내에서 S라는 명제가 증명되었을 때 S의 부정에 해당하는 명제가 증명될 수 없음을 의미한다. 또한 이론이 "완전"하다는 것은 체계내의 참값이 모두 공리들로부터 1차적으로 유도될 수 있다는 것을 말한다.

제 1 불완전성 정리는 이러한 ‘공리적 방법’이 체계의 참인 명제들을 모두 구성해낼 수 없는 근본적이고 치명적인 문제를 안고 있다는 것을 보여준다. 괴델은 체계가 무모순임을 가정했을 때, 참이지만 증명될 수도, 반증될 수도 없는 산술적 명제를 항상 구성할 수 있다는 것을 증명했다. 괴델의 정리는 '골드바흐의 추측' 처럼, 여러 세기 동안 미해결 문제로 남아 있는 문제들이 언젠가는 증명될 것이라는 낙관을 하지 못하게 만들었다. "모든 짝수는 두 소수의 합" 과 같은 명제가 영원히 증명되지도, 반증되지도 않고 미해결 문제로 남을 수도 있는 것이다.

제2 불완전성 정리[편집]

괴델의 제2 불완전성 정리의 내용은 다음과 같다:

산술적인 참인 명제를 증명할 수 있는, 공리로부터 구성된 산술체계에 대하여 이 산술체계가 무모순이라면 이 산술체계는 스스로의 무모순성에 대한 진술을 포함할 수 없고 그 도 성립한다.

제 2 불완전성 정리는 실제로 공리로부터 출발한 산술체계가 무모순인지의 여부 자체에 대해 참 거짓을 결정할 수 없음을 뜻한다. 괴델은 산술 전체가 들어있는 포괄적인 체계의 무모순성은 초수학적으로 증명할 수 없다는 것을 증명했다.

괴델의 증명 맛보기[편집]

증명 개요[편집]

1931년에 출간된 '<수학 원리> 및 관련 체계에서 형식적으로 결정될 수 없는 명제에 관하여'라는 제목의 괴델의 논문은 수학계에 큰 충격을 안겨주었다. 괴델의 정리는 무모순성의 대가가 불완전성이라는 것을 말하고 있다. 괴델의 정리 내용이 혁신적인 만큼 그 증명 방법도 충분히 수학사적인 의의가 있다.

괴델은 먼저 형식화된 체계의 명제나 명제들의 나열에도 각각 괴델수라는 것을 부여했다. 그리고 체계 안의 각 식에 수를 부여함으로써 초수학적인 개념들도 산술 관계로 사상된다는 것을 보여주었다. 이러한 산술 술어들을 사용하면 괴델 수 m인 식이 증명될 수 없다고 말하는 산술 명제 G를 구성할 수 있었다. 여기서 괴델은 산술 명제 G의 괴델 수가 m이 되도록 조작하였다. 즉, G는 자기 자신이 증명될 수 없다고 말하는 명제인 것이다. 따라서 G를 체계 안에서 형식적으로 증명할 수 있다면 G는 증명될 수 없다는 명제 역시 증명될 것이며, 처음부터 무모순인 체계를 가정하면 G가 증명된다는 가정 하에 모순이 도출되므로 G는 증명 불가능한 명제가 된다. 이러한 결정 불가능한 명제를 찾아낸 후 괴델은 "산술은 무모순이다"에 해당하는 산술 명제 A를 구성하고, A⊃G임을 보였다. 그러면 여전히 체계가 무모순이라는 전제하에 G가 결정될 수 없으므로 A또한 결정될 수 없었다. 산술의 무모순성을 증명하는 것이 불가능함을 이끌어낸 것이다. 아래에서는 괴델의 방법이 어떤 식으로 구체화될 수 있는지 좀 더 쉬운 방법으로 증명해보자.

괴델수 붙이기[편집]

“ 하나의 수에 하나의 공식 ”

괴델은 <수학원리>라는 러셀과 화이트헤드의 저작에서 제시된 형식화된 체계에서 '체계의 무모순성을 증명할 수 없음'을 증명했다. 이 증명의 첫 단계는 모든 ‘체계 내’ 기본 부호나 임의의 연쇄체, 어떤 명제에 대한 개별 증명 등에 각각 마치 ID 처럼 하나의 수(여기서는 특히 자연수)를 대응시키는 작업이다. 여기서는 이러한 수를 특별히 ‘괴델수’ 라고 부를 것이다. 이 작업의 기본적인 구상은 다음과 같다.

  1. 자연수의 어떤 부분집합에 들어있는 임의의 괴델수를 하나 선택했을 때, 그 수에 대응되는 공식(체계 내 부호 연쇄체: 아무 의미 없는 부호들의 나열일 수도 있고, 어떤 명제에 대한 증명일 수도 있다.)이 혼동 없이 단 하나 존재하고, 이를 찾을 수 있다.
  2. 체계 내 하나의 공식을 선택했을 때, 그 공식에 대응되는 괴델수가 단 하나 존재한다.

모든 체계 내 언어를 각각의 수들에 1:1로 대응시키기 위해 우리는 산술의 기본적인 정리들을 이용할 것이다.

기본 어휘 구축[편집]

  • 불변부호, 즉 ¬ = 0 s ( ) ,에 각각 1부터 10까지의 괴델수를 붙인다.
    여기서 s는 "바로 다음에 오는 것" 이라는 뜻을 나타낸다.
  • x y z 와 같은 수치적 변수에 각각 10보다 큰 소수를 괴델수로 붙인다.
  • p q r 과 같은 문장적 변수에 각각 10보다 큰 소수의 제곱을 괴델수로 붙인다.
  • P Q R 과 같은 술어적 변수에 각각 10보다 큰 소수의 세제곱을 괴델수로 붙인다.


기본 부호들에 괴델수 붙이기
기본 어휘 ¬ = 0 s ( ) , x y z p q r P Q R
괴델 수 1 2 3 4 5 6 7 8 9 10 11 13 17 112 132 172 113 133 173

공식에 대한 괴델수 붙이기[편집]

기본 부호들로 이루어진 이 체계의 어떤 공식에 대해서는, 공식을 이루는 각 부호들의 괴델수를 차례대로 나열할 수 있을 것이다. 이렇게 임의의 공식에 대해 공식을 이루는 부호의 괴델수들로 이뤄진 유한 수열을 얻을 수 있다. 이 유한수열의 각 항을 차례대로 2,3,5,7,⋯로 이어지는 소수들의 지수 자리에 올린 다음 소수들의 거듭제곱항들을 모두 곱해준 것을 공식의 괴델수로 정한다.

예) (∃x)¬(x=y)의 괴델수
( x ) ¬ ( x = y )
각 부호에
대한 괴델수
8 4 11 9 1 8 11 5 13 9
28 34 511 79 111 138 1711 195 2313 299
명제의 괴델수 28×34×511×79×111×138×1711×195×2313×299


이렇게 해서 모든 체계 내 공식에 대해 각각 하나의 괴델수를 부여할 수 있다. 하지만 여전히 '자연수의 어떤 부분집합에 들어있는 임의의 괴델수를 하나 선택했을 때, 그 수에 대응되는 공식이 혼동 없이 단 하나 존재하고, 이를 찾을 수 있다'는 것을 확인하는 일이 남았다. 이를 확인하기 위해 정수에 대해 기본적으로 성립하는 두 가지 정리인, 산술의 기본정리(Fundamental Theorem of Arithmetic)와 수학적 귀납법을 사용하기로 하자.

산술의 기본정리: 어떤 수가 1보다 크다면 그 수는 소수이거나 소수들의 곱이며 또한 이 수는 단 한 가지 방법으로만 소인수분해 될 수 있다
수학적 귀납법: a가 S의 원소이다. S가 a보다 크거나 같고 n보다 작은 모든 정수를 포함한다고 가정했을 때 n 역시 S의 원소이면, S는 a보다 크거나 같은 모든 자연수를 원소로 갖는다.

n보다 작은 모든 자연수에 대하여, 각각의 수에 대응하는 공식이 혼동 없이 단 하나 존재하고, 이를 찾을 수 있다고 가정하자. n은 산술의 기본 정리에 의해 소인수분해 가능하며 그 형태가 유일하다. 따라서 n=2a1×3a2×...×pam꼴로 쓸 수 있다. 이 때, ai은 n보다 작으므로 각각의 ai에 대응하는 공식이 존재하며, 이를 찾을 수 있다. 따라서 n에 대응하는 공식은 ai에 대응하는 공식들을 순차적으로 늘어놓은 것으로 존재하며, 유일하다. 즉 어떤 괴델수가 주어졌을 때, 이 수를 괴델수로 갖는 공식을 추리해낼 수 있다.

예) 243000000에 대응하는 산술 공식을 찾아보자. 243000000=26×35×56 로 소인수분해 되며, 6을 괴델수로 갖는 부호는 "0"이고 5를 괴델수로 갖는 부호는 "="이다. 따라서 이 수를 괴델수로 갖는 공식은 "0=0"이 된다.

초수학의 산술화[편집]

모든 수에 하나의 연쇄체를, 모든 연쇄체에 하나의 수를 대응 시키고 나서 괴델의 다음 단계는 수와 수사이의 산술적 관계를 연쇄체와 연쇄체의 관계에 사상시키는 것이었다. 즉, 산술 공식이 특정한 연쇄체들 사이의 초수학적 관계를 반영하게 된 것이다.

ⓐ Dem(x,y) 어떤 연쇄체 p가 연쇄체 q를 증명한다고 해보자. 이 때 ‘p가 q를 증명한다.’는 명제는 초수학적 명제인데, p의 괴델수를 x라 하고 q의 괴델수를 y라고 하면 x와 y사이에는 이런 p, q의 초수학적 관계를 대변하는 산술적인 관계가 성립할 것이다. 그러면 거꾸로 x와 y라는 두 수 사이에 이러한 산술적 관계가 성립한다는 것만 보여주어도, <괴델수를 x로 갖는 연쇄체는 괴델수를 y로 갖는 연쇄체를 증명한다>는, 체계 내 정리를 증명할 수 있게 된다. 이러한 관계를 Dem(x,y)라고 표현하도록 하자. 이 때, 만약 두 수 r과 s가 있어, r을 괴델수로 갖는 연쇄체(m)가 s를 괴델수로 갖는 연쇄체(l)에 대한 증명이 아닐 경우에는 r과 s사이에 이러한 산술적 관계가 성립하지 않는다는 것만 보여주면 충분할 것이다. 즉, 이러한 두 수(r,s) 사이에는 ~Dem(r,s)라는 관계가 성립하게 된다. (‘~’는 not을 의미하고 ~Dem(r,s)는 Dem(r,s)의 형식적 부정이다. 이를테면, ~(r=s)는 r≠s를 의미한다. )

ⓑ sub(m,13,m) 예를 들어, ' (∃x)(sx=y) '(x 다음이 y인 x가 존재한다)라는 공식의 괴델수를 m이라고 하자. 이 공식에 있는 ‘y’라는 부호를 ‘m’으로 바꿔 넣을 수 있을 것이다. 물론, 여기서 m은 공식 안에 들어가기 위해 sss⋯0(s는 m개, s는 '다음'의 의미이다. 이를테면 s0의 의미는 1과 같다고 할 수 있다.)로 체계 내 부호를 써서 표현할 것이다. 그러면 이 공식은 (∃x)(sx=sss⋯0)으로 바뀌고 이제 이 새로운 공식의 괴델수를 구할 수 있다. y의 괴델수를 앞에서 13으로 정의했는데, 그렇다면 새로운 공식의 괴델수란 13과 m이라는 두 수에 의해 결정되는 수일 것이다. 이 새로운 공식의 괴델수를 sub(m,13,m)이라고 표기하도록 하자. (혼란을 미연에 방지하고자 밝혀두자면, sub(a,b,c)의 정의는 ‘괴델수가 a인 식에서 괴델수가 b인 변수를 괴델수가 c인 수로 치환했을 때 그 식의 괴델수’이다. 여기서는 b가 13이므로 b가 가리키는 식은 y이다. sub(m,13,m)이 가리키는 것은 명확히 하나의 정수이다. )

형식적으로 증명될 수 없는 명제[편집]

스스로 자신은 증명될 수 없다고 주장하는 공식[편집]

다음의 공식은 산술 체계에 속하지만, 초수학적 명제를 표현하는 것이다.

ㄱ. (x)~Dem(x, sub(y,13,y))

여기서 (x)는 “모든 자연수 x에 대하여(x는 s0,ss0,sss0,⋯)” 라는 뜻이고 ~Dem(x, sub(y,13,y))는 정의에 따르면 “x를 괴델수로 갖는 공식은 괴델수로 sub(y,13,y)를 갖는 공식을 증명할 수 없다.” 라는 뜻이다. 따라서 ㄱ의 의미는 “괴델수로 sub(y,13,y)를 갖는 공식은 증명될 수 없다.”이다. 이제 “ㄱ의 괴델수”를 n이라고 하자.

체계 M(우리가 대상으로 삼은 산술체계)에서 G의 위치
G. (x)~Dem(x, sub(n,13,n))

이제 G를 살펴보자. 앞에서 괴델수 13을 갖는 변수는 y였으므로 <괴델수 13을 갖는 변수를 n으로 치환한 연쇄체의 공식>은 sub(n,13,n)이며 동시에 G의 괴델수이다. 여기서 다시 이 식의 의미로 돌아가 보면, ‘괴델수로 sub(n,13,n)을 갖는 공식을 증명할 수 없다.’ 이며 따라서 G는 ‘G-자기 자신-를 증명할 수 없다’ 는 초수학적 의미의 체계 내 공식이 된 것이다.

애물단지 G에 대한 형식체계의 골머리 썩기[편집]

이제 G가 형식 체계 안에서 형식적으로 증명될 수 있다고 가정해보자. 그렇다면 G에 대한 증명 과정이 있을 것이고 그 증명 과정식의 괴델수를 k라 하면, Dem(k,sub(n,13,n))이라는 관계가 성립할 것이다. (여기서 sub(n,13,n)은 G의 괴델수) 따라서 Dem(k,sub(n,13,n))은 정리가 된다. 그런데 우리는 이로부터 기초논리학의 변형 규칙을 이용하여 ~(x)~Dem(x,sub(n,13,n))를 유도할 수 있다. (‘모든 x에 대하여 x는 p라는 성질을 갖지 않는다.’의 부정은 ‘어 떤 x가 존재하여 x는 p라는 성질을 갖는다.’이다.) 즉, 체계 내에서 G가 증명가능하면 ~G도 증명가능하다. 따라서 형식체계가 무모순적이라면 G는 증명될 수 없다는 결론을 얻을 수 있다.

참이지만 형식적으로 증명될 수 없는 명제[편집]

에서 봤듯이 G는 형식적으로는 ‘결정 불가능’하다. 무모순적인 형식 체계에서 G는 증명될 수 없다. 따라서 무모순적인 형식 체계에서 G, 즉 ‘sub(n,13,n)을 괴델수로 갖는 공식(사실은 G 자기 자신이다.)은 증명될 수 없다.’는 참이다. 우리가 여기서 주목해야 할 점은 체계 내 G의 참값이 체계 내의 공리로부터 형식적으로 얻어진 것이 아니라 초수학적 추론으로 입증되었다는 것이다.

무모순성의 결정불가능률[편집]

괴델은 이렇게 해서 러셀과 화이트헤드의 ‘수학원리’에서 제시된 체계에 대해, <이 체계가 무모순적이라면, 이 체계는 불완전하다>는 초수학적 명제를 얻었다. 우리는 이 명제를 체계 내 증명 가능한 공식으로 옮길 수 있다. 체계가 무모순적이라는 초수학적 진술은 ‘체계 내 증명할 수 없는 공식이 적어도 하나 있다’라는 초수학적 진술과 동치이다. (**) 이를 다음과 같이 쓸 수 있다.

A. (∃y)(x)~Dem(x,y)

즉, A가 <이 체계가 무모순적이라면, 이 체계는 불완전하다>의 조건절을 뜻하게 된다. 한편, 이 명제의 결과절은 바로 G로 표현될 수 있다는 것을 알 수 있다. 즉, <이 체계가 무모순적이라면, 이 체계는 불완전하다>라는 참인 초수학적 명제는 체계 내 공식 ‘A⊃G’로 표현된다. 이제 A가 증명가능하다고 해보자. 이 때 A⊃G는 증명 가능하기 때문에, 분리규칙(modus ponens)에 의해 G도 증명가능하다. 그러나 체계가 무모순적이라면, G는 체계 내에서 형식적으로 증명될 수 없으므로 A가 증명가능하다고 했을 때 모순이 생긴다. 따라서 체계가 무모순적이라면, A는 형식적으로 결정 불가능하다. 즉, 체계가 무모순적이라면, 체계의 무모순성은 증명될 수 없다. 다시 한 번 조심스럽게 말하자면, 체계가 무모순적이라면 체계의 무모순성을 보이는, 체계 내로 사상시킬 수 있는, 무모순성의 초수학적 추론은 존재하지 않는다는 것이다.

같이 보기[편집]

참고 문헌[편집]

  • 어니스트 네이글 외, 고중숙, 곽강제 역, 『괴델의 증명』, 승산, 2010
  • 모리스 클라인, 심재관 역, 『수학의 확실성』, 사이언스북스, 2007
  • 존 캐스티, 베르너 드파울리, 박정일 역, 『괴델』, 몸과마음, 2002
  1. Florence P. Lewis (Jan 1920). 《History of the Parallel Postulate》. The American Mathematical Monthly, Vol. 27, No. 1, 16–23쪽. doi:10.2307/2973238. JSTOR 2973238

바깥 고리[편집]