5.12 괴델 문장(G)의 구성: “이 문장은 증명 불가능하다”

1. 괴델 문장의 구성

괴델 문장(Gödel Sentence) $G$ 는 대각화 보조 정리(Diagonal Lemma)를 증명 불가능성 술어 $\neg\text{Prov}(x)$ 에 적용하여 구성된다.

1.1 구성 절차

단계 1: 증명 가능성 술어 $\text{Prov}(y)$ 를 PA 내에서 정의한다:

$\text{Prov}(y) \equiv \exists x \, \text{Prf}(x, y)$

여기서 $\text{Prf}(x, y)$ 는 “ $x$ 는 괴델 수 $y$ 를 가진 공식의 PA 증명의 괴델 수이다“를 표현하는 PA의 공식이다.

단계 2: 대각화 보조 정리를 $\psi(x) \equiv \neg\text{Prov}(x)$ 에 적용한다.

보조 정리에 의해, 다음을 만족하는 문장 $G$ 가 존재한다:

$\text{PA} \vdash G \leftrightarrow \neg\text{Prov}(\overline{\ulcorner G \urcorner})$

1.2 괴델 문장의 의미

$G$ 는 PA 내에서 증명 가능하게 다음과 동치이다:

$\neg\text{Prov}(\overline{\ulcorner G \urcorner})$

이 공식의 의미: “괴델 수 $\ulcorner G \urcorner$ 를 가진 공식(즉, $G$ 자체)은 PA에서 증명 가능하지 않다.”

따라서 $G$ 는 “이 문장은 PA에서 증명 불가능하다“를 산술적으로 표현한 문장이다.

괴델 문장의 구성 원리 상세

대각화의 메커니즘

괴델 문장의 구성을 더 구체적으로 전개한다.

보조 공식의 정의: 자유 변수 $v$ 를 하나 가진 공식 $\theta(v)$ 를 다음과 같이 정의한다:

$\theta(v) \equiv \neg\exists x \, \text{Prf}(x, \text{diag}(v))$

여기서 $\text{diag}(v)$ 는 “괴델 수 $v$ 를 가진 공식의 자유 변수에 $\overline{v}$ 를 대입한 결과 문장의 괴델 수“를 반환하는 함수의 PA 내 표현이다.

$\theta(v)$ 의 의미: “괴델 수 $v$ 를 가진 공식을 대각화한 결과 문장은 PA에서 증명 불가능하다.”

대각화: $\theta(v)$ 자체의 괴델 수를 $t = \ulcorner \theta(v) \urcorner$ 라 하자. 괴델 문장 $G$ 는 $\theta$ 를 대각화한 것이다:

$G \equiv \theta(\overline{t})$

$G$ 의 의미를 풀어쓰면:

$G = \theta(\overline{t})$ = “괴델 수 $t$ 를 가진 공식(즉, $\theta(v)$ )을 대각화한 결과 문장은 PA에서 증명 불가능하다.”
$\theta(v)$ 를 대각화한 결과는 $\theta(\overline{t}) = G$ 자체이다.
따라서 $G$ = “문장 $G$ 는 PA에서 증명 불가능하다.”

자기 참조의 간접성

$G$ 는 “이 문장“이라는 직접적 자기 참조를 사용하지 않는다. 대신, $G$ 는 특정 괴델 수를 가진 공식에 관해 말하며, 이 괴델 수가 우연히(그러나 필연적으로) $G$ 자체의 괴델 수와 일치하도록 구성된다. 이 간접적 자기 참조가 대각화 보조 정리의 핵심 기제이다.

괴델 문장의 산술적 내용

$G$ 는 PA의 언어로 작성된 순수 산술적 문장이다. $G$ 에는 “증명”, “공식”, “괴델 수” 등의 메타수학적 용어가 직접 나타나지 않는다. $G$ 는 자연수의 덧셈, 곱셈, 등호만을 사용하는 복잡한 산술적 문장이며, 그 산술적 내용이 메타수학적 해석 하에서 “이 문장은 증명 불가능하다“를 표현하는 것이다.

구체적으로, $G$ 는 다음과 같은 형태의 산술적 문장이다:

