정수론, 그 두 번째 이야기 | Recursion Theorem

Recursion Theorem 은 차후 어떤 함수의 존재성과 유일성을 보이는데 유용하게 사용되는 정리이다.

그렇기에 따로 포스팅하고자 한다.

 

Recursion Theorem 은 아래와 같은 정리이다.

어떤 집합 $X$와 그의 원소 $a \in X$, 그리고 함수 $f : X \rightarrow X$ 가 주어질 때,      다음 두 조건을 만족하는 함수 $F : \mathbb{N} \rightarrow X$ 는 유일하게 존재한다.      $1.\; F(1) = a$      $2.\;F(S(n)) = f(F(n))$

 

위 정리를 증명하자.

 

Part 1. 유일성

위의 두 조건을 만족하는 서로 다른 함수 $F : \mathbb{N} \rightarrow X$와 $G : \mathbb{N} \rightarrow X$ 가 존재한다고 가정하자.

이 때, $F(1) = G(1) = a$ 임은 조건에 의해 자명하다. 

 

만약 어떤 정수 $k$ 에 대해 $F(k) = G(k)$ 가 성립한다면,

$F(k + 1) = f(F(k)) = f(G(k)) = G(k + 1)$ 이므로

 

수학적 귀납법에 의해, $\forall x \in \mathbb{N},\;F(x) = G(x) $ 이고, 이는 $F$와 $G$가 같은 함수임을 의미한다.

따라서 주어진 조건을 만족하는 함수는 유일하다.

 

Part 2. 존재성

$\mathrm{dom}f \subseteq \mathbb{N}$ 이고 $\mathrm{ran}f \subseteq X$ 인 함수들의 집합을 $\mathbb{A}$ 라고 하자.

 

우리는 다음과 같은 함수 $F$를 선택할 것이다.

$$F = \left \{ \left ( n \mapsto \omega \right ) : \exists p \in A \;s.t.\; \left ( n \in \mathrm{dom}p \wedge p(n) = \omega \right ) \right \}$$

$F \in \mathbb{A}$ 임은 정의에 의해 자명하고, 만약 존재한다면 유일함 또한 증명하였으므로,  $\mathrm{dom} F = \mathbb{N}$ 임을 보이자

 

정의에 의해, $1 \in \mathrm{dom} F$ 가 성립하고, $n \in \mathrm{dom} F$ 라고 가정하자.

이 때, 정의에 의해 $\exists p \in \mathbb{A} \; s.t. \; n \in \mathrm{dom} p$ 이고, 함수 $q$를 다음처럼 정의하자

$$q = p \cup \left \{ S(n) \mapsto f(p(n)) \right \}$$

이때 $q \in \mathbb{A}$ 이므로, $S(n) \in \mathrm{dom} q \subseteq \mathrm{dom} F$

따라서, 수학적 귀납법에 의해 $\mathrm{dom} F = \mathbb{N}$ 이고, 조건을 만족하는 함수는 존재한다.