20세기 초 힐베르트는 완전하고 무모순인 공리 체계 위에 수학의 세계를 건설하고자 하는 야심찬 계획을 제시했다. 그러나 1931년 괴델은 불완전성 정리를 통해 이러한 계획이 근본적으로 불가능함을 보였다.
괴델의 불완전성 정리는 자연수의 기본 성질을 포함하는 충분히 강한 형식 체계는 완전할 수 없다는 것을 보여준다. 즉, 그러한 체계에는 증명도 반증도 할 수 없는 명제가 반드시 존재한다. 더 나아가 그러한 체계가 무모순이라면, 자기 자신의 무모순성을 증명할 수 없다는 놀라운 결과도 따라온다.
이 부에서는 페아노 산술이라는 구체적인 형식 체계를 통해 불완전성 정리를 살펴본다. 괴델이 사용한 독창적인 방법인 괴델 수매김을 도입하고, 이를 통하여 괴델의 불완전성 정리의 핵심 아이디어를 기술한다. 또한 불완전성 정리의 대표적인 예인 램지 정리와 페리스-해링스턴 정리를 살펴본다.
일계논리의 완전성과 이론
일계논리 문장의 집합 \(\varSigma\)가 완전하다(complete)는 것은 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha)\) 중 하나가 \(\varSigma\)의 논리적 귀결인 것이다. 일계논리의 완전성 정리에서는 형식계의 완전성을 말하기 때문에 용어의 사용이 약간 다르지만, 두 개념은 깊은 연관이 있다. \(\varSigma\)가 완전할 때는 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha)\)가 \(\varSigma\)로부터 증명될 수 있기 때문이다.
\(M\)이 구조일 때, \(M \models \sigma\)인 모든 \(\sigma\)들의 모임, 즉 \(M\)에서 성립하는 모든 일계논리 문장 \(\sigma\)들의 모임을 \(M\)의 이론(theory)이라고 부른다. \(M\)의 이론은 완전성을 가진다.
문장들의 모임 \(\varSigma\)가 무한 모델을 가지면 \(\varSigma\)는 여러 개의 모델을 가진다. 그러나 만약 \(\varSigma\)가 완전성을 가지면 \(\varSigma\)의 모델은 모두 동일한 일계논리 이론을 가진다.
수학의 특정 분야를 공리화한다고 할 때, 그 분야가 군론과 같이 다양한 모델을 가지는 경우에는 완전한 하나의 집합을 정하려고 하지는 않는다. 반면, 하나의 모델만을 갖는 분야를 공리화한다면 일계논리의 문장을 적절히 구성하여 그 문장들이 모델을 완전히 결정하도록 해야 한다.
자연수계
일계논리를 사용하여 공리화할 때 흥미로운 분야가 바로 자연수계이다. 여기서는 자연수 집합을 \(0\) 이상의 정수의 집합으로 정의하고 \(\omega\)로 나타내기로 하자.
집합론을 구성하지 않고 \(\omega\)의 구조를 일계논리로 직접 공리화하는 것이 가능할까? 일계논리를 사용한 \(\omega\)의 공리는 \(0\)으로부터 출발하여 따름수(successor)를 취함으로써 \(\omega\)의 모든 원소를 얻을 수 있어야 한다. 그러나 일계논리만으로는 '임의의 유한 번의 반복'에 대하여 논할 수 없다. 그러한 표현이 일계논리에서 허용되지 않기 때문이다.
\(\omega\)는 자기동형사상을 갖지 않는다. [\(\omega\)의 자기동형사상은 \(0\)을 부동점으로 갖고, 그에 따라 \(1,\) \(2,\) \(3,\) \(\cdots\)도 부동점으로 가진다. 따라서 \(\omega\)는 올리고모르픽 군(oligomorphic group)이 아니며 \(\omega\)와 동형이 아닌 가산 모델을 가진다.] 따라서 \(\omega\)를 공리화할 때에는 모델의 유일성을 기대할 수 없으며, \(\omega\)의 성질을 모두 끌어낼 수 있는 완전성을 갖는 단순한 공리계를 구성하는 것이 최선이다.
따름수 원리(succession principle)는 수학적 귀납법의 근거가 되며, 이것을 구현하는 방법은 수학적 귀납법의 원리(principle of induction)를 허용하는 것이다. 성질 \(\mathrm{P}\)가 \(0\)에 대하여 성립하고, \(\mathrm{P}\)가 \(n\)에 대하여 성립할 때마다 \(n+1\)에 대해서도 성립하면, \(\mathrm{P}\)는 임의의 \(n \in \omega\)에 대하여 성립해야 한다. 그러나 일계논리에서는 일계논리식으로 표현 가능한 성질만 다룰 수 있다.
자연수계의 공리화
\(\omega\)를 공리화하기 위하여 먼저 따름수 함수(successor function)와 관련된 공리를 도입하자. 우리의 언어는 상수기호 \(0\)과 일항함수 \(s\)를 가지는 것으로 약속한다. 여기서 \(s\)는 따름수 함수를 나타낸다.
- (P1) \(0\)을 제외한 임의의 원소 \(x\)는 유일한 \(y\)의 따름수이다.
- (P2) \(0\)은 어떠한 원소의 따름수도 아니다.
이들 공리는 일계논리의 문장으로 표현된다. 예를 들어 (P2)는 \((\forall x)(\lnot (s(x) =0))\)으로 표현된다. (P1)과 (P2)는 서로 동형이 아닌 가산 모델을 무한히 많이 가진다.
이제 덧셈과 곱셈을 다룰 수 있는 공리를 추가하자.
- (P3) \((\forall x)(x+0=x)\)
- (P4) \((\forall x)(\forall y)(x+s(y) = s(x+y))\)
- (P5) \((\forall x)(x \cdot 0 =0)\)
- (P6) \((\forall x)(\forall y)(x \cdot s(y) = x \cdot y + x)\)
끝으로 수학적 귀납법의 원리를 위한 공리를 도입하자. 이 공리는 하나의 공리가 아닌 공리틀이다. 즉 하나의 자유변수 \(x\)를 가진 언어의 각 논리식 \(\phi\)에 대하여 공리가 하나씩 대응된다.
- (P7) \(((\phi [0/x] \wedge (\forall x)(\phi \rightarrow \phi [s(x)/x])) \rightarrow (\forall x)\phi)\)
(P1)\(\sim\)(P7)로 이루어진 공리계를 페아노 산술(Peano arithmetic)이라고 부른다. [참고로 페아노 산술은 \(\omega\) 뿐만 아니라 \(\omega\)와는 다른 모델도 가진다. 그러한 모델을 '비표준 모델'이라고 부른다.]