5.14 제1 불완전성 정리의 증명: 괴델 문장 G의 결정 불가능성

1. 증명의 구조

제1 불완전성 정리의 증명은 괴델 문장 $G$ 가 PA(또는 더 일반적으로, 전제 조건을 만족하는 형식 체계 $\mathcal{F}$ )에서 결정 불가능함을 보이는 것이다. 증명은 두 부분으로 구성된다:

$\mathcal{F}$ 가 무모순이면 $\mathcal{F} \nvdash G$ ( $G$ 는 증명 불가능)
$\mathcal{F}$ 가 $\omega$ -무모순이면 $\mathcal{F} \nvdash \neg G$ ( $\neg G$ 도 증명 불가능)

2. 전제: 괴델 문장의 성질

대각화 보조 정리에 의해 구성된 괴델 문장 $G$ 는 다음을 만족한다:

$\mathcal{F} \vdash G \leftrightarrow \neg\text{Prov}(\overline{\ulcorner G \urcorner}) \quad \cdots (*)$

여기서 $\text{Prov}(y) \equiv \exists x \, \text{Prf}(x, y)$ 이고, $\text{Prf}$ 는 증명 관계를 표현하는 $\mathcal{F}$ 의 공식이다.

또한, $\text{Prf}$ 는 원시 재귀적 관계를 정확히 표현(Represent)하므로:

자연수 $m$ 이 실제로 $G$ 의 증명의 괴델 수이면: $\mathcal{F} \vdash \text{Prf}(\overline{m}, \overline{\ulcorner G \urcorner})$
자연수 $m$ 이 $G$ 의 증명의 괴델 수가 아니면: $\mathcal{F} \vdash \neg\text{Prf}(\overline{m}, \overline{\ulcorner G \urcorner})$

부분 1: $G$ 의 증명 불가능성

정리: $\mathcal{F}$ 가 무모순이면 $\mathcal{F} \nvdash G$ .

증명: 귀류법. $\mathcal{F} \vdash G$ 라고 가정한다.

단계 1: $\mathcal{F} \vdash G$ 이므로, $G$ 의 형식적 증명 $\pi$ 가 존재한다. $\pi$ 의 괴델 수를 $m$ 이라 하면, $m$ 은 $G$ 의 증명의 괴델 수이다. 즉, $\text{Proof}(m, \ulcorner G \urcorner)$ 가 참이다.

단계 2: $\text{Prf}$ 가 $\text{Proof}$ 를 표현하므로:
$\mathcal{F} \vdash \text{Prf}(\overline{m}, \overline{\ulcorner G \urcorner})$

단계 3: 존재 양화에 의해:
$\mathcal{F} \vdash \exists x \, \text{Prf}(x, \overline{\ulcorner G \urcorner})$
$\mathcal{F} \vdash \text{Prov}(\overline{\ulcorner G \urcorner})$

단계 4: $(*)$ 에 의해 $G \leftrightarrow \neg\text{Prov}(\overline{\ulcorner G \urcorner})$ 이므로:
$\mathcal{F} \vdash \neg G$

( $\mathcal{F} \vdash G$ 와 $\mathcal{F} \vdash G \leftrightarrow \neg\text{Prov}(\overline{\ulcorner G \urcorner})$ 와 $\mathcal{F} \vdash \text{Prov}(\overline{\ulcorner G \urcorner})$ 로부터 $\mathcal{F} \vdash \neg G$ 가 도출된다.)

단계 5: 가정에 의해 $\mathcal{F} \vdash G$ 이고, 단계 4에 의해 $\mathcal{F} \vdash \neg G$ 이다. 이는 $\mathcal{F}$ 의 무모순성에 모순이다.

결론: $\mathcal{F} \nvdash G$ . $\blacksquare$

부분 2: $\neg G$ 의 증명 불가능성

정리: $\mathcal{F}$ 가 $\omega$ -무모순이면 $\mathcal{F} \nvdash \neg G$ .

증명: 귀류법. $\mathcal{F} \vdash \neg G$ 라고 가정한다.

단계 1: 부분 1에서 $\mathcal{F} \nvdash G$ 를 증명하였다( $\mathcal{F}$ 의 무모순성은 $\omega$ -무모순성에 의해 보장). 따라서 $G$ 의 형식적 증명은 존재하지 않는다.

