# Primitive recursive permutations

How to show that the inverse of a primitive recursive permutation of $$\mathbb{N}$$ is not necessarily a primitive recursive function?

• Does it necessarily have to be a bijection? The inverse of the Ackermann function is known to be primitive recursive (since Ackermann has a primitive recursive graph). (I guess maybe you can pad this out into a primitive recursive bijection too). May 9 at 14:15
• @AnupamDas: yes. It is easy to show that recursive permutations form a group under composition. But primitive recursive permutations do not; that is why I would like to show (or see a proof...) that the inverse of a primitive recursive permutation might be non-primitive recursive. Thank you for pointing out that property of Ackermann function.
– ijon
May 10 at 9:30
• I had not seen this before, but a quick search led to descriptions of (essentially the same) counterexamples here (math.stackexchange.com/questions/2975305/…) and here (ncatlab.org/nlab/show/partial+recursive+function#inverse). May 10 at 20:11
• @NoamZeilberger Thanks!
– ijon
May 14 at 20:32

Given a set $$X\not\ni 0$$, let $$\pi_X$$ be the permutation of $$\mathbb{N}$$ defined as follows: $$\pi_X(x)=\begin{cases} x+1 & \mbox{ if }x\not\in X,\\ \max(\{y\in X: y
This basically breaks $$\mathbb{N}$$ into finite loops. Now if the characteristic function of $$X$$ is primitive recursive, so is the function $$\pi_X$$. However, if $$X$$ is extremely sparse then $$\pi_X^{-1}$$ will fail to be primitive recursive since it will have to grow extremely quickly.
In particular, if we let $$X$$ be the range of the Ackermann function, we get $$\pi_X$$ primitive recursive but $$\pi_X^{-1}$$ not primitive recursive.