페아노 산술이 완전성을 가질까? 그렇지 않다는 것이 1930년 괴델에 의하여 밝혀졌다. 즉 \(\omega\)에서 참이지만 페아노의 공리를 사용하여 증명할 수 없는 문장이 존재한다.
괴델의 불완전성 정리는 20세기에 손꼽히는 위대한 지적 업적 중 하나이다. 여기서는 불완전성 정리의 핵심적인 아이디어와 증명의 개요를 살펴보자.
1. 괴델 수매김
괴델의 아이디어는 각 논리식을 \(0\) 이상의 정수에 대응시키는 것이다. 이것을 괴델 수매김(Gödel numbering)이라고 부른다. 십진법으로 나타낸 정수는 숫자 기호들로 구성된 문자열이며, 논리식 역시 여러 기호들로 구성된 문자열이므로 논리식을 자연수에 대응시키는 것이 가능하다.
간단한 예로, 언어를 구성하는 기호에 다음 표와 같이 숫자를 배정할 수 있다.
여기에 두 개의 기호가 더 필요하다. 즉 '변수 표시 기호'와 '논리식 표시 기호'가 필요하다. 이들 두 기호를 각각 \(A,\) \(B\)로 나타내자. 이로써 논리식을 정수로 나타내는 데에는 10진법이 아니라 12진법을 사용해야 한다.
이 방식으로 모든 기호에 수를 할당하고, 변수도 적절히 처리한 후, 논리식을 이 숫자들의 나열로 표현할 수 있다. 이렇게 얻은 정수를 해당 논리식의 괴델 수(Gödel number)라고 부른다.[괴델 수매김은 이러한 방법 외에도 소수의 거듭제곱을 사용하는 방법도 있다.]
예를 들어, 페아노 공리 중 하나인 논리식 \((\forall x_0)(\lnot (s(x_0) = 0))\)을 괴델 수로 나타내면 다음과 같다. \[43A0A541474A0A56055\] 이러한 방식으로 논리식뿐만 아니라 증명 전체도 괴델 수로 나타낼 수 있다. 논리식 \(\phi\)의 괴델 수를 \(G(\phi)\)로 나타내자.
문제 19.1. 식 \(2+2=4\)를 산술의 일차논리 언어로 나타내고, 이 식의 괴델수를 구하시오.
2. 자기참조의 형식화
괴델은 형식계에서 자기참조를 형식화함으로써 불완전성 정리를 증명한다. 즉 "이 문장은 증명할 수 없다"라는 문장을 수학 내에서 구성하였다. 이 문장을 \(\zeta\)라고 하자. 만약 \(\zeta\)가 증명 가능하다면, \(\zeta\)의 내용("\(\zeta\)는 증명 불가능하다")이 거짓이 되므로 체계가 건전하지 않다. 반대로 \(\zeta\)가 증명 불가능하다면, \(\zeta\)의 내용이 참이 되지만 증명할 수 없는 참인 문장이 존재하게 된다.
자기 참조를 형식화하려면 "증명 가능하다"라는 상위수학적 진술을 형식적으로 표현해야 한다. 이것을 위해 다음과 같은 논리식의 존재성을 사용한다.
(a) 두 개의 변수 \(x_0,\, x_1\)을 가진 일계논리 산술의 논리식 \(\pi\)가 존재하여 다음을 만족시킨다.
- \(\omega \models \pi [n/x_0,\, m/x_1]\) (\(m = G(\phi)\)이고 \(n\)이 페아노 산술에서 \(\phi\)의 증명의 괴델 수일 때)
- \(\omega \models (\lnot \pi [n/x_0,\, m/x_1])\) (그 외의 경우)
(b) 두 개의 변수 \(x_0,\, x_1\)을 가진 일계논리 산술의 논리식 \(\tau\)가 존재하여 다음을 만족시킨다.
- \(\omega \models \tau [m/x_0,\, n/x_1]\) (변수 \(x_0\)가 자유변수로서 나타나는 적당한 논리식 \(\phi\)와 페아노 산술에서의 \(\phi [m/x_0]\)의 증명의 괴델 수 \(n\)에 대하여 \(m=G(\phi)\)일 때)
- \(\omega \models (\lnot \tau [m/x_0,\, n/x_1])\) (그 외의 경우)
(a)에서 논리식 \(\pi[n/x_0,\, m/x_1]\)는 직관적으로 "\(n\)은 괴델 수가 \(m\)인 논리식의 증명의 괴델 수이다"를 의미한다. (b)에서 논리식 \(\tau\)는 대각화(diagonalization) 과정을 표현한다. 즉, 어떤 논리식에 그 자신의 괴델 수를 대입하는 과정을 산술화한 것이다.
이와 같은 논리식 \(\pi\)와 \(\tau\)가 존재한다는 것은 괴델 수매김을 통해 논리식의 구문적 성질을 산술적 성질로 표현할 수 있다는 것을 의미한다. 즉, "이 문장은 증명할 수 없다"와 같은 상위수학적 진술을 일계논리 내에서 형식화할 수 있게 된다.
문제 19.2. 괴델의 '대각화 보조정리'에 대하여 조사해 보자.
3. 괴델의 불완전성 정리
이제 괴델의 불완전성 정리를 살펴보자. 핵심 아이디어를 바탕으로, \(p\)가 논리식 \((\forall x_1)(\lnot \pi)\)의 괴델 수라고 하자. 여기서 \(\pi\)는 자유변수 \(x_0\)와 \(x_1\)을 가지고 있다. 이 논리식에서 \(x_0\)를 \(p\)로 치환한 논리식을 \(\zeta\)라고 하자.
\(\zeta\)는 자기 자신의 증명 불가능성을 주장하는 문장이다. 즉, \(\zeta\)가 참이라면 \(\zeta\)는 증명 불가능하다는 것을 의미한다.
정리 19.1. (괴델의 불완전성 정리)
페아노 산술이 무모순이면 페아노 산술에서 증명도 불가능하고 반증도 불가능한 문장이 존재한다.
증명 개요 이 정리의 증명은 다음과 같이 진행된다.
- 페아노 산술이 무모순이라고 가정하자.
- \(\zeta\)가 증명 가능하다고 가정하고, 그 증명의 괴델 수를 \(q\)라고 하자.
- 그러면 \(\pi[p/x_0,\, q/x_1]\)이 증명 가능하다.
- 그러나 \(\zeta\)의 정의에 의해 \((\forall x_1)(\lnot \pi[p/x_0])\)도 증명 가능하다.
- 이로부터 \((\lnot \pi[p/x_0,\, q/x_1])\)이 증명 가능하다.
- 이것은 모순이므로, \(\zeta\)는 증명 불가능하다.
- 유사한 방법으로 \((\lnot \zeta)\)도 증명 불가능함을 보일 수 있다.
따라서 \(\zeta\)는 페아노 산술에서 증명도 불가능하고 반증도 불가능한 문장이다.
불완전성 정리는 수학의 불완전성을 의미하는 것이 아니며, 페아노 산술을 포함한 공리계의 특성을 나타낼 뿐이다. 오히려, 불완전성 정리는 단일 형식계를 통해 '수학의 세계'를 완성할 수 없다는 점을 시사하므로, 수학의 세계에서 인간의 유의미한 역할에 대한 긍정적인 측면을 드러낸다고 할 수 있다.
4. 제 2 불완전성 정리
괴델의 제 2 불완전성 정리는 페아노 산술이 자신의 무모순성을 증명할 수 없다는 것을 보여준다. [이 정리와 구분하기 위하여 정리 19.1을 '제 1 불완전성 정리'라고도 부른다.]
정리 19.2. (제 2 불완전성 정리)
만약 페아노 산술 \(\mathrm{PA}\)가 무모순이면, \(\mathrm{PA}\)의 무모순성을 나타내는 논리식은 증명 불가능하다.
증명
PA의 무모순성을 나타내는 논리식을 \(\gamma\)라고 하자. 불완전성 정리(19.1)에 의하여 증명과 반증이 불가능한 논리식 \(\zeta\)가 존재한다. \(\gamma\)가 PA의 무모순성을 나타내는데, \(\zeta\)가 증명과 반증이 불가능한 논리식이므로 \(\mathrm{PA}\cup\left\{ \gamma \right\} \vdash \zeta\)가 성립한다. 따라서 추론 정리에 의하여 \(\mathrm{PA}\vdash (\gamma \rightarrow \zeta)\)를 얻는다. 만약 PA로부터 \(\gamma\)가 추론 가능하다면 MP에 의하여 \(\gamma\)의 증명이 존재한다. 이것은 모순이므로 \(\gamma\)는 증명 불가능하다.
자연수계는 집합론을 사용하여 페아노 공리계를 만족시키도록 구성될 수 있다. 그러므로 집합론의 ZF 공리계는 페아노 공리계의 무모순성을 증명하기에 충분하다. 즉 페아노 산술은 스스로의 무모순성을 증명할 수 없지만 그보다 더 큰 체계에서 페아노 산술의 무모순성을 증명할 수 있다. 그러나 이 경우에도 더 큰 체계의 무모순성과 관련된 문제는 여전히 남아 있다.