디멘의 블로그 이데아를 여행하는 히치하이커

베타 함수를 통한 페아노 산술에서의 괴델 수 정의

25 Jan 2025
수학
논리학

요약. 1차 페아노 산술은 술어에 대한 양화를 허용하지 않기 때문에 덧셈과 곱셈 공리를 별도로 요구한다. 그러나 지수나 계승 등의 추가적인 연산은 — 튜플을 페아노 산술에서 정의할 수 있는 한 — 별도의 공리 없이 정의 가능하다. 그리고 튜플은 베타 암호화를 통해 페아노 산술에서 정의 가능하기 때문에, 페아노 산술은 지수, 계승, 소인수분해, 나아가 괴델 수까지 형식화할 수 있다.

1. 서론

정의. 페아노 산술(Peano arithmetics, PA)은 $(0, S, +, \cdot)$를 부호수(signature)로 가지는 이론으로, 공리는 다음과 같다.

  1. $\forall x : S(x) \neq 0$
  2. $\forall x, y : S(x) = S(y) \rightarrow x = y$
  3. $\forall x : x + 0 = x$
  4. $\forall x, y : x + S(y) = S(x + y)$
  5. $\forall x, y : x \cdot 0 = 0$
  6. $\forall x, y : x \cdot S(y) = (x \cdot y) + x$

추가로 다음의 귀납 공리꼴(axiom schema)을 가진다. 임의의 1차 논리식 $\phi(x)$에 대해,

 7. $\big[ \phi(0) \land \forall x \; [ \phi(x) \rightarrow \phi(S(x)) ] \big] \rightarrow \forall x \;\phi(x)$

추가적으로 편의를 위해 $<, -, \bmod$를 다음과 같이 정의한다.

\[\begin{aligned} &x < y : &&\exists z \neq 0\; [x + z = y]\\ &x - y = z : &&x = y + z \\ &x \bmod y = z: && (z < y) \land \exists q \;[ qy + z = x ] \end{aligned}\]

역사적으로 데데킨트가 처음 제시한 페아노 산술은 2차 논리 이론이었기 때문에 귀납 공리꼴 대신 귀납 공리가 있었다. 또한 3번부터 7번 공리가 없었다.

정의. 2차 논리 페아노 산술은 $(0, S)$를 부호수(signature)로 가지는 이론으로, 공리는 다음과 같다.

  1. $\forall x : S(x) \neq 0$
  2. $\forall x, y : S(x) = S(y) \rightarrow x = y$
  3. $\forall \phi \bigg[ \big[ \phi(0) \land \forall x \; [ \phi(x) \rightarrow \phi(S(x)) ] \big] \rightarrow \forall x \;\phi(x)\bigg]$

나머지 공리가 불필요한 이유는, 2차 논리는 술어에 대한 양화를 허용하기 때문에 2차 논리식만으로 덧셈과 곱셈을 정의할 수 있기 때문이다. 예를 들어 $w = u + v$는 다음 논리식과 동치이다.

