5.13 제1 불완전성 정리의 정식화와 전제 조건

1. 제1 불완전성 정리의 정밀한 진술

1.1 괴델의 원래 진술(1931)

페아노 산술(PA)을 포함하는 $\omega$ -무모순(ω-Consistent) 형식 체계 $\mathcal{F}$ 에 대해, $\mathcal{F}$ 의 언어로 표현 가능하지만 $\mathcal{F}$ 내에서 증명도 반증도 불가능한 문장이 존재한다.

1.2 로서의 강화된 진술(1936)

페아노 산술을 포함하는 무모순(Consistent) 형식 체계 $\mathcal{F}$ 에 대해, $\mathcal{F}$ 의 언어로 표현 가능하지만 $\mathcal{F}$ 내에서 증명도 반증도 불가능한 문장이 존재한다.

로서(J. Barkley Rosser)의 개선은 전제 조건을 $\omega$ -무모순성에서 단순 무모순성으로 약화시킨 것이다.

1.3 현대적 표준 진술

효과적으로 공리화되고(Effectively Axiomatized), 충분히 강력하며(Sufficiently Powerful), 무모순한(Consistent) 형식 체계 $\mathcal{F}$ 에 대해, $\mathcal{F}$ 에서 결정 불가능한(증명도 반증도 불가능한) 문장이 존재한다.

2. 전제 조건의 상세 분석

2.1 전제 1: 효과적 공리화(Effective Axiomatization)

형식 체계 $\mathcal{F}$ 의 공리 집합 $\text{Ax}$ 가 결정 가능(Decidable)해야 한다. 즉, 임의의 공식 $\phi$ 에 대해 $\phi \in \text{Ax}$ 인지 아닌지를 판정하는 알고리즘이 존재해야 한다.

필요 이유: 증명 관계 $\text{Proof}(m, n)$ 이 원시 재귀적(따라서 PA에서 표현 가능)이려면, 공리의 판별이 기계적으로 가능해야 한다. 공리 집합이 결정 불가능하면, 증명의 유효성을 기계적으로 검증할 수 없다.

충족하는 체계의 예: PA(귀납법 공리 도식의 각 인스턴스가 기계적으로 식별 가능), ZFC(체르멜로-프렝켈 집합론 + 선택 공리).

위반하는 체계의 예: “표준 모형에서 참인 모든 산술적 문장“을 공리로 취한 체계. 이 체계는 완전하지만, 공리 집합이 결정 불가능하다.

2.2 전제 2: 충분한 표현력(Sufficient Expressive Power)

형식 체계 $\mathcal{F}$ 가 기초적인 산술을 “포함“해야 한다. “포함“의 정밀한 의미는 다음과 같다:

표현 가능성(Representability): 모든 재귀적 함수(또는 동등하게, 모든 원시 재귀 함수)가 $\mathcal{F}$ 내에서 표현 가능해야 한다.

함수 $f: \mathbb{N}^n \rightarrow \mathbb{N}$ 가 $\mathcal{F}$ 에서 표현 가능하다 함은, $\mathcal{F}$ 의 공식 $\phi_f(x_1, \ldots, x_n, y)$ 가 존재하여 모든 $a_1, \ldots, a_n, b \in \mathbb{N}$ 에 대해:

$f(a_1, \ldots, a_n) = b \iff \mathcal{F} \vdash \phi_f(\overline{a_1}, \ldots, \overline{a_n}, \overline{b})$
$f(a_1, \ldots, a_n) = b \implies \mathcal{F} \vdash \forall y \, (\phi_f(\overline{a_1}, \ldots, \overline{a_n}, y) \rightarrow y = \overline{b})$

최소 요구 체계: 불완전성 정리가 적용되는 가장 약한 체계는 로빈슨 산술 $Q$ (Robinson Arithmetic)이다. $Q$ 는 PA에서 귀납법 공리 도식을 제거한 유한 공리 체계이며, 모든 재귀적 함수를 표현할 수 있을 만큼 충분히 강력하다.

2.3 전제 3: 무모순성(Consistency)

$\mathcal{F}$ 가 무모순해야 한다: 어떤 문장 $\phi$ 에 대해서도 $\mathcal{F} \vdash \phi$ 와 $\mathcal{F} \vdash \neg\phi$ 가 동시에 성립하지 않는다.

