Let $r_n : \mathbb{{N}^{n}} \rightarrow \mathbb{N}$ a fixed bijection. Show that $f$ is recursive iff $r_n \circ f \circ (r_k)^{-1}$ is recursive.

Question

Let $r_n : \mathbb{{N}^{n}} \rightarrow \mathbb{N}$ a fixed bijection.

I have to show that $f : \mathbb{{N}^{k}} \rightarrow \mathbb{{N}^{n}}$ is recursive iff $r_n \circ f : \mathbb{{N}^{k}} \rightarrow \mathbb{N}$ is recursive and iff $r_n \circ f \circ (r_k)^{-1} : \mathbb{N} \rightarrow \mathbb{N} $ is recursive too.

For the "left to right" side, I am tempted to use the fact that a composition of recursive function is also recursive. Can we make the jump from "fixed bijection" to "recursive" ? Namely is every fixed bijection necessarily computable ?

For the "right to left" side, I was thinking of using a proof by "contraposition", i.e. if $r_n \circ f$ is not recursive then by some properties $f$ would not be neither but I can't find any.

I am fairly new to this field and website therefore I would appreciate hints/solutions that doesn't involve too complex material.

Thanks.

Answer 1

This is not true as stated; it is only true if the $r_n$ are required to be recursive.

You can see that the indicated property implies that $r_n$ is recursive by taking $k=n$ and $f$ equal to the identity function.

If you do assume that the $r_n$ are recursive, then each $r_n^{-1}$ is also recursive, and the statement follows immediately, using the fact that the composition of recursive functions is recursive.