5.11 자기 참조 문장의 구성: 대각화 보조 정리(Diagonalization Lemma)

1. 자기 참조의 형식적 문제

자기 참조(Self-Reference)란 문장이 자기 자신에 관해 말하는 것이다. “이 문장은 거짓이다”(거짓말쟁이 역리)는 자기 참조의 고전적 예이다. 괴델의 불완전성 정리에서 핵심적 역할을 하는 괴델 문장 “이 문장은 증명 불가능하다“도 자기 참조적 문장이다.

형식 체계의 언어에서 “이 문장“이라는 직접적 자기 참조 장치가 없으므로, 자기 참조를 간접적으로 구현하는 기법이 필요하다. 대각화 보조 정리(Diagonalization Lemma, 또는 고정점 보조정리, Fixed-Point Lemma)가 이 기법을 제공한다.

2. 대각화 보조 정리의 진술

정리(대각화 보조 정리, Diagonal Lemma): PA의 자유 변수를 하나 가진 임의의 공식 $\psi(x)$ 에 대해, 다음을 만족하는 문장(폐쇄식) $G$ 가 존재한다:

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

여기서 $\ulcorner G \urcorner$ 는 $G$ 의 괴델 수이고, $\overline{\ulcorner G \urcorner}$ 는 이 괴델 수의 PA 내 표기( $S^{\ulcorner G \urcorner}(0)$ )이다.

의미: 문장 $G$ 는 PA 내에서 증명 가능하게 “ $G$ 의 괴델 수가 속성 $\psi$ 를 만족한다“와 동치이다. 즉, $G$ 는 자기 자신에 관해 “ $\psi$ 가 나에게 성립한다“고 말하는 문장이다.

증명

보조 구성: 대각화 함수

대각화 함수(Diagonalization Function) $\text{diag}$ 를 정의한다. 자유 변수 $x$ 를 하나 가진 공식 $\phi(x)$ 의 괴델 수 $\ulcorner \phi(x) \urcorner$ 가 주어졌을 때:

$\text{diag}(\ulcorner \phi(x) \urcorner) = \ulcorner \phi(\overline{\ulcorner \phi(x) \urcorner}) \urcorner$

$\text{diag}$ 는 공식 $\phi(x)$ 에서 변수 $x$ 를 공식 자체의 괴델 수 $\overline{\ulcorner \phi(x) \urcorner}$ 로 대입한 결과 문장의 괴델 수를 반환한다.

$\text{diag}$ 는 대입 함수 $\text{sub}$ 의 특수한 경우이며, 원시 재귀적이다. PA 내에서 이를 표현하는 함수 기호(또는 이를 정의하는 공식)를 $d(x)$ 로 나타낸다.

2.1 증명의 구성

$\psi(x)$ 가 주어졌을 때:

단계 1: 보조 공식 $\theta(x)$ 를 정의한다:

$\theta(x) \equiv \psi(d(x))$

$\theta(x)$ 는 “변수 $x$ 에 대입된 괴델 수의 대각화 결과가 $\psi$ 를 만족한다“를 표현한다.

단계 2: $\theta(x)$ 자체의 괴델 수 $\ulcorner \theta(x) \urcorner = t$ 를 계산한다.

단계 3: $G$ 를 $\theta$ 의 대각화로 정의한다:

$G \equiv \theta(\overline{t}) = \psi(d(\overline{t}))$

단계 4: $d(\overline{t})$ 의 값을 계산한다:

$d(\overline{t}) = d(\overline{\ulcorner \theta(x) \urcorner}) = \overline{\ulcorner \theta(\overline{t}) \urcorner} = \overline{\ulcorner G \urcorner}$

마지막 등식은 $\theta(\overline{t}) = G$ 라는 정의에 의해 성립한다.

단계 5: 따라서:

$G = \psi(d(\overline{t})) = \psi(\overline{\ulcorner G \urcorner})$

