괴델의 불완전성 정리는 “효과적으로 공리화할 수 있으면서 자연수 산술을 충분히 표현하는 무모순 이론”은 완전할 수 없다는 사실을 보여준다. 여기서 효과적으로 공리화 가능(effectively axiomatizable)하다는 것은 공리들을 알고리즘을 사용하여 차례로 나열할 수 있다는 뜻으로 이해한다.
이 장에서는 \(\mathrm{PA}\)를 중심으로 핵심 아이디어를 설명한다.
1. 괴델 수매김과 산술화
괴델의 아이디어는 형식언어의 유한한 부호열과 증명을 자연수로 부호화하는 것이다. 이러한 부호화를 괴델 수매김(Gödel numbering)이라고 부른다. 구체적인 수매김 방식은 여러 가지가 있으며, 중요한 것은 부호열의 연결, 치환, “올바른 증명인가”와 같은 구문적 연산과 관계가 자연수에 대한 효과적인 산술 연산과 관계로 바뀐다는 점이다.
간단한 예로 다음과 같이 기본기호에 12진 숫자를 배정하자.
12진 숫자 \(\mathrm A\), \(\mathrm B\)를 각각 변수 표시와 논리식 시작 표시로 사용하자. 변수 \(x_n\)은 \(\mathrm A\), \(n\)의 12진 표기, \(\mathrm A\)를 차례로 적어 부호화하고, 완전한 논리식의 코드 맨 앞에는 \(\mathrm B\)를 붙인다. 이 시작 표시는 코드가 \(0\)으로 시작할 때 생길 수 있는 선두 \(0\)의 모호함을 없앤다. 예를 들어 \[ (\forall x_0)(\neg(s(x_0)=0)) \] 의 12진 코드는 \[ \mathrm{B43A0A541474A0A56055}_{(12)} \] 이다. 이 12진 정수가 해당 논리식의 한 가지 괴델 수(Gödel number)가 된다. 논리식 \(\phi\)의 괴델 수인 자연수를 \(G(\phi)\)로 나타내고, 그 자연수를 산술 언어 안에서 나타내는 수사 \(\overline{G(\phi)}\)를 간단히 \(\ulcorner\phi\urcorner\)로 쓰자.
증명은 논리식들의 유한열이므로 유한열에 대한 표준적인 자연수 부호화를 한 번 더 사용하여 자연수 하나로 부호화할 수 있다. 이후 정확한 숫자 자체보다 “그 부호가 어떤 구문적 대상을 나타내는가”가 중요하다.
괴델 수매김의 핵심은 단순한 부호화 자체가 아니라, 구문론을 산술 안에서 표현할 수 있다는 사실이다.
정리 19.1. (구문론의 산술화)
적절한 괴델 수매김을 고정시키면 “\(p\)는 \(\mathrm{PA}\)의 공리의 괴델 수이다”, “\(p\)는 괴델 수가 \(q\)인 문장의 \(\mathrm{PA}\)-증명의 괴델 수이다”, “\(q\)는 한 변수 논리식에 수사를 대입하여 얻은 논리식의 괴델 수이다”와 같은 기본적인 구문적 관계는 원시재귀적(primitive recursive) 관계로 만들 수 있으며, 따라서 \(\mathrm{PA}\)의 논리식으로 표현할 수 있다.
더 나아가 이러한 원시재귀적 관계를 표현하는 논리식은 표준 자연수의 수사에 대하여 수사별로 그 참·거짓을 \(\mathrm{PA}\) 안에서 정확히 판정하도록 택할 수 있다. 즉 표준 자연수들을 대입했을 때 해당 관계가 실제로 성립하면 그 논리식을 \(\mathrm{PA}\)에서 증명할 수 있고, 성립하지 않으면 그 부정을 \(\mathrm{PA}\)에서 증명할 수 있다.
특히 두 변수 논리식 \[ \operatorname{Prf}_{\mathrm{PA}}(p,q) \] 를 택하여 표준 자연수 \(m,n\)에 대해 \[ \mathcal N\models \operatorname{Prf}_{\mathrm{PA}}(\overline m,\overline n) \] 이 성립할 필요충분조건이 \(m\)이 괴델 수 \(n\)인 문장의 실제 \(\mathrm{PA}\)-증명 코드이도록 할 수 있다. 또한 정리 19.1의 수사별 판정 성질에 의해, 실제 증명 코드인 경우에는 \[ \mathrm{PA}\vdash \operatorname{Prf}_{\mathrm{PA}}(\overline m,\overline n), \] 실제 증명 코드가 아닌 경우에는 \[ \mathrm{PA}\vdash \neg\operatorname{Prf}_{\mathrm{PA}}(\overline m,\overline n) \] 가 성립하도록 \(\operatorname{Prf}_{\mathrm{PA}}\)를 택할 수 있다. 이때 \[ \operatorname{Prov}_{\mathrm{PA}}(q) :=(\exists p)\operatorname{Prf}_{\mathrm{PA}}(p,q) \] 를 \(\mathrm{PA}\)의 증명가능성 술어(provability predicate)라고 부른다.
2. 제1 불완전성 정리
불완전성 정리를 증명할 때 사용하는 자기참조의 핵심 도구는 다음 정리이다.
정리 19.2. (대각화 보조정리)
\(\theta(x)\)가 자유변수가 \(x\) 하나인 \(\mathcal L_{\mathrm{PA}}\)-논리식이면 어떤 문장 \(\sigma\)가 존재하여 \[ \mathrm{PA}\vdash \sigma\leftrightarrow \theta(\ulcorner\sigma\urcorner) \] 가 성립한다.
증명 개요 \(d(n)\)을 “괴델 수가 \(n\)인 한 변수 논리식의 자유변수에 수사 \(\overline n\)을 대입하여 얻는 문장의 괴델 수”라고 하자. 정리 19.1에 의해 이 대각함수 \(d\)를 산술 안에서 표현할 수 있다.
\(d(x)=y\)를 표현하는 논리식을 \(D(x,y)\)라고 하고 \[ \eta(x):=(\exists y)(D(x,y)\wedge\theta(y)) \] 로 둔다. \(e=G(\eta)\)이고 \(\sigma=\eta(\overline e)\)라고 하면, 정의상 \[ d(e)=G(\sigma). \] 따라서 \(D\)가 \(d\)를 올바르게 표현한다는 사실을 \(\mathrm{PA}\) 안에서 사용하면 \[ \mathrm{PA}\vdash \sigma\leftrightarrow \theta(\ulcorner\sigma\urcorner) \] 를 얻는다.
대각화 보조정리를 사용하면 다음 괴델 문장을 얻는다.
정리 19.3. (괴델 문장)
문장 \(G\)가 존재하여 \[ \mathrm{PA}\vdash G\leftrightarrow \neg\operatorname{Prov}_{\mathrm{PA}} (\ulcorner G\urcorner) \] 가 성립한다.
- \(\mathrm{PA}\)가 무모순이면 \(\mathrm{PA}\nvdash G\)이다.
- \(\mathrm{PA}\)가 \(\omega\)-무모순이면 \(\mathrm{PA}\nvdash\neg G\)이다.
증명 (1) \(\mathrm{PA}\vdash G\)라고 하자. 실제 증명의 괴델 수를 \(n\)이라 하면 구문론의 산술화에 의해 \[ \mathrm{PA}\vdash \operatorname{Prf}_{\mathrm{PA}} (\overline n,\ulcorner G\urcorner), \] 따라서 \[ \mathrm{PA}\vdash \operatorname{Prov}_{\mathrm{PA}} (\ulcorner G\urcorner) \] 이다. 한편 괴델 문장의 정의에서 \(\mathrm{PA}\vdash G\)는 그 부정을 함께 주므로 무모순성에 모순이다.
(2) \(\mathrm{PA}\vdash\neg G\)라고 하자. 괴델 문장의 동치에서 \[ \mathrm{PA}\vdash (\exists p)\operatorname{Prf}_{\mathrm{PA}} (p,\ulcorner G\urcorner) \] 를 얻는다. 그러나 (1)에 의해 실제 표준 자연수 \(n\) 가운데 \(G\)의 증명 코드는 하나도 없다. \(\operatorname{Prf}_{\mathrm{PA}}\)는 원시재귀적이므로 각 표준 \(n\)에 대해 \[ \mathrm{PA}\vdash \neg\operatorname{Prf}_{\mathrm{PA}} (\overline n,\ulcorner G\urcorner) \] 이다. 이는 \(\omega\)-무모순성에 어긋난다.
특히 \(\mathrm{PA}\)가 무모순이면 실제 자연수 가운데 \(G\)의 증명 코드는 없으므로 표준구조 \(\mathcal N\)에서 \(\neg\operatorname{Prov}_{\mathrm{PA}}(\ulcorner G\urcorner)\)가 참이다. 괴델 문장의 동치도 \(\mathcal N\)에서 참이므로 \(\mathcal N\models G\)이다. 따라서 \(G\)는 표준 자연수에서 참이면서 \(\mathrm{PA}\)에서는 증명할 수 없는 문장이다.
여기서 이론 \(T\)가 \(\omega\)-무모순(\(\omega\)-consistent)이라는 것은 어떤 논리식 \(\phi(x)\)에 대해서도 \[ T\vdash(\exists x)\phi(x) \] 이면서 동시에 모든 표준 자연수 \(n\)에 대해 \[ T\vdash\neg\phi(\overline n) \] 인 일이 없다는 뜻이다. 단순한 무모순성보다 강한 조건이다.
괴델의 원래 논증은 위와 같이 \(G\)의 반증 불가능성에 \(\omega\)-무모순성과 같은 추가 조건을 사용한다. 로서는 문장을 조금 바꾸어 이 조건을 제거하였다.
정리 19.4. (괴델-로서 제1 불완전성 정리)
\(\mathrm{PA}\)가 무모순이면 어떤 산술 문장 \(R\)이 존재하여 \[ \mathrm{PA}\nvdash R, \quad \mathrm{PA}\nvdash\neg R \] 이다. 더 일반적으로 \(\mathrm{PA}\)를 포함하는 효과적으로 공리화된 무모순 산술 이론도 완전할 수 없다.
개요 여기서는 로서 논증의 개요를 살펴본다.
대각화 보조정리를 이용하여 \(R\)이 다음 내용을 표현하도록 만든다.
“나의 임의의 증명보다 번호가 작거나 같은 내 반증이 존재한다.”
좀 더 정확히는 \(R\)이 \[ (\forall p)\Bigl( \operatorname{Prf}_{\mathrm{PA}}(p,\ulcorner R\urcorner) \to (\exists q\le p) \operatorname{Prf}_{\mathrm{PA}}(q,\ulcorner\neg R\urcorner) \Bigr) \] 의 고정점이 되도록 한다. 여기서 \(q\le p\)는 \((\exists r)(q+r=p)\)로 산술 안에서 표현할 수 있다.
만약 \(R\)의 증명이 존재하면 그 가운데 가장 작은 코드를 \(p\)라고 할 수 있다. 무모순성 때문에 \(\neg R\)의 증명은 존재하지 않는다. 그러나 \(R\)의 내용과 \(p\)가 실제 증명 코드라는 사실을 \(\mathrm{PA}\) 안에서 확인하면 코드가 \(p\) 이하인 \(\neg R\)의 증명이 있어야 한다는 결론을 얻어 모순이다. 따라서 \(R\)은 증명되지 않는다.
반대로 \(\neg R\)의 가장 작은 증명 코드를 \(q\)라고 가정하자. 무모순성 때문에 \(R\)의 증명은 없다. \(p<q\)인 유한 개의 코드가 \(R\)의 증명이 아니라는 사실과 \(q\) 자체가 \(\neg R\)의 증명이라는 사실은 모두 \(\mathrm{PA}\) 안에서 확인할 수 있다. 따라서 모든 \(p\)에 대해 로서 조건이 성립함을 증명하여 \(\mathrm{PA}\vdash R\)을 얻게 되고, 다시 무모순성에 모순이다. 그러므로 \(\neg R\)도 증명되지 않는다.
불완전성 정리는 “수학 전체가 불완전하다”라는 뜻이 아니다. 핵심은 “효과적으로 공리화된 하나의 무모순 체계가 자연수 산술에 관한 모든 문장을 결정할 수는 없다”는 것이다. 실제로 \(\operatorname{Th}(\mathcal N)\)은 완전하지만, 제1 불완전성 정리에 의해 효과적으로 공리화될 수 없다.
3. 제2 불완전성 정리
제2 불완전성 정리는 “\(\mathrm{PA}\)가 무모순하다”라는 메타수학적 명제를 적절히 산술화했을 때 그 문장을 \(\mathrm{PA}\) 자체가 증명할 수 없다는 결과이다. 표준 증명가능성 술어를 이용하여 \[ \operatorname{Con}(\mathrm{PA}) := \neg\operatorname{Prov}_{\mathrm{PA}} (\ulcorner 0=1\urcorner) \] 로 둔다.
제2 불완전성 정리에는 증명가능성 술어가 만족시키는 몇 가지 사실이 필요하다. 여기서는 다음 정리를 증명 없이 소개한다.
정리 19.5. (힐베르트-베르나이스 도출가능성 조건)
문장 \(\phi\), \(\psi\)에 대해 표준 증명가능성 술어는 다음을 만족시킨다.
- \(\mathrm{PA}\vdash\phi\)이면 \[ \mathrm{PA}\vdash \operatorname{Prov}_{\mathrm{PA}}(\ulcorner\phi\urcorner). \]
- \(\mathrm{PA}\)는 \[ \operatorname{Prov}_{\mathrm{PA}}(\ulcorner\phi\to\psi\urcorner) \to \bigl( \operatorname{Prov}_{\mathrm{PA}}(\ulcorner\phi\urcorner) \to \operatorname{Prov}_{\mathrm{PA}}(\ulcorner\psi\urcorner) \bigr) \] 의 수사화된 형태를 증명한다.
- \(\mathrm{PA}\)는 \[ \operatorname{Prov}_{\mathrm{PA}}(\ulcorner\phi\urcorner) \to \operatorname{Prov}_{\mathrm{PA}} (\ulcorner\operatorname{Prov}_{\mathrm{PA}}(\ulcorner\phi\urcorner)\urcorner) \] 의 수사화된 형태를 증명한다.
정리 19.6. (괴델의 제2 불완전성 정리)
\(\mathrm{PA}\)가 무모순이면 \[ \mathrm{PA}\nvdash\operatorname{Con}(\mathrm{PA}). \]
개요 정리 19.3의 괴델 문장 \(G\)를 사용한다. 도출가능성 조건들을 \(\mathrm{PA}\) 안에서 형식화하면 \[ \mathrm{PA}\vdash \operatorname{Con}(\mathrm{PA})\to G \] 를 얻는다. 핵심은 다음과 같다. 괴델 문장의 고정점 성질에서 \(\neg G\)는 \(\operatorname{Prov}_{\mathrm{PA}}(\ulcorner G\urcorner)\)를 뜻한다. 한편 도출가능성 조건은 \(G\)가 증명 가능하다는 가정으로부터 “\(G\)가 증명 가능하다”와 “\(G\)가 증명 가능하지 않다”의 증명가능성을 모두 끌어내어 모순의 증명가능성을 얻도록 한다. 따라서 \(\neg G\)이면 \(\mathrm{PA}\)가 모순이라는 결론을 \(\mathrm{PA}\) 내부에서 증명할 수 있고, 그 대우가 위 식이다.
만약 \(\mathrm{PA}\vdash\operatorname{Con}(\mathrm{PA})\)라면 MP에 의해 \(\mathrm{PA}\vdash G\)이다. 그러나 \(\mathrm{PA}\)가 무모순이면 정리 19.3에 의해 \(G\)는 증명 불가능하다. 모순이므로 \(\mathrm{PA}\)는 자신의 표준적인 무모순성 문장을 증명할 수 없다.
제2 불완전성 정리는 더 강한 이론이 더 약한 이론의 무모순성을 증명하는 것까지 불가능하다는 뜻은 아니다. 예를 들어 ZF에서는 자연수의 표준구조를 구성하고 \(\mathrm{PA}\)의 공리와 추론규칙이 그 구조에서 건전함을 형식화할 수 있으므로 \(\operatorname{Con}(\mathrm{PA})\)를 증명할 수 있다. 다만 ZF 자체가 적절한 효과적 형식 체계로서 무모순하다면, 같은 이유로 ZF는 자신의 표준적인 무모순성 문장을 증명할 수 없다.
문제 19.1. 위의 기호 변환표의 수매김을 사용하자. 산술식 \(2+2=4\)를 \(0\), \(s\), \(+\), \(=\)만을 사용하여 나타내되, 완전 괄호 표기는 \[ ((s(s(0))+s(s(0)))=s(s(s(s(0))))) \] 로 한다. 위의 규칙에 따른 이 논리식의 12진 코드를 구하시오.
문제 19.2. 문장 \(\phi\)와 자연수 \(n\)을 생각하자. 다음 각 표현이 메타수학적으로 무엇을 뜻하는지 설명하시오.
- \(\mathcal N\models\operatorname{Prf}_{\mathrm{PA}}(\overline n,\ulcorner\phi\urcorner)\)
- \(\mathcal N\models\operatorname{Prov}_{\mathrm{PA}}(\ulcorner\phi\urcorner)\)
- \(\operatorname{Con}(\mathrm{PA})=\neg\operatorname{Prov}_{\mathrm{PA}}(\ulcorner0=1\urcorner)\)
또한 (2)는 “\(\phi\)가 표준구조 \(\mathcal N\)에서 참이다”라는 말과 일반적으로 같지 않음을 설명하시오.
문제 19.3. 대각화 보조정리를 \[ \theta(x)=\neg\operatorname{Prov}_{\mathrm{PA}}(x) \] 에 적용하시오. 얻어지는 문장 \(G\)가 어떤 의미에서 “나는 \(\mathrm{PA}\)에서 증명되지 않는다”라고 말하는지 설명하시오.
문제 19.4. 괴델 문장 \(G\)가 \[ \mathrm{PA}\vdash G\leftrightarrow \neg\operatorname{Prov}_{\mathrm{PA}}(\ulcorner G\urcorner) \] 를 만족시킨다고 하자.
- \(\mathrm{PA}\vdash G\)라고 가정하면 왜 실제 \(G\)의 증명 코드 \(n\)이 존재하는지 설명하시오.
- 그 코드와 구문론의 산술화를 사용하면 왜 \[ \mathrm{PA}\vdash\operatorname{Prov}_{\mathrm{PA}}(\ulcorner G\urcorner) \] 를 얻는지 설명하시오.
- \(\mathrm{PA}\)가 무모순이면 \(\mathrm{PA}\nvdash G\)임을 결론내리시오.
- 같은 무모순성 가정 아래 표준구조에서는 왜 \(\mathcal N\models G\)인지 설명하시오.
문제 19.5. 이론 \(T\)와 한 변수 논리식 \(\phi(x)\)에 대하여 다음 상황을 생각하자.
- \(T\vdash(\exists x)\phi(x)\)이고 모든 표준 자연수 \(n\)에 대하여 \(T\vdash\neg\phi(\overline n)\)이다.
- \(T\vdash(\exists x)\phi(x)\)이고 \(n=0,1,\ldots,100\)에 대해서만 \(T\vdash\neg\phi(\overline n)\)이다.
- 어떤 표준 자연수 \(m\)에 대하여 \(T\vdash\phi(\overline m)\)이다.
어느 경우가 \(\omega\)-무모순성의 정의에 직접 어긋나는지 답하시오. 또한 \(\omega\)-무모순인 이론은 무모순임을 설명하시오.
문제 19.6. 괴델의 원래 제1 불완전성 논증과 로서의 개선을 비교하여 다음 물음에 답하시오.
- 괴델 문장 \(G\)의 반증 불가능성을 위 본문 방식으로 얻을 때 필요한 추가 가정은 무엇인가?
- 로서 문장 \(R\)에서는 어떤 가정만으로 \(R\)과 \(\neg R\)의 증명 불가능성을 모두 얻는가?
- \(R\) 또는 \(\neg R\)의 증명이 실제로 존재한다고 가정했을 때 “가장 작은 증명 코드”를 택할 수 있는 이유는 무엇인가?
- 로서의 개선이 제1 불완전성 정리를 “완전한 이론을 얻는 방법”으로 바꾸는 것은 아닌 이유를 설명하시오.
문제 19.7. 다음 명제의 참·거짓을 본문의 제2 불완전성 정리와 그 설명에 근거하여 판단하고, 간단히 이유를 쓰시오.
- \(\mathrm{PA}\)가 무모순이면 \(\mathrm{PA}\nvdash\operatorname{Con}(\mathrm{PA})\)이다.
- 제2 불완전성 정리는 어떤 이론도 다른 이론의 무모순성을 증명할 수 없다고 말한다.
- 예를 들어 ZF는 \(\operatorname{Con}(\mathrm{PA})\)를 증명할 수 있다.
- 제2 불완전성 정리는 \(\mathrm{PA}\)가 실제로 모순인지 무모순인지를 결정해 주는 정리이다.
- \(\mathrm{PA}\)가 무모순이라는 가정이 빠지면 정리 19.6의 결론을 그대로 주장할 수 없다.