1
$\begingroup$

Let $J$ be the function: \begin{equation*} J(m,n)= \begin{cases} n^2+m \text { if } m\le n \\ m^2 + m + (m-n) \text { if } m > n \\ \end{cases} \end{equation*}

Let $K, L$ such that

$K(k)$ is the unique $n \in \mathbb{N}$ for which there is some $m\in \mathbb{N} $ such that $J(n,m)=k$

$L(k)$ is the unique $m \in \mathbb{N}$ for which there is some $n \in \mathbb{N} $ such that $J(n,m)=k$

Prove that $K$ and $L$ are primitive recursive.

I know and have proved that $J$ is primitive recursive, so I can work with that. I also know that I have to work with the minimisation, to show that it can be bounded by a primitive recursive function. Now I start to get into trouble. I think the minimisation can be written as $K(k)= \mu n (\exists x < k + 1)J(n,x)=k$, but I don't really know where to go from here. I would very much appreciate any input you could give me, I have some trouble really finding the functions that minimise the things.

$\endgroup$
1
$\begingroup$

First consider the function $L^\prime(y,k)=\mu x<k+1[J(x,y)-k=0]$, which is primitive recursive since the primitive recursive functions are closed under substitution and bounded minimization.

Then we get that $L(k)=\mu y<k+1[J(L^\prime(y,k),y)-k=0]$. Again, since the primitive recursive functions are closed under substitution and bounded minimization, then $L$ is primitive recursive.

You can now apply the same idea to see that $K$ is also primitive recursive.

$\endgroup$
  • $\begingroup$ Thank you, this helps me see it much more clearly! $\endgroup$ – Sara May 6 '15 at 11:06

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.