필요 이유: 무모순하지 않은 체계에서는 모든 문장이 증명 가능하므로(폭발 원리, Ex Falso Quodlibet), 결정 불가능한 문장이 존재하지 않는다. 불완전성 정리는 무모순 체계에 대해서만 의미가 있다.

3. $\omega$ -무모순성과 단순 무모순성

3.1 $\omega$ -무모순성의 정의

형식 체계 $\mathcal{F}$ 가 $\omega$ -무모순( $\omega$ -Consistent)하다 함은, 어떤 공식 $\phi(x)$ 에 대해서도 다음이 성립하지 않음을 의미한다:

$\mathcal{F} \vdash \phi(\overline{0}), \quad \mathcal{F} \vdash \phi(\overline{1}), \quad \mathcal{F} \vdash \phi(\overline{2}), \quad \ldots \quad \text{그리고 동시에} \quad \mathcal{F} \vdash \exists x \, \neg\phi(x)$

즉, $\phi$ 가 각 자연수에 대해 성립하면서 동시에 “ $\phi$ 가 성립하지 않는 수가 존재한다“가 증명 가능한 것은 허용되지 않는다.

관계

$\omega$ -무모순성은 단순 무모순성보다 강한 조건이다:

$\omega\text{-무모순} \implies \text{무모순}$

역은 성립하지 않는다. 무모순하지만 $\omega$ -무모순하지 않은 체계가 존재한다.

3.2 로서의 개선의 의의

괴델의 원래 증명은 $\omega$ -무모순성을 가정하지만, 로서는 괴델 문장을 변형하여 단순 무모순성만으로도 결정 불가능 문장의 존재를 증명하였다. 로서 문장(Rosser Sentence) $R$ 은:

$R \leftrightarrow \forall x \, (\text{Prf}(x, \ulcorner R \urcorner) \rightarrow \exists y \leq x \, \text{Prf}(y, \ulcorner \neg R \urcorner))$

“ $R$ 이 증명 가능하다면, 더 짧은(작은 괴델 수의) $\neg R$ 의 증명이 존재한다.”

전제 조건이 위반되는 경우

효과적 공리화의 위반

$\text{Th}(\mathbb{N}) = \{\phi \mid \mathbb{N} \models \phi\}$ (표준 자연수에서 참인 모든 산술적 문장의 집합)은 완전한 이론이다. 모든 문장 $\phi$ 에 대해 $\phi \in \text{Th}(\mathbb{N})$ 또는 $\neg\phi \in \text{Th}(\mathbb{N})$ 이다. 그러나 $\text{Th}(\mathbb{N})$ 은 효과적으로 공리화되지 않는다(결정 불가능). 불완전성 정리의 전제 1이 위반되며, 실제로 이 이론은 완전하다.

충분한 표현력의 위반

프레스버거 산술(Presburger Arithmetic)은 자연수의 덧셈만을 포함하는 산술 체계이다(곱셈 없음). 프레스버거 산술은 완전하고 결정 가능하다(Presburger, 1929). 곱셈의 부재로 인해 괴델 수 부여 기법(소수 거듭제곱)이 불가능하며, 자기 참조적 구성이 표현 불가능하다. 불완전성 정리의 전제 2가 위반된다.

무모순성의 위반

무모순하지 않은 체계에서는 모든 문장이 증명 가능하다(폭발 원리). 따라서 결정 불가능 문장이 존재하지 않으며, 불완전성 정리가 의미 없다.

전제 조건의 분석적 의의

불완전성 정리의 전제 조건 분석은 “어떤 체계에서 불완전성이 발생하는가“를 정밀하게 규정한다.

핵심 통찰: 형식 체계가 자기 자신의 구문론적 성질을 산술적으로 표현할 수 있을 만큼 충분히 강력하면(전제 2), 효과적으로 공리화되어 있고(전제 1), 무모순하다면(전제 3), 불완전성이 불가피하다.

이 통찰은 “계산 가능한 체계는 충분히 강력하면서 동시에 완전할 수 없다“는 근본적 결론으로 이어지며, 인공지능의 이론적 한계—알고리즘에 기반한 체계가 모든 수학적 진리를 포착할 수 없다—를 규정한다.