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

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

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

 

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

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

 

위 정리를 증명하자.

 

Part 1. 유일성

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

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

 

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

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

 

수학적 귀납법에 의해, $\mathrm{\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=\{(n\mapsto \omega ):\mathrm{\exists }p\in As.t.(n\in \mathrm{dom}p\wedge p(n)=\omega )\}$$

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

 

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

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

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

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

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