recursion theorem

recursion theorem은 몰라도 되는 부분입니다. 주어진 operations들에 대해서 닫혀있는 함수를 단일하게 생성할 수 있다는 것이 요지이지만(즉, PL에 대한 모든 formula들은 unique하게 구성됨), 다른 것들을 이해하는데는 크게 연관이 없습니다. recursion은 가급적이면 생략하시는 게 (정신건강에) 좋습니다.

 

Recursion Theorem : Assume that the subset of $C$ of $U$ is freely generated from $B$ by $f$ and $g$, where

$f: U \times U \rightarrow U$ and $g: U \rightarrow U$. Let $V$ be a set and $F$, $G$, and $h$ be any functions such that $h : B \rightarrow V$, $F :V \times V \rightarrow V$, and $G : V \rightarrow V$. Then there is unique function $\bar{h} : C \rightarrow V$ such that

(i) For $x$ in $B$, $\bar{h}(x)=h(x)$ and

(ii) For $x$, $y$ in $C$, $\bar{h}(f(x,y))=F(\bar{h}(x), \bar{h}(y))$ and $\bar{h}(g(x))=G(\bar{h}(x))$.

 

before proving this, define some ideas.

 

1. a set $C$ is closed under $f$ and $g$ iff $x,y \in C \rightarrow f(x,y) \in C \wedge g(x) \in C$

2. a set $C$ inductive iff for a given set $B \subseteq U$, $B \subseteq C$ and $C$ is closed under $f$ and $g$. 

3. if $C=\cap S$ where $S \subseteq U$ is any inductive set, then we'll call $C$ is generated from $B$ by $f$ and $g$.

4. $C$ is freely generated from $B$ by $f$ and $g$ iff $C$ is generated from $B$ by $f$ and $g$, and satisfies (a), (b).

(a) $B$, $ran f_C$ and $ran g_C$(restriction domain to the $C$) are pairwise disjoint;

(b) $f_C$, $g_C$ are one-to-one.

 

 

Proof of the theorem

 

define $v_i: A_i(\subseteq C) \rightarrow D_i(\subseteq V)$ is acceptable if it meets (i') and (ii').

 

for $x,y \in C$