단계 2: $G$ 의 증명이 존재하지 않으므로, 모든 자연수 $m$ 에 대해 $m$ 은 $G$ 의 증명의 괴델 수가 아니다: $\text{Proof}(m, \ulcorner G \urcorner)$ 가 거짓.

단계 3: $\text{Prf}$ 가 $\text{Proof}$ 를 표현하므로, 모든 자연수 $m$ 에 대해:
$\mathcal{F} \vdash \neg\text{Prf}(\overline{m}, \overline{\ulcorner G \urcorner})$

즉, $\mathcal{F} \vdash \neg\text{Prf}(\overline{0}, \overline{\ulcorner G \urcorner})$ , $\mathcal{F} \vdash \neg\text{Prf}(\overline{1}, \overline{\ulcorner G \urcorner})$ , $\mathcal{F} \vdash \neg\text{Prf}(\overline{2}, \overline{\ulcorner G \urcorner})$ , $\ldots$

단계 4: 가정에 의해 $\mathcal{F} \vdash \neg G$ 이다. $(*)$ 에 의해 $G \leftrightarrow \neg\text{Prov}(\overline{\ulcorner G \urcorner})$ 이므로:
$\mathcal{F} \vdash \neg\neg\text{Prov}(\overline{\ulcorner G \urcorner})$
$\mathcal{F} \vdash \text{Prov}(\overline{\ulcorner G \urcorner})$
$\mathcal{F} \vdash \exists x \, \text{Prf}(x, \overline{\ulcorner G \urcorner})$

단계 5: 단계 3에서 모든 $m$ 에 대해 $\mathcal{F} \vdash \neg\text{Prf}(\overline{m}, \overline{\ulcorner G \urcorner})$ 이고, 단계 4에서 $\mathcal{F} \vdash \exists x \, \text{Prf}(x, \overline{\ulcorner G \urcorner})$ 이다.

$\phi(x)$ 를 $\text{Prf}(x, \overline{\ulcorner G \urcorner})$ 로 놓으면:

모든 $m$ 에 대해 $\mathcal{F} \vdash \neg\phi(\overline{m})$
$\mathcal{F} \vdash \exists x \, \phi(x)$

이는 $\omega$ -무모순성의 정의에 의해 $\mathcal{F}$ 의 $\omega$ -무모순성에 모순이다.

결론: $\mathcal{F} \nvdash \neg G$ . $\blacksquare$

제1 불완전성 정리의 완성

부분 1과 부분 2를 결합하면:

$\mathcal{F}$ 가 $\omega$ -무모순이면 $\mathcal{F} \nvdash G$ 이고 $\mathcal{F} \nvdash \neg G$ 이다.

따라서 $G$ 는 $\mathcal{F}$ 에서 결정 불가능(Undecidable)한 문장이다. $\mathcal{F}$ 는 불완전(Incomplete)하다. $\blacksquare$

괴델 문장 $G$ 의 진리값

부분 1에서 $\mathcal{F} \nvdash G$ 가 증명되었다. 즉, $G$ 의 PA 증명은 존재하지 않는다. $G$ 의 내용이 “이 문장은 PA에서 증명 불가능하다“이므로, $G$ 가 주장하는 바가 사실이다. 따라서 $G$ 는 표준 자연수 $\mathbb{N}$ 에서 참이다.

결론: $G$ 는 참이지만 $\mathcal{F}$ 에서 증명 불가능한 문장이다. 이는 수학적 진리(Truth)가 형식적 증명 가능성(Provability)을 초과함을 의미한다.

불완전성의 불가피성

괴델 문장 $G$ 를 공리로 추가하여 $\mathcal{F}' = \mathcal{F} + G$ 를 구성하면, $G$ 는 $\mathcal{F}'$ 에서 증명 가능하다(공리이므로). 그러나 $\mathcal{F}'$ 도 전제 조건을 만족하므로, $\mathcal{F}'$ 에 대한 새로운 괴델 문장 $G'$ 가 존재하여 $\mathcal{F}' \nvdash G'$ 이다. 이 과정은 무한히 반복되며, 어떤 공리 추가에 의해서도 불완전성은 해소되지 않는다.

이 불가피성은 불완전성이 특정 형식 체계의 “결함“이 아니라, 충분히 강력한 형식 체계의 본질적 성질임을 보여준다.