논리학, 그 열두 번째 이야기 | 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$가 주어졌다고 하자. 그러면 다음 조건을 만족하는 함수 $\bar{h} : C \to V$가 유일하게 존재한다. 1) 임의의 $x \in B$에 대하여 $\bar{h}(x) = h(x)$ 2) 임의의 $x, y \in C$에 대하여 $\bar{h}\left( f(x,y) \right) = F \left( \bar{h}(x), \bar{h}(y) \right)$ 3) 임의의 $x \in C$에 대하여 $\bar{h}\left( g(x) \right) = G \left( \bar{h}(x) \right)$

 

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 \left( f(x,y) \right) = F \left( v(x), v(y) \right)$
3') 임의의 $x \in A$에 대하여 $v \left( g(x) \right) = G \left( v(x) \right)$

 

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

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

 

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

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

 

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

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

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

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

 

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

먼저 $x \in B$인 경우에 대해 생각해보자. 그러면 $h$의 정의역이 $B$이므로 함수 $v : \{ x \} \to \{ h(x) \}$를 생각할 수 있다. 만약 이렇게 정의된 함수 $v$가 acceptable하다면 $B$가 $\bar{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$는 $\bar{h}$의 정의역의 부분집합이 된다.

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

$$ v(c) = \begin{cases} \bar{h}(c) &\mbox{ if } c \in \text{dom}\bar{h} \\ F\left(\bar{h}(x),\bar{h}(y)\right) &\mbox{ if } c = f(x,y) \end{cases} $$

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

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

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

$$ v \left( f(\bar{x},\bar{y}) \right) = v \left( f(x,y) \right) = F \left( \bar{h}(x), \bar{h}(y) \right) = F \left( v(x), v(y) \right) = F \left( v(\bar{x}), v(\bar{y}) \right)$$

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

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

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

 

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

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

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

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

$$ \bar{h}_1 \left( f(x,y) \right) = F \left( \bar{h}_1(x), \bar{h}_2(x) \right) = F \left( \bar{h}_2(x), \bar{h}_2(y) \right) = \bar{h}_2 \left( f(x,y) \right) $$

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

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

$\blacksquare$

 

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