(i') For $x$ in $B \cap domv$, $v(x)=h(x)$ and

(ii') if $f(x,y) \in domv$, then $x,y$ does and $v(f(x,y))=F(v(x), v(y))$. if $g(x) \in domv$, then so does $x$ and $v(g(x))=G(v(x))$.

 

Let $K$ be the collection of all acceptable functions and $\bar{h}=\cup K$.

 

then $<x,z>\in \bar{h}$ iff $<x,z>\in v_i$ for some $i$ iff $v_i(x)=z$ for some $i$.

 

we'll show that (1) $\bar{h}$ is a function, (2) $\bar{h}$ is acceptable, (3) $\bar{h}$ is defined throughout $C$, and (4) $\bar{h}$ is unique.

 

(1) Let $S=\{ x \in C | \text{for at most one z}, <x,z> \in \bar{h} \} = \{x \in C | \text{all acceptable functions defined at x agree there} \}$

 

we'll show that $S=C$ by proving $S$ is inductive. if then, since $dom\bar{h} \subseteq C$ and $C=S$, all elemetns in $dom\bar{h}$ should be single-valued. thus $\bar{h}$ is a singled-valued function.

 

Consider $x \in B$. suppose $v_i(x)$ and $v_j(x)$ is defined at x. since $v_i$ and $v_j$ are acceptable, they must meet (i'). thus $v_i(x)=v_j(x)$. thus $B \subseteq S$.

 

now we've to show that $S$ is closed under f and g. Let $x,y \in S$. suppose $f(x,y)$ is defined at $v_i$ and $v_j$. by (ii'), $v_i(f(x,y))=F(v_i(x),v_j(y))$ and $v_j(f(x,y))=F(v_j(x),v_j(y))$. and since $x,y \in S$, $v_i(x)=v_j(x)$ and $v_i(y)=v_j(y)$. thus $v_i(f(x,y))=v_j(f(x,y))$. and you can check similarly $S$ is closed under g. now we showed $S$ is inductive. since $S \subseteq C$ and $C \subseteq S$, $S=C$. thus $\bar{h}$ is a single-valued function.

 

(2) $\bar{h}$ is acceptable.

 

 since $\bar{h}= \cup K$ is a function and every x-coordinate of $\cup K$ belongs to $C$ and every y-coordinate of $\cup K$ belongs to $V$, $dom \bar{h} \subseteq C$ and $ran \bar{h} \subseteq V$(think about union of acceptable functions).

 

about (i'), let $x \in B$. then $x \in S$. thus $<x,z> \in \bar{h}$ iff $<x,z>\in v_i$. thus $v_i(x)=\bar{h}(x)$. and since $v_i$ is acceptable, $v_i(x)=h(x)$. thus $\bar{h}(x)=h(x)$

 

about (ii'), think about $\bar{h}(f(x,y))=F(\bar{h}(x), \bar{h}(y))$. let $f(x,y)\in dom\bar{h}$. then $\bar{h}(f(x,y))=v(f(x,y))$ for some acceptable $v$. since $v$ meets (ii'), $v(f(x,y))=F(v(x),v(y))$. $F(v(x),v(y))$ means $x$ and $y$ is defined $v$. thus by definition of acceptable function, $v(x)=\bar{h}(x)$ and $v(y)=\bar{h}(y)$. thus $\bar{h}(f(x,y))=F(\bar{h}(x), \bar{h}(y))$. we can check about $g$ simiarly. now we proved $\bar{h}$ is acceptable.

 

(3) $\bar{h}$ is defined throughout $C$.

 

 for this, we've to show that $dom\bar{h}=C$. since $dom\bar{h} \subseteq C$, it sufficies to show that $dom\bar{h}$ is inductive.

 

Let $x \in B$. then $<x,h(x)>\in h$. we'll show that $\{<x,h(x)>\}$ is acceptable thus $domh \subseteq dom\bar{h}$. (i') is clear. and since C is freely generated by $f$ and $g$,  the range of $f_C$, $g_C$, and $B$ is pairwise disjoint. thus $f(x,y)$ and $g(x)$ cannot belong to $domh=B$. thus vacuously (ii') is satisfied.

 

now let $x,y \in dom\bar{h}$. we'll check whether $f(x,y) \in dom \bar{h}$. suppose not. define $v=\bar{h} \cup\{<f(x,y), F(\bar{h}(x),\bar{h}(y))>\}$. we'll show $v$ is acceptable, so $f(x,y) \in domv \subseteq dom\bar{h}$.

 

trivially $v$ is a function.

Consider $x \in B \cap domv$. since $C$ is freely generated, $x \neq f(x,y) \in dom\bar{h} \subseteq C$. thus $x \in dom\bar{h}$. rest of this is trivial.

 

Consider (ii'). assume $f(\bar{x},\bar{y}) \in domv$. the case that $f(\bar{x},\bar{y}) \in dom\bar{h}$ is trivial. so let $f(\bar{x},\bar{y}) = f(x,y)$. $x,y \in C$ trivially. by freeness, $f_C$ is one-to-one. thus $\bar{x}=x$ and $\bar{y}=y$. then $v(f(\bar{x},\bar{y}))=v(f(x,y))=F(\bar{h}(x),\bar{h}(y))=F(v(x),v(y))=F(v(\bar{x}),v(\bar{y}))$. the case of $g$ is easy.

 

 now we proved $v$ is acceptable function. then since $v$ is acceptable, $domv \subseteq dom\bar{h}$. thus $f(x,y) \in dom\bar{h}$ which is contraction to our supposition. thus $f(x,y) \in dom \bar{h}$.

 

about $g$, you can check same as $f$.

 

consequently, since $dom\bar{h}$ is inductive, and $dom\bar{h} \subseteq C$, $dom\bar{h}=C$.

 

(4) $\bar{h}$ is unique.

 

assume that $\bar{h_1}$ and $\bar{h_2}$ satisfy the recursion theorem.

 

define $S=\{x\in C | \bar{h_1}(x)=\bar{h_2}(x)\}$. by showing $S$ is inductive(that is, $S=C$), we know that $\bar{h_1}(x)=\bar{h_2}(x)$ for all $x \in C=dom\bar{h}$. thus $\bar{h}$ is unique.

 

 

Let $x \in B$. domains of $\bar{h_1}$ and $\bar{h_2}$ are $C \supseteq B$. since $\bar{h_1}$ and $\bar{h_2}$ is acceptable, $\bar{h_1}(x)=h(x)=\bar{h_2}(x)$. thus $x\in S$.

 

second condition. let $x,y \in S$. we've to prove $f(x,y) \in S$; $\bar{h_1}(f(x,y))=\bar{h_2}(f(x,y))$ and $g(x) \in S$;$\bar{h_1}(g(x))=\bar{h_2}(g(x))$.

 

since $x,y\in S \subseteq C$, $f(x,y), g(x) \in C=dom\bar{h_1}=dom\bar{h_2}$ by generating property. then $\bar{h_1}(f(x,y))=F(\bar{h_1}(x),\bar{h_2}(y))=F(\bar{h_2}(x),\bar{h_2}(y))=\bar{h_2}(f(x,y))$ since $x,y\in S \leftrightarrow \bar{h_1}(x)=\bar{h_2}(x) \wedge \bar{h_1}(y)=\bar{h_2}(y)$.

 

now consider $g(x) \in S$. $\bar{h_1}(g(x))=G(\bar{h_1}(x))=G(\bar{h_2}(x))=\bar{h_2}(g(x))$ since $x \in S \leftrightarrow \bar{h_1}(x)=\bar{h_2}(x)$.

 

consequently, $S$ is inductive. thus $\bar{h_1}=\bar{h_2}=\bar{h}$. hence, uniqueness is proved.

 

 

now recursion theorem is fully proved.