논리학, 그 열두 번째 이야기 | Recursion Theorem

이번 글에서는 저번 글에서 언급한 Recursion Theorem에 대해 이야기해보려 한다. 여기서 말하는 recursion theorem은 정수론에서 말하는 Recursion Theorem을 더 확장한 것으로, 어떤 시작점들에서의 함숫값이 정해져 있고, 다른 함숫값을 결정하는 재귀적인 규칙들이 있다면, 해당 조건들을 만족시키는 함수가 언제나 유일하게 존재한다는 정리이다. 이렇게 말로만 설명하면 뭔가 헷갈리고 어려울 수 있으니 보다 수학적인 용어를 사용하여 명확하게 설명하도록 하겠다. 다음 정리를 보자.

 

Theorem 1. Recursion Theorem

$C$가 $U$의 부분집합 $B$로부터 두 함수 $f:U\times U\to U$와 $g:U\to U$에 의해 freely generated되었다고 하자. 추가로 집합 $V$와 함수 $h:B\to V$, $F:V\times V\to V$, $G:V\to V$가 주어졌다고 하자. 그러면 다음 조건을 만족하는 함수 $\overline{h}:C\to V$가 유일하게 존재한다. 1) 임의의 $x\in B$에 대하여 $\overline{h}(x)=h(x)$ 2) 임의의 $x,y\in C$에 대하여 $\overline{h}(f(x,y))=F(\overline{h}(x),\overline{h}(y))$ 3) 임의의 $x\in C$에 대하여 $\overline{h}(g(x))=G(\overline{h}(x))$

 

Proof.

증명을 하기에 앞서, 한 가지 개념을 먼저 정의하고 시작하자.

만약 어떤 함수 $v:A\to D$가 아래의 세 가지 조건 1'), 2'), 3')을 모두 만족할 때 이를 acceptable하다고 부르기로 하자. 물론, 이때 $A$는 $C$의 부분집합이며 $D$는 $V$의 부분집합이 될 것이다.

1') 임의의 $x\in B\cap A$에 대하여 $v(x)=h(x)$
2') 임의의 $x,y\in A$에 대하여 $v(f(x,y))=F(v(x),v(y))$
3') 임의의 $x\in A$에 대하여 $v(g(x))=G(v(x))$

 

이제 acceptable한 모든 함수의 집합을 $S$라고 하고, $\overline{h}=\bigcup S$를 정의하자.

만약 $\overline{h}$가 함수이고 $\overline{h}$가 acceptable하며 $\overline{h}$의 정의역이 $C$라면 우리는 정리에서 요구하는 조건을 모두 만족하는 함수의 존재성을 보이게 된다. 거기에 추가로 이러한 함수가 유일함을 보인다면 우리는 정리를 증명하게 될 것이다.

 

그러니 먼저 $\overline{h}$가 함수임을 보이도록 하자. 먼저, 집합 $T$를 $(x,z)\in \overline{h}$인 $z$가 최대 한 개 존재하도록 하는 모든 $x\in C$의 집합이라고 정의하자. 만약 $T$가 귀납적이라면 이 글의 Theorem 2에 의해 $T=C$임이 보장되며, 이는 곧 $\overline{h}$가 함수임을 의미한다. 따라서 우리는 $T$가 귀납적이라는 것을 보일 것이다.

일단 $x\in B$에 대해 생각하자. 만약 어떤 두 개의 acceptable한 함수 $v$와 $u$가 $x$를 원소로 하는 정의역을 가진다고 하자. 그러면 $v$와 $u$ 모두 조건 1')을 만족하므로 $v(x)=u(x)=h(x)$이다. 따라서 $\overline{h}$의 정의에 의해 $(x,z)\in \overline{h}$인 $z$가 아무리 많아봐야 한 개임을 알 수 있으며, 이로 인해 $B\subseteq T$임을 알 수 있다. 즉, $\overline{h}$는 함수이다.

 

이제 $\overline{h}$가 acceptable하다는 것을 보이자. $\overline{h}=\bigcup S$이므로 $S$의 정의에 의해 $\overline{h}$의 정의역은 $C$의 부분집합이며, $\overline{h}$의 치역 역시 $V$의 부분집합이다. 이 사실을 기억해두자.

먼저, $\overline{h}$가 조건 1')을 만족한다는 것은 위의 논의로부터 자명하다.

