5.6 괴델 수(Gödel Number) 부여 기법의 원리

1. 괴델 수 부여의 핵심 아이디어

괴델 수 부여(Gödel Numbering)는 형식 체계의 모든 구문론적 대상—기호, 항, 공식, 증명—을 자연수에 체계적으로 대응시키는 부호화(Encoding) 기법이다. 이 부호화에 의해 형식 체계에 관한 메타수학적 명제(“이 공식은 증명 가능하다” 등)가 산술적 명제(“이 자연수는 특정 성질을 만족한다”)로 변환된다. 이 변환이 형식 체계의 자기 참조(Self-Reference)를 가능하게 하는 핵심 기제이다.

2. 기호의 부호화

형식 체계의 각 기본 기호에 고유한 홀수 자연수를 대응시킨다. 괴델의 원래 부호화에서:

기호	의미	괴델 수
$0$	영	1
$S$	후자	3
$+$	덧셈	5
$\times$	곱셈	7
$=$	등호	9
$($	왼쪽 괄호	11
$)$	오른쪽 괄호	13
$\neg$	부정	15
$\rightarrow$	조건	17
$\forall$	전칭 양화사	19
$x_i$	변수 $i$	$21 + 2i$

3. 유한 열의 부호화: 소수 거듭제곱 기법

괴델의 핵심적 부호화 기법은 소수 거듭제곱(Prime Power) 방법에 의한 유한 열의 부호화이다. 자연수의 유한 열 $(a_1, a_2, \ldots, a_n)$ 을 다음과 같이 단일 자연수로 부호화한다:

$\ulcorner a_1, a_2, \ldots, a_n \urcorner = p_1^{a_1} \cdot p_2^{a_2} \cdot \cdots \cdot p_n^{a_n} = \prod_{i=1}^{n} p_i^{a_i}$

여기서 $p_i$ 는 $i$ 번째 소수이다: $p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, \ldots$

부호화의 유일성

산술의 기본 정리(Fundamental Theorem of Arithmetic)에 의해 모든 자연수 $> 1$ 은 소인수분해가 유일하다. 따라서 서로 다른 유한 열은 서로 다른 괴델 수에 대응하며, 괴델 수로부터 원래 열을 유일하게 복원할 수 있다.

복호화(Decoding)

괴델 수 $g = \prod_{i=1}^{n} p_i^{a_i}$ 가 주어졌을 때:

열의 $i$ 번째 원소: $a_i = \text{exp}(g, p_i)$ (자연수 $g$ 의 소인수분해에서 $p_i$ 의 지수)
열의 길이: 지수가 0이 아닌 최대 소수의 인덱스

$\text{exp}(g, p)$ 함수는 원시 재귀적(Primitive Recursive)이며, 따라서 복호화가 기계적으로 수행 가능하다.

공식의 괴델 수

공식(Formula)은 기호의 유한 열이므로, 각 기호의 괴델 수를 열로 나열하고 소수 거듭제곱 기법을 적용한다.

예시

공식 $\forall x_0 \, (0 = x_0)$ 의 기호 열: $\forall, x_0, (, 0, =, x_0, )$

각 기호의 괴델 수: $19, 21, 11, 1, 9, 21, 13$

공식의 괴델 수:

$\ulcorner \forall x_0 \, (0 = x_0) \urcorner = 2^{19} \cdot 3^{21} \cdot 5^{11} \cdot 7^{1} \cdot 11^{9} \cdot 13^{21} \cdot 17^{13}$

이 수는 극도로 크지만, 이론적 분석에서 수의 크기는 중요하지 않다. 중요한 것은 부호화의 체계성과 복호화의 가능성이다.

4. 증명의 괴델 수

형식적 증명은 공식의 유한 열이다. 증명 $(\phi_1, \phi_2, \ldots, \phi_k)$ 의 괴델 수는:

