20세기 초 힐베르트는 수학을 효과적으로 주어진 무모순 공리계 위에 세우고, 그 공리계 안에서 모든 수학적 명제를 결정할 수 있기를 기대하였다. 그러나 괴델의 불완전성 정리는 자연수의 기본 산술을 충분히 표현할 수 있는 효과적인 형식 체계에는 본질적인 한계가 있음을 보여준다.
이 부에서는 먼저 일계논리의 이론을 사용하여 페아노 산술을 정의하고, 콤팩트성을 사용하여 비표준 모형이 생기는 이유를 살펴본다. 이어서 괴델 수매김, 산술화, 대각화 보조정리를 바탕으로 자기참조를 형식화하고, 불완전성 정리의 핵심 논증을 설명한다.
앞에서 일계논리의 건전성과 완전성을 다루었지만, 여기서 말하는 “이론의 완전성”은 그 완전성 정리와 구별해야 한다.
정의 18.1. (완전한 이론)
만족 가능한 일계논리 문장 집합 \(T\)가 완전하다(complete)는 것은 임의의 문장 \(\sigma\)에 대하여 \[ T\models\sigma \quad\text{또는}\quad T\models\neg\sigma \] 가 성립한다는 뜻이다. 정리 16.7의 일계논리 완전성 정리에 의해 이는 \[ T\vdash\sigma \quad\text{또는}\quad T\vdash\neg\sigma \] 와 동치이다.
한 구조 \(\mathcal M\)의 이론 \(\operatorname{Th}(\mathcal M)\)은 정의 15.6에서 도입하였다. 임의의 문장 \(\sigma\)는 \(\mathcal M\)에서 참이거나 거짓이므로 \(\operatorname{Th}(\mathcal M)\)은 완전한 이론이다.
완전성은 모형의 동형 유일성과는 다른 개념이다. 완전한 이론의 모든 모형은 같은 일계논리 문장들을 만족시키지만 서로 동형일 필요는 없다. 두 구조가 같은 일계논리 문장들을 만족시킬 때 “두 구조가 초등동치(elementarily equivalent)이다”라고 표현한다. 따라서 완전한 이론의 임의의 두 모형은 초등동치이다.
이제 17장의 결과를 자연수에 적용한다. \(\omega=\mathbb N\)은 6장에서 구성한 자연수 집합이며, 9장의 무한 공리는 그 집합론적 존재를 정당화한다. 표준 산술 구조를 \[ \mathcal N=(\omega,0,s,+,\cdot) \] 로 나타내자. 여기서 \(s(n)=n+1\)이다.
페아노 산술의 공리
산술의 언어를 \[ \mathcal L_{\mathrm{PA}}=\{0,s,+,\cdot\} \] 로 둔다. 등호는 일계논리 자체의 논리기호이다. \(\overline n=s^n(0)\)을 자연수 \(n\)을 나타내는 수사(numeral)라고 하자.
공리틀은 일곱 개로 이루어져 있다. 그 중 처음 여섯 개는 다음과 같다.
(P1) \((\forall x)\neg(s(x)=0)\)
(P2) \((\forall x)(\forall y)(s(x)=s(y)\to x=y)\)
(P3) \((\forall x)(x+0=x)\)
(P4) \((\forall x)(\forall y)(x+s(y)=s(x+y))\)
(P5) \((\forall x)(x\cdot0=0)\)
(P6) \((\forall x)(\forall y)(x\cdot s(y)=x\cdot y+x)\)
마지막으로 귀납 공리틀을 추가하자. \(\phi(x,\vec y)\)가 \(\mathcal L_{\mathrm{PA}}\)-논리식이고 \(x\)가 귀납할 변수라고 하자. 다음 식의 모든 자유변수 \(\vec y\)를 전칭 한정한 문장을 공리로 삼는다.
(P7) \[ \bigl(\phi(0,\vec y)\wedge (\forall x)(\phi(x,\vec y)\to\phi(s(x),\vec y))\bigr) \to (\forall x)\phi(x,\vec y). \]
여기서 \(\phi(0,\vec y)\)와 \(\phi(s(x),\vec y)\)는 정의 14.5의 자유로운 대입으로 이해한다.
정의 18.2. (페아노 산술)
(P1)–(P6)과 귀납 공리틀 (P7)로 이루어진 \(\mathcal L_{\mathrm{PA}}\)-이론을 페아노 산술(Peano arithmetic)이라 하고 \(\mathrm{PA}\)로 나타낸다.
표준 구조 \(\mathcal N\)은 \(\mathrm{PA}\)의 모든 공리를 만족시킨다. 그러나 \(\mathrm{PA}\)의 모형이 \(\mathcal N\) 하나뿐인 것은 아니다.
정리 18.3. (페아노 산술의 비표준 모형)
\(\mathrm{PA}\)는 \(\mathcal N\)과 동형이 아닌 가산무한 모형을 가진다. 더 나아가 완전한 이론 \(\operatorname{Th}(\mathcal N)\)도 \(\mathcal N\)과 동형이 아닌 가산무한 모형을 가진다.
증명 언어에 새 상수기호 \(c\)를 추가하고 \[ T=\operatorname{Th}(\mathcal N) \cup \{c\ne\overline n\mid n\in\mathbb N\} \] 으로 둔다. \(T\)의 임의의 유한부분집합에는 \(c\ne\overline n\) 꼴의 문장이 유한 개만 나타난다. \(c\)를 그 수사들과 다른 충분히 큰 자연수로 해석하면 \(\mathcal N\)의 확장이 그 유한부분집합을 만족시킨다. 따라서 정리 17.1의 일계논리 콤팩트성에 의해 \(T\)는 모형 \(\mathcal M\)을 가진다.
\(\mathcal M\)에서 \(c^{\mathcal M}\)은 어느 표준 수사 \(\overline n\)의 값과도 같지 않다. 따라서 \(\mathcal M\)의 \(\mathcal L_{\mathrm{PA}}\)-축소는 \(\mathcal N\)과 동형일 수 없다.
언어가 가산이므로 \(T\)에 정리 17.3의 가산 모형 정리를 적용하여 \(T\)의 가산무한 모형을 얻을 수 있다. 그런데 \(\mathcal L_{\mathrm{PA}}\)-축소는 \(\mathcal N\)과 동형이 아닌 \(\operatorname{Th}(\mathcal N)\)의 가산무한 모형이다. 또한 \[ \mathrm{PA}\subseteq\operatorname{Th}(\mathcal N) \] 이므로, 이 축소는 동시에 \(\mathrm{PA}\)의 가산무한 비표준 모형이다.
따라서 “완전한 이론”과 “모형을 동형까지 유일하게 결정하는 이론”은 전혀 다른 개념이다. 실제로 \(\operatorname{Th}(\mathcal N)\)은 완전하지만 비표준 모형을 가진다. 반면 \(\mathrm{PA}\)는 공리 여부를 기계적으로 판정할 수 있는 효과적인 공리계이지만, 다음 장에서 보듯 무모순이라면 완전하지 않다.
문제 18.1. 다음 물음에 답하시오.
- 임의의 구조 \(\mathcal M\)에 대하여 \(\operatorname{Th}(\mathcal M)\)은 완전한 이론임을 보이시오.
- 만족 가능한 이론 \(T\)의 임의의 두 모형이 초등동치이면 \(T\)가 완전함을 보이시오.
- \(\operatorname{Th}(\mathcal N)\)을 이용하여 완전한 이론이 반드시 모형을 동형까지 유일하게 결정하지는 않음을 설명하시오.
문제 18.2. \(\mathcal M\models\mathrm{PA}\)라고 하자.
- \(\overline0,\overline1,\overline2,\overline3,\overline4\)를 \(0\)과 \(s\)만을 사용하여 쓰시오.
- 공리 (P1), (P2)만을 사용하여 \[ \overline0^{\mathcal M},\overline1^{\mathcal M},\ldots,\overline4^{\mathcal M} \] 이 서로 다른 원소임을 보이시오.
- 같은 논증을 일반화하여 \(m\ne n\)이면 \[ \overline m^{\mathcal M}\ne\overline n^{\mathcal M} \] 임을 설명하시오.
문제 18.3. 언어에 새 상수기호 \(c\)를 추가하고 \[ T=\operatorname{Th}(\mathcal N) \cup\{c\ne\overline n\mid n\in\mathbb N\} \] 으로 두자.
- \(k\in\mathbb N\)에 대하여 \[ \operatorname{Th}(\mathcal N)\cup \{c\ne\overline0,\ldots,c\ne\overline k\} \] 의 모형을 \(\mathcal N\)에서 직접 만드시오.
- \(T\)의 임의의 유한부분집합이 만족 가능함을 설명하시오.
- 콤팩트성 정리를 적용하여 \(T\)의 모형 \(\mathcal M\)이 존재함을 보이고, \(c^{\mathcal M}\)이 어느 표준 수사의 값과도 같지 않음을 설명하시오.
- 이 사실이 왜 \(\mathcal M\)의 \(\mathcal L_{\mathrm{PA}}\)-축소가 \(\mathcal N\)과 동형이 아님을 뜻하는지 설명하시오.
문제 18.4. 구조 \(\mathcal M\)이 공리 (P1), (P2)를 만족시킨다고 하자. \(\mathcal M\)의 영역이 무한집합임을 증명하시오. (유한집합에서 자기 자신으로 가는 일대일함수가 전사함수라는 성질을 활용한다.)