이제 조건 2')에 대해 생각해보자. 어떤 $x,y\in C$에 대해 $f(x,y)$가 $\overline{h}$의 정의역의 원소라고 가정하자. 그러면 $\overline{h}$의 정의에 의해 어떤 acceptable한 함수 $v$에 대해 $f(x,y)$가 $v$의 정의역의 원소라는 사실을 알 수 있으며, $v$가 acceptable하므로 조건 2')에 의해 $v(f(x,y))=F(v(x),v(y))$이다. 이때, $\overline{h}$의 정의에 의해 $v(f(x,y))=\overline{h}(f(x,y))$이고, $v(x)=\overline{h}(x)$, $v(y)=\overline{h}(y)$이므로 $\overline{h}(f(x,y))=F(\overline{h}(x),\overline{h}(y))$임을 알 수 있다. 따라서 $\overline{h}$는 조건 2')을 만족하며, 비슷한 방법을 통해 $\overline{h}$가 조건 3')을 만족하는 것을 보일 수 있다.

따라서 $\overline{h}$는 조건 1'), 2'), 3')을 모두 만족하며, 이로부터 $\overline{h}$는 acceptable한 함수임을 알 수 있다.

 

이제 $\overline{h}$의 정의역이 $C$라는 것을 보이자. 만약 $\overline{h}$의 정의역이 귀납적이라면, 이 글의 Theorem 2에 의해 $\overline{h}$의 정의역이 $C$임이 보장되므로 $\overline{h}$의 정의역이 귀납적이라는 것을 보이자.

먼저 $x\in B$인 경우에 대해 생각해보자. 그러면 $h$의 정의역이 $B$이므로 함수 $v:\{x\}\to \{h(x)\}$를 생각할 수 있다. 만약 이렇게 정의된 함수 $v$가 acceptable하다면 $B$가 $\overline{h}$의 정의역의 부분집합이 됨은 자명하다. 먼저 조건 1')을 살펴보자. 함수 $v$의 정의에 의해 $v(x)=h(x)$이고, $v$의 정의역과 $B$의 교집합은 $\{x\}$이므로 함수 $v$는 조건 1')을 만족한다. 정리의 조건에서 $C$가 $B$로부터 두 함수 $f,g$에 의해 freely generated되었다고 하였으므로 그 어떤 $x,y\in C$에 대해서도 $f(x,y)$와 $g(x)$는 $B$의 원소가 될 수 없으며, 따라서 조건 2')와 조건 3')은 공허하게 참이다. 따라서 함수 $v$는 acceptable하며, 이로 인해 $B$는 $\overline{h}$의 정의역의 부분집합이 된다.

이제 $x$와 $y$가 모두 $\overline{h}$의 정의역의 원소라고 하자. 이제 귀류법을 사용하여 $f(x,y)$ 역시 $\overline{h}$의 정의역의 원소가 됨을 보일 것이다. $f(x,y)$가 $\overline{h}$의 정의역의 원소가 아니라고 가정하면, $\overline{h}$의 정의역에 $f(x,y)$를 추가한 집합을 정의역으로 가지는 함수 $v$를 다음과 같이 정의할 수 있다.

$$v(c)=\{\begin{array}{ll}\overline{h}(c)& \text{ if }c\in \text{dom}\overline{h}\\ F(\overline{h}(x),\overline{h}(y))& \text{ if }c=f(x,y)\end{array}$$

여기서 $\text{dom}\overline{h}$는 $\overline{h}$의 정의역을 의미한다. 만약 함수 $v$가 acceptable하다면 $\overline{h}$의 정의에 의해 $f(x,y)$가 $\overline{h}$의 정의역의 원소가 아니라는 가정에 모순이 발생한다. 따라서 우리는 함수 $v$가 acceptable함을 보이면 충분하다.

함수 $v$가 조건 1')을 만족함을 보이기 위해 $v$의 정의역과 $B$의 교집합의 원소 $c$를 생각하자. 정리의 조건에서 $C$가 $B$로부터 두 함수 $f,g$에 의해 freely generated되었다고 하였으므로 $f(x,y)$는 $B$의 원소가 될 수 없다. 따라서 $c\in \text{dom}\overline{h}$이며, 이로 인해 $v$가 조건 1')을 만족함은 자명하다.

이제 $v$가 조건 2')을 만족한다는 것을 보이자. $f(\overline{x},\overline{y})$가 $v$의 정의역의 원소임을 가정하자. 만약 $f(\overline{x},\overline{y})\in \text{dom}\overline{h}$라면, $\overline{h}$가 acceptable하다는 사실로부터 $v(f(\overline{x},\overline{y}))=F(v(\overline{x}),v(\overline{y}))$임은 자명하다. 이제 $f(\overline{x},\overline{y})=f(x,y)$인 경우를 생각하자. 이때, 정리의 조건에서 $C$가 $B$로부터 두 함수 $f,g$에 의해 freely generated되었다고 하였으므로 $f_C$는 단사함수이며, 이로부터 $x=\overline{x}$, $y=\overline{y}$임을 알 수 있다. 따라서 다음이 성립한다.