$\ulcorner \phi_1, \phi_2, \ldots, \phi_k \urcorner = 2^{\ulcorner \phi_1 \urcorner} \cdot 3^{\ulcorner \phi_2 \urcorner} \cdot \cdots \cdot p_k^{\ulcorner \phi_k \urcorner}$

즉, 각 공식의 괴델 수를 원소로 하는 열을 다시 소수 거듭제곱으로 부호화한다.

구문론적 관계의 산술화

괴델 수 부여에 의해 형식 체계의 구문론적 관계가 자연수 위의 산술적 관계로 변환된다.

핵심 관계들

변수 판별: $\text{Var}(x)$ ≡ “ $x$ 는 변수의 괴델 수이다”
→ $x \geq 21 \wedge x$ 는 홀수 (원시 재귀적)

항 판별: $\text{Term}(x)$ ≡ “ $x$ 는 항의 괴델 수이다”
→ 귀납적으로 정의. 원시 재귀적.

공식 판별: $\text{Formula}(x)$ ≡ “ $x$ 는 적격식의 괴델 수이다”
→ 귀납적으로 정의. 원시 재귀적.

공리 판별: $\text{Axiom}(x)$ ≡ “ $x$ 는 공리의 괴델 수이다”
→ 원시 재귀적 (공리 도식의 각 인스턴스가 기계적으로 식별 가능).

증명 관계: $\text{Proof}(x, y)$ ≡ “ $x$ 는 괴델 수 $y$ 를 가진 공식의 증명의 괴델 수이다”
→ 원시 재귀적. $x$ 로 부호화된 공식 열의 각 원소가 공리이거나 앞선 원소들로부터 추론 규칙에 의해 도출되었는지를 검사.

증명 가능성: $\text{Prov}(y)$ ≡ “ $\exists x \, \text{Proof}(x, y)$ ” ≡ “괴델 수 $y$ 를 가진 공식이 증명 가능하다”
→ $\Sigma_1^0$ 관계 (존재 양화가 포함되므로 원시 재귀적이 아닌 RE).

원시 재귀성의 의의

위 관계들이 원시 재귀적이라는 것은 괴델 증명에서 본질적이다. 원시 재귀적 관계는 페아노 산술(PA) 내에서 표현(Represent) 가능하기 때문이다. 구체적으로, 원시 재귀적 관계 $R(x_1, \ldots, x_n)$ 에 대해 PA의 공식 $\phi_R(x_1, \ldots, x_n)$ 이 존재하여:

$R(a_1, \ldots, a_n)$ 이 참이면 $\text{PA} \vdash \phi_R(\overline{a_1}, \ldots, \overline{a_n})$
$R(a_1, \ldots, a_n)$ 이 거짓이면 $\text{PA} \vdash \neg \phi_R(\overline{a_1}, \ldots, \overline{a_n})$

이 표현 가능성에 의해, “이 공식은 증명 가능하다“라는 메타수학적 명제가 PA의 산술적 문장으로 표현될 수 있으며, 이것이 괴델 문장의 구성을 가능하게 한다.

괴델 수 부여의 이론적 의의

괴델 수 부여는 “언어가 자기 자신에 관해 말한다“는 자기 참조(Self-Reference)의 형식적 실현이다. 형식 체계의 구문론적 대상을 자연수로 부호화함으로써, 형식 체계가 자기 자신의 구문론적 성질에 관한 산술적 진술을 표현할 수 있게 된다.

이 자기 참조 가능성은 “거짓말쟁이 역리“의 형식적 유사물—괴델 문장 “이 문장은 증명 불가능하다”—의 구성을 가능하게 하며, 이것이 불완전성 정리의 핵심이다.

괴델 수 부여는 현대의 프로그래밍 언어에서 프로그램이 자기 자신의 소스 코드에 접근하는 반영(Reflection) 기능, 컴파일러가 프로그래밍 언어의 구문을 데이터로 처리하는 기법, 그리고 보편 튜링 기계에서 튜링 기계의 부호화가 데이터로 처리되는 원리의 이론적 기원이다.