0
$\begingroup$

Which function results from primitive recursion of the functions $g$ and $h$?

  1. $f_1=PR(g,h)$ with $g=succ\circ zero_0, h=zero_2$
  2. $f_2=PR(g,h)$ with $g=zero_0, h=f_1\circ P_1^{(2)}$
  3. $f_3=PR(g,h)$ with $g=P_1^{(2)}, h=P_2^{(4)}$
  4. $f_4=PR(g,h)$ with $g=f_3\left(f_1(x),succ(x),f_2(x)\right)$

(1.) $g:N^0\to N$, $h:N^2\to N$
$f(0)=1$
$f(0+1)=h(0,f(0))=h(0,1)=0$
$f(1+1)=h(1,f(1))=h(1,0)=0$
$\forall n\in N_{>0}:f(n+1)=h(n,f(n))=0$, $f_1$ is defined as $f_1:N^1\to N$ with $f_1(x)=\begin{cases}1, x=0\\ 0, x>0\end{cases}$

(2.) $g:N^0\to N$, $h:N^2\to N$
$f(0)=0$
$f(0+1)=h(0,f(0))=h(0,0)=1$ $f(1+1)=h(1,f(1))=h(1,1)=0$ $\forall n\in N_{>0}: f(n+1)=h(n,f(n))=0$, $f_2$ is defined the same as $f_1$, $f_1(x)=f_2(x)$

(3.) $g:N^2\to N$, $h:N^4\to N$
$f(x,y,0)=x$
$f(x,y,0+1)=h(x,y,0,f(x,y,0))=h(x,y,0,x)=y$ $f(x,y,1+1)=h(x,y,1,f(x,y,1))=h(x,y,1,y)=y$ $\forall z \in N_{>0}: f(x,y,z+1)=h(x,y,z,f(x,y,z))=y$, $f_3$ is defined as $f_3:N^3\to N$ with $f_3(x,y,z)=\begin{cases}x, z=0\\ y, z>0\end{cases}$

Is this correct up to here? It looks way too easy, that's why I'm not sure.

$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Sep 10 at 6:47
  • $\begingroup$ Sry, I forgot about the different rules here in comparison to the MathStackExchange. I will rewrite it if I have time. $\endgroup$ – Doesbaddel Sep 10 at 8:54

Your Answer

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

Browse other questions tagged or ask your own question.