Proof that mappings $K$ and $L$ are primitive recursive.

Question

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.

Answer 1

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.