일계논리와 무모순성

By | September 3, 2017

Hilbert는 수학의 기초를 확립하는 단계에서 무모순성에 관한 형식적 증명을 찾아냄으로써 수학의 여러 모순을 제거하고자 하였다. 그 증명은 오직 유한 단계의 기계적 절차에 의해 행해질 수 있는 것이어야 했다. Hilbert는 수학적 개체의 존재성과 그 개체의 무모순성은 일치한다고 믿었다. 예컨대 Hilbert의 관점에서 보면 실수 범위에서 제곱하여 \(-1\)이 되는 성질은 자기모순적이므로 그러한 조건을 만족시키는 실수는 존재하지 않는다. Euclid 기하학은 실수 집합의 카르테시안 곱으로 구성될 수 있으므로 Euclid 기하학은 자기모순적이지 않다. 즉 실수계가 존재하면 Euclid 기하학이 존재한다. 한편 유리수계에 Dedekind 절단의 개념을 도입하여 실수계를 구성할 수 있으며, 정수계를 이용하여 유리수계를 구성할 수 있고, 자연수계를 이용하여 정수계를 구성할 수 있다. 따라서 Hilbert는 자연수계의 무모순적인 공리계를 구성하고자 노력하였다.

그러나 그와 같은 노력은 Gödel에 의하여 무너졌다.

일계논리 이론 \(\varSigma\)가 무모순적이라는 것은 \(\varSigma\)로부터 모순이 유도되지 않음을 뜻한다. 이 정의를 이용하여 \(\varSigma\)가 모순적임을 증명할 수는 있지만 \(\varSigma\)가 무모순적임을 증명하는 일반적인 구성적 방법은 존재하지 않는다. \(\varSigma\)가 무모순적임을 증명하려면 \(\varSigma\)의 밖으로 나와서 건전성 정리와 완전성 정리를 사용해야 한다. 즉 \(\varSigma\)가 무모순적임을 보이려면 \(\varSigma\)의 모델을 구성해야 한다.

그러나 Gödel 숫자붙이기의 방법은 체계 내에서 무모순성의 증명을 찾아낼 가능성을 열어주었다. 먼저 모순을 하나 잡는다. 예컨대 \(0 = 1\)과 같은 문장을 잡을 수 있다. 그리고 이 문장의 Gödel 수를 \(N\)이라고 하자. [참고로 \(0=1\)의 Gödel 수는 12진법으로 \(40674055\)이다.] \(\pi\)가 Peano 산술(관련 글 보기)의 정리 1에서 살펴본 함수라고 하자. 그러면 문장 \[(\forall x)(\lnot \pi (x,\,N )) \] 은 주어진 형식계의 무모순성을 보여준다.

형식론자들은 Peano 산술과 ZF 집합론과 같은 체계의 무모순성이 형식적 방법으로 증명될 수 있을 것이라고 믿었다. 그러나 Gödel의 제 2 불완전성 정리에 의하여 이것이 불가능함이 밝혀졌다.

정리 1.  Gödel의 제 2 불완전성 정리(Second Incompleteness Theorem).
만약 Peano 산술 \(\mathrm{PA}\)가 무모순적이면, \(\mathrm{PA}\)의 무모순성을 나타내는 논리식은 증명 불가능하다.

증명. \(\gamma\)가 \(\mathrm{PA}\)의 무모순성을 나타내는 논리식이라고 하자. Gödel의 불완전성 정리에 의하여 증명 가능하지도 않고 불가능하지도 않은 논리식 \(\zeta\)가 존재한다. 우리는 \(\mathrm{PA}\)가 무모순적일 때 \(\zeta\)가 증명 불가능함을 보일 것이다. \(\zeta\)가 자기 자신의 증명 불가능성을 함의하며, 이것은 \(\zeta\)가 참이라는 것을 뜻한다. \(\gamma\)가 \(\mathrm{PA}\)의 무모순성을 나타내므로, \(\zeta\)가 자기 자신의 증명 불가능성을 함의한다는 것을 형식적으로 나타내면 다음과 같다. \[\mathrm{PA} \cup \left\{ \gamma \right\} \vdash \zeta .\] 따라서 추론 정리에 의하여 다음을 얻는다. \[\mathrm{PA} \vdash ( \gamma \rightarrow \zeta ).\] 만약 \(\mathrm{PA}\)로부터 \(\gamma\)가 추론 가능하다면 Modus Ponens에 의하여 \(\zeta\)의 증명이 존재하게 된다.

이것은 모순이므로 \(\gamma\)는 증명 불가능하다.

위 정리는 \(\mathrm{PA}\)에서 \(0=1\)의 증명이 영원히 발견되지 않으리라는 확신을 할 수 없음을 시사한다. 물론 우리가 다루는 자연수계에서 \(0=1\)은 참이 아니며, \(0=1\)을 증명하지 않는다.

Peano 산술에서 살펴보았다시피, 직후자, 자연수의 합, 곱을 다룰 수 있는 무모순적인 형식계는 자기 자신의 무모순성을 증명할 수 없다. 따라서 위와 같은 정리가 그리 놀라운 것은 아니다.

한편 자연수계는 집합론을 이용하여 Peano 공리계를 만족시키도록 구성될 수 있다. 그러므로 집합론의 ZF 공리계는 Peano 공리계의 무모순성을 증명하기에 충분하다. 즉 Peano 산술은 스스로의 무모순성을 증명할 수 없지만 그보다 더 큰 체계에서 Peano 산술의 무모순성을 증명할 수 있다. 그러나 이 경우 더 큰 체계의 무모순성에 관련된 문제가 남는다.

Leave a Reply