- Nechť $A \subseteq \mathbb{N}$ je nekonečná rek. mn. $\implies \exists TVF f : \mathbb{N} \rightarrow \mathbb{N}$ takové, že $A = range(f) a $f$ je rostoucí.
- $B = {f(i) | i \in k} \subseteq A$
- $B$ je r.e., protože je oborem hodnot fce počítané
- $B \subseteq \mathbb{N}, f : \mathbb{N} ^ k \rightarrow \mathbb{N}$ $f^{-1}$
- strana 5:
-
- $\chi_{f^{-1}(B)}(x_1,…,x_k) = \begin{cases} 1 & f(x_1,…,x_k) \in B \ 0 & jinak \end{cases}$
- $\chi_B(f(x_1, …, x_k)) \implies f^{-1}(B)$ je rek, $\chi_B$ je TVF
-
- $(x_1,…,x_k,y_1,..,y_e) \in A \times B \iff (x_1,…,x_k) \in A \land (y_1,..,y_e) \in B$
- strana 7:
- $W_i^{(k)} = dom(\varphi_i^{(k)})$
- $W_j^{(k)} = dom(\varphi_j^{(k)})$
begin
\Phi(i, x_1, ..., x_k);
\Phi(j, x_{k+1}, ..., x_{k+e});
end
- $h(i,j)$ počítá kód programu $\uparrow \implies TVF$