$\forall x \, \neg R(x, \overline{\ulcorner G \urcorner})$

여기서 $R(x, y)$ 는 $\text{Prf}(x, y)$ 를 표현하는 PA의 공식이다. 이 문장은 “어떤 자연수 $x$ 도 자연수 $\ulcorner G \urcorner$ 와 특정 산술적 관계 $R$ 을 만족하지 않는다“라는 순수 산술적 진술이다. 이 산술적 진술이 메타수학적으로 “괴델 수 $\ulcorner G \urcorner$ 를 가진 공식의 증명이 존재하지 않는다“로 해석되는 것이다.

2. 괴델 문장의 진리값

2.1 $G$ 가 참임을 보이는 비형식적 논증

$G$ 가 거짓이라고 가정하자. 그러면 $\neg G$ 가 참이고, $\text{Prov}(\ulcorner G \urcorner)$ 가 참이다. 즉, $G$ 의 PA 증명이 존재한다. PA가 건전(Sound)하므로 PA에서 증명 가능한 문장은 참이다. 따라서 $G$ 가 참이다. 이는 $G$ 가 거짓이라는 가정에 모순된다. 따라서 $G$ 는 참이다.

$G$ 가 참이므로, $\neg\text{Prov}(\ulcorner G \urcorner)$ 가 참이다. 즉, $G$ 는 PA에서 증명 불가능하다.

결론: $G$ 는 참이지만 PA에서 증명 불가능한 문장이다.

2.2 형식적 분석(제1 불완전성 정리)

위의 비형식적 논증을 형식화하면 제1 불완전성 정리가 된다:

PA가 무모순(Consistent)이면 PA $\nvdash G$ ( $G$ 는 증명 불가능).
PA가 $\omega$ -무모순( $\omega$ -Consistent)이면 PA $\nvdash \neg G$ ( $\neg G$ 도 증명 불가능).

따라서 PA가 $\omega$ -무모순이면 $G$ 는 PA에서 결정 불가능(증명도 반증도 불가능)하다.

로서(J. Barkley Rosser)는 1936년 $\omega$ -무모순성 조건을 단순 무모순성(Simple Consistency)으로 약화시킨 강화된 불완전성 정리를 증명하였다.

3. 거짓말쟁이 역리와의 비교

측면	거짓말쟁이 문장	괴델 문장
형태	“이 문장은 거짓이다”	“이 문장은 증명 불가능하다”
자기 참조 대상	진리(Truth)	증명 가능성(Provability)
결과	역리(Paradox)—참도 거짓도 불가	비역리—참이지만 증명 불가능
전제	진리 술어의 형식 체계 내 정의 가능성	증명 가능성 술어의 형식 체계 내 정의 가능성
귀결	타르스키 정의 불가능성 정리	괴델 불완전성 정리

핵심적 차이: 거짓말쟁이 문장은 역리를 산출하여 진리 술어가 체계 내에서 정의 불가능함을 보여주고, 괴델 문장은 역리를 산출하지 않고 참이지만 증명 불가능한 문장의 존재를 보여준다. “참“과 “증명 가능“이 동일하지 않기 때문에 괴델 문장은 역리가 아닌 비완전성의 증거가 된다.

4. 괴델 문장의 독립성(Independence)

$G$ 는 PA로부터 독립(Independent)이다: PA $\nvdash G$ 이고 PA $\nvdash \neg G$ .

이는 PA에 $G$ 를 공리로 추가한 체계 PA + $G$ 도 무모순하고, PA에 $\neg G$ 를 공리로 추가한 체계 PA + $\neg G$ 도 무모순함을 의미한다.

PA + $G$ 는 표준 모형 $\mathbb{N}$ 을 가지며, PA + $\neg G$ 는 비표준 모형(Nonstandard Model)만을 가진다.

괴델 문장은 형식 체계의 표현력이 자기 참조를 가능하게 할 만큼 충분히 강력할 때 불가피하게 발생하는 불완전성의 구체적 증거이며, 형식적 증명과 수학적 진리 사이의 근본적 간극을 드러내는 역사적 구성물이다.