0
$\begingroup$

Theorem

Let be $A$ a set and let be $S:=\bigcup_{n\in\Bbb{N}}(A^n)$ and finally let be $g:S\rightarrow A$ a function. So there exist a unique function $f:\Bbb{N}\rightarrow A$ such that $$f(n)=g(f|_n)$$ for any $n\in\Bbb{N}$.

My text suggest to use the recursion to prove the last theorem: however I can't prove it and so could someone help me, please?

$\endgroup$
2
$\begingroup$

Define $\varphi:S\to S$ as follows: if $\sigma\in A^n$, then $\varphi(\sigma)=\sigma\cup\{\langle n,g(\sigma)\rangle\}$. If you think of $\sigma$ as a sequence $\langle\sigma(0),\sigma(1),\ldots,\sigma(n-1)\rangle$ of element of $A$, $\varphi$ simply extends that sequence by one term, so that $\varphi(\sigma)$ can be thought of as the sequence $\langle\sigma(0),\sigma(1),\ldots,\sigma(n-1),g(\sigma)\rangle$. By the recursion theorem there is a function $\Phi:\Bbb N\to S$ such that $\Phi(0)=\varnothing$ and $\Phi(n+1)=\varphi(\Phi(n))$ for each $n\in\Bbb N$.

  • Prove by induction that $\Phi(n)\in A^n$ for each $n\in\Bbb N$.
  • Prove that $\Phi(n+1)\upharpoonright n=\Phi(n)$ for each $n\in\Bbb N$.

Define $f:\Bbb N\to A:n\mapsto\big(\Phi(n+1)\big)(n)$.

  • Show by induction that $f\upharpoonright n=\Phi(n)$ for each $n\in\Bbb N$.
  • Show that $f(n)=g(f\upharpoonright n)$ for each $n\in\Bbb N$.
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.