PA 내에서 $d(\overline{t}) = \overline{\ulcorner G \urcorner}$ 가 증명 가능하므로:

$\text{PA} \vdash G \leftrightarrow \psi(\overline{\ulcorner G \urcorner}) \quad \blacksquare$

칸토어의 대각선 논법과의 관계

대각화 보조 정리의 명칭은 칸토어의 대각선 논법(Diagonalization)에서 유래한다. 구조적 유사성:

칸토어의 대각선 논법에서 함수 $f$ 의 열 $f_0, f_1, f_2, \ldots$ 에 대해 대각선 함수 $g(n) = f_n(n) + 1$ 을 구성한다. $g$ 는 열에서의 “자기 자신에 적용“의 변형이다.

대각화 보조 정리에서 공식 $\phi(x)$ 에 대해 $\phi$ 를 자기 자신의 괴델 수에 “적용“한 $\phi(\overline{\ulcorner \phi(x) \urcorner})$ 를 구성한다. 이는 대각선 논법의 “자기 적용” 구조를 형식 체계 내에서 재현한 것이다.

거짓말쟁이 역리와의 관계

대각화 보조 정리를 진리 술어(Truth Predicate) $\text{True}(x)$ 에 적용하면:

$G \leftrightarrow \neg\text{True}(\ulcorner G \urcorner)$

$G$ 는 “이 문장은 참이 아니다“와 동치인 문장이 된다. 이는 거짓말쟁이 역리(Liar’s Paradox)의 형식적 유사물이다.

타르스키의 정의 불가능성 정리(Tarski’s Undefinability Theorem)는 이 구성을 사용하여, 산술적 진리 집합 $\{n \mid \mathbb{N} \models \phi_n\}$ 이 PA 내에서 정의 불가능함을 증명한다.

3. 괴델 문장의 구성

대각화 보조 정리를 증명 불가능성 술어 $\neg\text{Prov}(x)$ 에 적용하면:

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

$G$ 는 “ $G$ 의 괴델 수가 증명 가능하지 않다“와 PA 내에서 동치인 문장이다. 즉:

$G \text{는 "이 문장은 PA에서 증명 불가능하다"를 산술적으로 표현한 문장이다.}$

이 $G$ 가 괴델 문장(Gödel Sentence)이며, 제1 불완전성 정리의 핵심 구성물이다.

4. 괴델 문장 $G$ 와 거짓말쟁이 문장의 차이

괴델 문장: $G \leftrightarrow \neg\text{Prov}(\ulcorner G \urcorner)$ — “이 문장은 증명 불가능하다”
거짓말쟁이 문장: $L \leftrightarrow \neg\text{True}(\ulcorner L \urcorner)$ — “이 문장은 참이 아니다”

핵심적 차이: 거짓말쟁이 문장은 역리(Paradox)를 야기하지만, 괴델 문장은 역리를 야기하지 않는다. 그 이유는 “증명 가능“과 “참“이 동일하지 않기 때문이다. 괴델 문장은 참이지만 증명 불가능한 문장으로서, 진리와 증명 가능성 사이의 간극을 드러낸다.

5. 대각화 보조 정리의 일반적 응용

대각화 보조 정리는 불완전성 정리 외에도 다수의 메타수학적 결과의 핵심 도구이다:

타르스키의 정의 불가능성 정리: 산술적 진리는 PA 내에서 정의 불가능하다.
뢰브의 정리(Löb’s Theorem): PA $\vdash \text{Prov}(\ulcorner \phi \urcorner) \rightarrow \phi$ 이면 PA $\vdash \phi$ .
클레이니의 재귀 정리: 튜링 기계가 자기 자신의 부호화에 접근할 수 있다.
로저스의 고정점 정리: 재귀 함수 이론에서의 대각화 보조 정리의 유사물.

대각화 보조 정리는 자기 참조의 형식적 구현을 위한 범용 도구이며, 현대 수리논리학과 계산 이론의 핵심적 기법이다.