0
$\begingroup$

I am not sure what strategy to use to I should use to show this is primitive recursive. I believe I am to show all three cases: primitive recursive, recursive, and semi-recursive.

The diagonal of $R$, given by $D(x)\iff R(x,x)$.

and

For any natural number $m$, the vertical and horizontal sections of $R$ at $m$, given by

$R_{m}(y)\iff R(m,y)$

and

$R^{m}(x)\iff R(x,m)$.

For the first relation, my attempt was

$ D(x) \iff R(x,x) \iff R(id^{1}_{1}(x),id^{1}_{1}(x))$ for the primitive recursion case, and

$ D(x) \iff R(x,x) \iff \exists z R(x,x,z) \iff \exists z R(id^{3}_{1}(x,y,z),id^{3}_{1}(x,y,z),id^{3}_{3}(x,y,z))$ for the semi-recursive case (where $id^{n}_{i}(a_1,a_2,...,a_i,...a_n)=a_i$ is the projection function);

however, I am not sure how to proceed differently for the (regular) recursive case. With the horizontal and vertical relations, I am unsure how I would go about introducing $m$ as any natural number. If anyone could start me in the right direction I would gladly post further attempts.

For reference, I am utilizing Boolos, Burgess, Jeffrey Computability and Logic, 5E

$\endgroup$
  • 1
    $\begingroup$ Your notation $Cn[R,id_1^1]$ looks like it is part of a particular formalism for writing down primitive recursive definitions. Such formalisms are usually invented from thin air by each textbook author, so you should not expect people who're not using the particular textbook you're taught from to understand its details -- I can imagine what $id_1^1$ means, but the $Cn$ would be particular to your system, and you need to explain how it works. $\endgroup$ – hmakholm left over Monica Mar 31 '16 at 11:57
  • $\begingroup$ @HenningMakholm My mistake - Cn[a,b] is in this case the composition operator. I have expanded the compositions in the post to clarify this. Thank you! $\endgroup$ – faux Mar 31 '16 at 12:07
2
$\begingroup$

With the horizontal and vertical relations, I am unsure how I would go about introducing $m$ as any natural number. If anyone could start me in the right direction I would gladly post further attempts.

For any $m$, the constant function that returns $m$ for every input value is primitive recursive. It can be made by composing the constant zero function (p.r. by definition) with the successor function an appropriate number of times.

| cite | improve this answer | |
$\endgroup$

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.