$$v(f(\overline{x},\overline{y}))=v(f(x,y))=F(\overline{h}(x),\overline{h}(y))=F(v(x),v(y))=F(v(\overline{x}),v(\overline{y}))$$

즉, 함수 $v$가 조건 2')을 만족한다. 같은 방법으로 함수 $v$가 조건 3')을 만족한다는 것을 보일 수 있다.

함수 $v$가 조건 1'), 2'), 3')을 모두 만족하므로 함수 $v$는 acceptable하며, 따라서 $f(x,y)$는 $\overline{h}$의 정의역의 원소임을 알 수 있다.

위와 같은 방법을 통해 $x$가 $\overline{h}$의 정의역의 원소라면, $g(x)$ 역시 $\overline{h}$의 정의역의 원소가 됨을 쉽게 보일 수 있다. 따라서 $\overline{h}$의 정의역은 귀납적이며, 이로부터 $\overline{h}$의 정의역이 $C$임을 알 수 있다.

 

이제 이러한 $\overline{h}$가 유일함을 보이자. 이를 위해 조건 1), 2), 3)을 모두 만족하는 두 함수 ${\overline{h}}_1$, ${\overline{h}}_2$가 존재한다고 가정하자.

집합 $K$를 $K=\{x\in C|{\overline{h}}_1(x)={\overline{h}}_2(x)\}$로 정의하자. 만약 $K=C$라면, ${\overline{h}}_1={\overline{h}}_2$이며, $K$가 귀납적이라면 이 글의 Theorem 2에 의해 $K=C$가 된다. 따라서 $K$가 귀납적이라는 것을 보이면 조건 1), 2), 3)을 만족하는 $\overline{h}$가 유일함이 증명된다.

먼저, $B\subseteq K$임을 보이기 위해 $x\in B$를 생각하자. $\overline{h_1}$과 $\overline{h_2}$가 acceptable하고 이 둘의 정의역이 $C$라는 사실로부터 ${\overline{h}}_1(x)=h(x)={\overline{h}}_2(x)$임을 알 수 있다. 따라서 $x\in K$임을 알 수 있으며, $x\in B$의 선택이 임의적이었으므로 $B\subseteq K$임은 자명하다.

이제 임의의 $x,y\in K$에 대하여 $f(x,y)\in K$임을 보이자. ${\overline{h}}_1$과 ${\overline{h}}_2$가 acceptable하고 이 둘의 정의역이 $C$라는 사실로부터 다음이 성립한다는 사실을 알 수 있다.

$${\overline{h}}_1(f(x,y))=F({\overline{h}}_1(x),{\overline{h}}_2(x))=F({\overline{h}}_2(x),{\overline{h}}_2(y))={\overline{h}}_2(f(x,y))$$

따라서 $x,y\in K$가 $f(x,y)\in K$를 함의한다는 사실이 증명되었다. $x\in K$가 $g(x)\in K$를 함의한다는 사실 역시 위와 비슷한 방법을 통해 증명할 수 있으며, 이로부터 $K$가 귀납적이라는 사실을 알 수 있다.

따라서 $h$의 유일성이 증명되었으며, 결과적으로 정리가 증명되었다.

$◼$

 

사실, 위 정리를 이해하는 데에는 생각보다 긴 시간이 필요할 것이다. 큰 맥락 안에서는 정수론에서 말하는 Recursion Theorem과 본질적으로 같지만 그보다 훨씬 추상화된 모습을 하고 있기 때문이다. 지금 이 글을 쓰고 있는 나도 위 정리를 처음 봤을 때엔 이게 무슨 소리인가 싶었으니 지금 당장 위 정리를 이해하지 못했어도 크게 상심하지는 말자. 다만, 위 정리가 대략적으로 어떤 것을 의미하는지는 꼭 이해하고 넘어가자. 위 정리가 논리학에서 상당히 중요한 정리 중 하나인 Unique Readability Theorem과 비슷한 맥락의 이야기를 하고 있기 때문이다. 또한, 위 정리에서는 $\mathcal{F}=\{f,g\}$인 경우에 대해 다뤘는데, 사실 $\mathcal{F}$가 유한집합일 필요는 없으며, $\mathcal{F}$의 원소가 꼭 단항 연산, 이항 연산일 필요는 없다. 보다 일반화된 형태에 대해서는 일차논리에 대해 설명한 후에 다룰 것이다.