5.8 소인수 분해를 이용한 기호열의 산술적 인코딩

1. 소인수 분해의 유일성과 인코딩의 기반

산술의 기본 정리(Fundamental Theorem of Arithmetic)는 모든 자연수 $n > 1$ 이 소수(Prime Number)의 곱으로 유일하게 표현됨을 보장한다:

$n = p_1^{a_1} \cdot p_2^{a_2} \cdot \cdots \cdot p_k^{a_k}$

여기서 $p_1 < p_2 < \cdots < p_k$ 는 소수이고, $a_i \geq 1$ 이다. 이 유일성이 소인수 분해에 의한 인코딩의 단사성(Injectivity)을 보장하는 수학적 기반이다.

자연수의 유한 열에서 자연수로의 인코딩

인코딩 함수의 정의

유한 열 $(a_1, a_2, \ldots, a_n)$ 에 대해 인코딩 함수 $\text{enc}$ 를 다음과 같이 정의한다:

$\text{enc}(a_1, a_2, \ldots, a_n) = \prod_{i=1}^{n} p_i^{a_i + 1}$

여기서 $p_i$ 는 $i$ 번째 소수이고, 지수에 1을 더하는 것은 $a_i = 0$ 인 경우에도 해당 소수가 인수로 나타나도록 하여 열의 길이 정보를 보존하기 위함이다.

대안적으로, 열의 길이를 별도로 인코딩하는 방식:

$\text{enc}'(a_1, a_2, \ldots, a_n) = 2^n \cdot \prod_{i=1}^{n} p_{i+1}^{a_i}$

이 방식에서 $2^n$ 이 열의 길이 $n$ 을 인코딩한다.

표준적 인코딩(괴델의 원래 방식)

가장 표준적인 인코딩은 지수에 1을 더하지 않는 단순한 형태이다:

$\text{enc}(a_1, a_2, \ldots, a_n) = \prod_{i=1}^{n} p_i^{a_i}$

이 방식에서 열의 끝부분에 0이 포함된 열과 그렇지 않은 열을 구별하기 어려우므로, 실제로는 $a_i \geq 1$ 인 인코딩(기호의 괴델 수가 1 이상)이 사용된다.

2. 인코딩과 디코딩의 원시 재귀성

2.1 소수 관련 원시 재귀 함수

인코딩과 디코딩에 필요한 소수 관련 함수들이 모두 원시 재귀적(Primitive Recursive)임을 확인한다.

소수 판별: $\text{Prime}(x)$ ≡ $x > 1 \wedge \forall y \leq x \, (y \mid x \rightarrow (y = 1 \vee y = x))$

제한 양화(Bounded Quantification)만을 포함하므로 원시 재귀적이다.

$n$ 번째 소수: $p(n)$ 을 $n$ 번째 소수로 정의한다. $p(0) = 2, p(1) = 3, p(2) = 5, \ldots$

$p(n+1)$ 은 $p(n)! + 1$ 이하에서 $p(n)$ 보다 큰 가장 작은 소수이다(유클리드의 소수 무한성 증명에 의해 이 범위 내에 소수가 존재). 제한 무한화(Bounded Minimization)로 정의되므로 원시 재귀적이다.

지수 추출: $\text{exp}(g, p)$ = $g$ 의 소인수분해에서 소수 $p$ 의 지수

$\text{exp}(g, p) = \mu k \leq g \, [\neg(p^{k+1} \mid g)]$

$p^{k+1}$ 이 $g$ 를 나누지 않는 가장 작은 $k$ 가 $p$ 의 지수이다. 제한 무한화이므로 원시 재귀적이다.

디코딩 함수

열의 $i$ 번째 원소를 추출하는 디코딩 함수:

$\text{decode}(g, i) = \text{exp}(g, p(i))$

열의 길이를 추출하는 함수:

$\text{length}(g) = \mu i \leq g \, [p(i+1) \nmid g \vee g = 0]$

