5.7 괴델 번호 매김(Gödel Numbering)의 구체적 절차

1. 구체적 부호화 절차

괴델 번호 매김(Gödel Numbering)의 구체적 절차를 단계별로 기술한다. 대상 형식 체계를 일차 페아노 산술(PA)로 설정한다.

2. 단계 1: 기본 기호에 대한 괴델 수 할당

PA의 각 기본 기호에 고유한 자연수를 할당한다. 할당 방식은 관례적이며, 핵심 요구사항은 각 기호에 고유한 수가 대응되고, 기호의 유형(상수, 변수, 연산 기호, 논리 기호 등)이 괴델 수로부터 원시 재귀적으로 판별 가능한 것이다.

2.1 고정 기호의 부호화

2.2 변수의 부호화

변수 x_i에 괴델 수 23 + 2i를 할당한다:

• x_0 \mapsto 23
• x_1 \mapsto 25
• x_2 \mapsto 27
• 일반적으로 x_i \mapsto 23 + 2i

변수의 괴델 수는 23 이상의 홀수이며, 이 조건에 의해 변수와 고정 기호가 구별된다.

3. 단계 2: 유한 기호열의 부호화

기호열 s_1 s_2 \cdots s_n의 괴델 수는 각 기호의 괴델 수를 소수의 지수로 사용한다:

\#(s_1 s_2 \cdots s_n) = 2^{\#(s_1)} \cdot 3^{\#(s_2)} \cdot 5^{\#(s_3)} \cdot \cdots \cdot p_n^{\#(s_n)}

구체적 예시: 항 S(0)의 괴델 수

기호열: S, (, 0, )
각 기호의 괴델 수: 3, 17, 1, 19

\#(S(0)) = 2^3 \cdot 3^{17} \cdot 5^1 \cdot 7^{19}
= 8 \cdot 129,140,163 \cdot 5 \cdot 11,398,895,185,373,143

계산 결과는 매우 큰 수이지만, 이론적 분석에서 수의 실제 크기는 관련이 없다.

구체적 예시: 공식 0 = 0의 괴델 수

기호열: 0, =, 0
각 기호의 괴델 수: 1, 9, 1

\#(0 = 0) = 2^1 \cdot 3^9 \cdot 5^1 = 2 \cdot 19683 \cdot 5 = 196,830

3.1 구체적 예시: 공식 \neg(0 = S(0))의 괴델 수

기호열: \neg, (, 0, =, S, (, 0, ), )
각 기호의 괴델 수: 11, 17, 1, 9, 3, 17, 1, 19, 19

\#(\neg(0 = S(0))) = 2^{11} \cdot 3^{17} \cdot 5^1 \cdot 7^9 \cdot 11^3 \cdot 13^{17} \cdot 17^1 \cdot 19^{19} \cdot 23^{19}

단계 3: 공식 열(증명)의 부호화

형식적 증명은 공식의 유한 열 (\phi_1, \phi_2, \ldots, \phi_k)이다. 증명의 괴델 수는 각 공식의 괴델 수를 원소로 하는 열의 부호화이다:

\#(\phi_1, \phi_2, \ldots, \phi_k) = 2^{\#(\phi_1)} \cdot 3^{\#(\phi_2)} \cdot \cdots \cdot p_k^{\#(\phi_k)}

이중 부호화(Double Encoding): 기호 → 기호열(공식) → 공식열(증명)의 두 단계 부호화가 적용된다.

4. 복호화(Decoding) 절차

4.1 열의 길이 추출

괴델 수 g로부터 열의 길이 \text{len}(g)를 추출한다:

\text{len}(g) = \max\{i \mid p_i \text{ divides } g\}

즉, g를 나누는 가장 큰 소수의 인덱스가 열의 길이이다.

열의 i번째 원소 추출

\text{elem}(g, i) = \text{exp}(g, p_i)

여기서 \text{exp}(g, p)는 g의 소인수분해에서 소수 p의 지수이다:

\text{exp}(g, p) = \max\{k \mid p^k \text{ divides } g\}

\text{exp} 함수는 원시 재귀적이다.

베타 함수 기법(β-Function Technique)

괴델의 대안적 부호화

괴델은 소수 거듭제곱 기법 외에, 중국인의 나머지 정리(Chinese Remainder Theorem)에 기반한 베타 함수(β-Function) 기법도 사용하였다. 이 기법은 소수 분포에 관한 가정 없이 유한 열을 부호화할 수 있다는 이점이 있다.

베타 함수의 정의

\beta(c, d, i) = \text{rem}(c, 1 + (i+1) \cdot d)

여기서 \text{rem}(a, b)는 a를 b로 나눈 나머지이다.

4.2 베타 함수 보조정리

임의의 자연수 열 a_0, a_1, \ldots, a_n에 대해, 자연수 c와 d가 존재하여 모든 i \leq n에 대해:

\beta(c, d, i) = a_i

이 보조정리의 증명은 중국인의 나머지 정리에 의해 이루어지며, d를 (n+1)! \cdot \max(a_0, \ldots, a_n)보다 크게 선택하면 1 + d, 1 + 2d, \ldots, 1 + (n+1)d가 쌍별 서로소(Pairwise Coprime)가 되어 중국인의 나머지 정리가 적용 가능하다.

베타 함수의 의의

베타 함수에 의해, 유한 열의 부호화가 세 개의 자연수 (c, d, n)으로 표현된다. \beta 함수 자체가 원시 재귀적이므로, 이 부호화와 복호화는 PA 내에서 표현 가능하다.

소수 거듭제곱 기법에서는 소수의 존재와 분포에 관한 산술적 사실이 필요하지만, 베타 함수 기법에서는 나머지 연산만으로 충분하므로, PA의 공리로부터 부호화의 성질을 직접 증명할 수 있다.

부호화의 핵심 성질 요약

괴델 번호 매김이 만족해야 하는 핵심 성질:

1. 단사성(Injectivity): 서로 다른 구문론적 대상은 서로 다른 괴델 수에 대응한다.
2. 효과적 부호화(Effective Encoding): 구문론적 대상으로부터 괴델 수를 계산하는 알고리즘이 존재한다.
3. 효과적 복호화(Effective Decoding): 괴델 수로부터 원래의 구문론적 대상을 복원하는 알고리즘이 존재한다.
4. 원시 재귀적 관계: 구문론적 관계들(항인지, 공식인지, 증명인지 등)이 괴델 수 위의 원시 재귀적 관계로 변환된다.

성질 4가 괴델 증명에서 가장 본질적이다. 원시 재귀적 관계가 PA 내에서 표현 가능하므로, 형식 체계가 자기 자신의 구문론적 성질에 관한 산술적 문장을 형식적으로 표현할 수 있게 된다.