\[\forall \phi \bigg[ \forall x, y, z \big[ \phi(x, 0, x) \land (\phi(x, S(y), z) \rightarrow \phi(x, y, S(z)) \big] \rightarrow \phi(u, v, w) \bigg]\]

그러나 2차 논리는 수많은 수학적 · 철학적 허점을 가지는 것으로 드러났기 때문에 서두에서 소개한 1차 논리 페아노 산술이 표준으로 선택되었다. 이 선택의 함의는 첫째로 귀납 공리가 귀납 공리꼴이 된다는 것이고, 둘째는 덧셈과 곱셈을 별도의 공리를 통해 정의해야 한다는 것이다.

그런데 이런 의문이 남는다. 덧셈과 곱셈 말고 다른 연산은 따로 정의할 필요가 없는 것일까? 예를 들어 지수, 소인수분해, 계승과 같은 연산은 별도의 공리 없이 정의 가능할까? 나아가, 임의의 논리식을 자연수에 대응시키는 괴델 수 기법은 페아노 산술만으로 정의 가능할까?

2. 튜플

이 의문에 답하는 혜안은, 튜플을 페아노 산술에서 정의할 수 있다면 기타 수많은 연산이 정의 가능해진다는 사실이다. 여기서 튜플이란 $(1, 4, 2)$와 같은 유한한 자연수의 나열을 말한다.

일례로 다음과 같은 술어와 함수들이 정의되어 있다고 가정하자.

  • $\mathrm{Tup}(\tau):$ $\tau$가 튜플이다.
  • $\mathrm{At}(\tau, i):$ $\tau$가 튜플일 때, $\tau$의 $i$번째 자연수를 반환한다.
  • $\mathrm{Len}(\tau):$ $\tau$의 길이를 반환한다.

편의를 위해 $\mathrm{At}(\tau, i)$를 $\tau[i]$로 쓰도록 하자. 예를 들어 $\tau = (1, 4, 2)$라면 다음이 성립한다. (인덱스는 0부터 시작하는 것으로 생각한다)

\[\mathrm{Tup}(\tau) \; \land \; \mathrm{Len}(\tau) = 3 \;\land\; \tau[1] = 4\]

튜플을 사용하면 다음과 같이 $z = x^y$를 정의할 수 있다.

\[\forall \tau \bigg[ \big[ \mathrm{Tup}(\tau)\; \land \; \tau[0] = 1 \;\land \forall i < y (\tau[i + 1] = \tau[i] \cdot x) \big] \rightarrow \tau[y] = z \bigg]\]

3. 베타 암호화

그렇다면 튜플을 덧셈과 곱셈, 그리고 1차 논리식만으로 정의할 수 있을까? 이에 대한 답은 “가능하다”이다. 아니나다를까역시나적시나 이 결과를 처음 증명한 사람은 괴델이다. 먼저 다음의 정리를 상기하자.

중국인의 나머지 정리. $(n_1, \dots, n_k)$가 켤레서로소(pairwise coprime)라고 하자. $0 \leq r_i < n_i$인 임의의 $(r_1, \dots, r_k)$에 대해 다음을 만족하는 수 $x$가 언제나 존재한다.

\[x \bmod n_i = r_i\]

괴델의 아이디어는 중국인의 나머지 정리에서 $x$에 해당하는 수를 튜플 $(r_1, \dots, r_k)$의 코드로 생각하는 것이다. 그런데 여기에는 문제가 있다. $x$로부터 $(r_1, \dots, r_k)$를 복호화하기 위해서는 $(n_1, \dots, n_k)$가 주어져야 하는데, 이는 또다시 튜플을 요구하기 때문이다.

이 문제를 해결하기 위해 괴델은 다음의 보조정리를 꺼내든다.

보조정리. $n!+ 1, 2n! + 1, \dots, n \cdot n! + 1$은 켤레서로소이다.

증명. $1 \leq a < b \leq n$에 대해 $u = an! + 1, v = bn! + 1$이라고 하자. 유클리드 호제법에 의해,

\[\mathrm{gcd}(u, v) = \mathrm{gcd}(u, v - u) = \mathrm{gcd}(an! + 1, (b - a)n!)\]

이다. $(b - a)n!$의 모든 약수의 집합은 $\lbrace 1, 2, \dots, n\rbrace $이다. 그런데 이중 어느 원소도 $an! + 1$의 약수가 아니므로 $\mathrm{gcd}(an! + 1, (b - a)n!) = \mathrm{gcd}(u, v) = 1$이다. □

이제 우리는 튜플을 순서쌍으로서 정의할 수 있다.

정의. 튜플 $(r_1, \dots, r_k)$를 다음과 같이 순서쌍 $\langle a, b \rangle$로 표현한다.

  • $b = n! \quad \text{where} \quad n = \max(r_1, \dots, r_k, k)$
  • $a \bmod (kb + 1) = r_k$

단, $a$는 2번 조건을 만족하는 자연수 중 가장 작은 자연수로 선택한다.

한편 튜플은 칸토어 대응을 통해 자연수로 표현이 가능하다.

정의.

\[\langle a, b \rangle = \frac{(a + b)(a + b + 1)}{2} + b\]

이로써 우리는 튜플 $\tau$를 자연수 $n$으로 암호화(coding)할 수 있다. 그리고 역으로 $n$이 주어지면 덧셈, 곱셈, 그리고 나머지 연산만을 사용하여 $\tau$를 복호화해낼 수 있다. 그리고 나머지 연산은 덧셈, 곱셈, 그리고 1차 논리로부터 쉽게 정의가 가능하므로, 목표가 달성되었다.

역사적으로 괴델이 증명한 정리는 다음과 같다.

$\beta$-함수 보조정리. 임의의 자연수열 $(n_1, \dots, n_k)$에 대해, 어떤 자연수 $a, b$가 존재하여 $1 \leq i \leq k$에 대해 $\beta(a, b, i) = n_i$이다. 여기서 $\beta$는 다음과 같이 정의된 함수이다.

\[\beta(x, y, i) = x \bmod (iy + 1)\]

이런 이유로 지금까지의 과정을 베타 암호화(Beta coding)라고 부른다. 괴델은 베타 암호화를 이용하여 지수 연산과 소인수분해를 PA에서 성공적으로 정의했으며, 이로부터 괴델 수와 비롯된 여러 술어를 PA에서 형식화할 수 있었다. 제목에서 드러나다시피 원래 이 글의 목표는 이 과정을 모두 개괄하는 것이었으나 때늦게 찾아온 필자의 귀찮음 이슈와, 글을 여기까지 읽은 독자라면 이후 내용은 어렵지 않게 유추 가능하리라는 생각으로 이만 줄인다.