$g$ 를 나누지 않는 가장 작은 소수의 인덱스 - 1이 열의 길이이다.

기호열의 산술적 인코딩 예시

예시 1: 항 $S(S(0))$ 의 인코딩

기호열: $S, (, S, (, 0, ), )$

각 기호의 괴델 수 (이전 절의 부호화 사용): $3, 17, 3, 17, 1, 19, 19$

기호열의 괴델 수:

$g = 2^3 \cdot 3^{17} \cdot 5^3 \cdot 7^{17} \cdot 11^1 \cdot 13^{19} \cdot 17^{19}$

2.2 예시 2: 공식 $\forall x_0 \, \neg(0 = x_0 \rightarrow 0 = 0)$ 의 인코딩

기호열: $\forall, x_0, \neg, (, 0, =, x_0, \rightarrow, 0, =, 0, )$

각 기호의 괴델 수: $15, 23, 11, 17, 1, 9, 23, 13, 1, 9, 1, 19$

$g = 2^{15} \cdot 3^{23} \cdot 5^{11} \cdot 7^{17} \cdot 11^1 \cdot 13^9 \cdot 17^{23} \cdot 19^{13} \cdot 23^1 \cdot 29^9 \cdot 31^1 \cdot 37^{19}$

구문론적 연산의 산술화

연결(Concatenation)

두 기호열의 연결을 산술적으로 표현한다. 길이 $m$ 의 열 $g_1$ 과 길이 $n$ 의 열 $g_2$ 의 연결:

$\text{concat}(g_1, g_2) = g_1 \cdot \prod_{i=1}^{n} p(m+i)^{\text{decode}(g_2, i)}$

$g_1$ 의 소인수분해를 유지하면서, $g_2$ 의 원소를 $g_1$ 이후의 소수에 대응시킨다.

2.3 대입(Substitution)

공식 $\phi$ 내의 변수 $x_i$ 를 항 $t$ 로 대입하는 연산 $\text{sub}(\ulcorner \phi \urcorner, i, \ulcorner t \urcorner)$ 도 원시 재귀적으로 정의 가능하다. 이 함수는 $\phi$ 의 괴델 수를 입력으로 받아, $x_i$ 의 모든 자유 출현을 $t$ 로 대체한 공식의 괴델 수를 출력한다.

대입의 원시 재귀성은 대각선 보조정리(Diagonal Lemma)의 증명에서 핵심적으로 사용된다.

3. 증명 관계의 산술화

3.1 $\text{Proof}(x, y)$ 의 정의

“ $x$ 는 괴델 수 $y$ 를 가진 공식의 PA 증명의 괴델 수이다“를 산술적 관계로 정의한다:

$\text{Proof}(x, y)$ ≡ 다음이 모두 성립한다:

$x$ 는 공식 열의 괴델 수이다.
열의 마지막 원소의 괴델 수가 $y$ 이다.
열의 각 원소는 PA의 공리이거나, 앞선 원소들로부터 전건 긍정 또는 전칭 일반화에 의해 도출된 것이다.

각 조건이 원시 재귀적으로 검사 가능하므로, $\text{Proof}(x, y)$ 는 원시 재귀적 관계이다.

4. 산술적 인코딩의 이론적 역할

소인수 분해에 의한 기호열의 산술적 인코딩은 괴델 증명의 기술적 핵심이다. 이 인코딩에 의해:

형식 체계의 모든 구문론적 대상이 자연수의 영역으로 사상(Map)된다.
구문론적 관계가 원시 재귀적 산술 관계로 변환된다.
원시 재귀적 관계가 PA 내에서 표현(Represent) 가능하다.
따라서 PA가 자기 자신의 구문론적 성질에 관한 산술적 문장을 표현할 수 있다.

이 네 단계의 연쇄가 괴델 문장—“이 문장은 PA에서 증명 불가능하다”—의 구성을 가능하게 하며, 불완전성 정리의 증명이 완성된다.