<p>Given a set <span class="math-container">$X\not\ni 0$</span>, let <span class="math-container">$\pi_X$</span> be the permutation of <span class="math-container">$\mathbb{N}$</span> defined as follows: <span class="math-container">$$\pi_X(x)=\begin{cases}
x+1 &amp; \mbox{ if }x\not\in X,\\
\max(\{y\in X: y&lt;x\}\cup \{0\}) &amp; \mbox{ if }x\in X.\\
\end{cases}$$</span></p>
<p>This basically breaks <span class="math-container">$\mathbb{N}$</span> into finite loops. Now if the characteristic function of <span class="math-container">$X$</span> is primitive recursive, so is the function <span class="math-container">$\pi_X$</span>. However, if <span class="math-container">$X$</span> is extremely sparse then <span class="math-container">$\pi_X^{-1}$</span> will fail to be primitive recursive since it will have to grow extremely quickly.</p>
<p>In particular, if we let <span class="math-container">$X$</span> be the <em>range</em> of the Ackermann function, we get <span class="math-container">$\pi_X$</span> primitive recursive but <span class="math-container">$\pi_X^{-1}$</span> not primitive recursive.</p>
<hr />
<p>EDIT: I just learned of an old strengthening of the above, due to Cannonito and Finkelstein (&quot;<a href="https://www.jstor.org/stable/2270855" rel="nofollow noreferrer">On primitive recursive permutations and their inverses</a>&quot;). The argument is short enough to reproduce here.</p>
<blockquote>
<p><strong>Theorem</strong> <em>(Cannonito/Finkelstein, improving on Kuznecov/Kent/J. Robinson)</em>: Let <span class="math-container">$\mathscr{E}^i$</span> be the <span class="math-container">$i$</span>th level of the Grzegorczyk hierarchy. Then there are <span class="math-container">$A,C\in\mathscr{E}^3$</span> such that, for every total recursive unary <span class="math-container">$f$</span>, there is a permutation <span class="math-container">$B\in\mathscr{E}^3$</span> with <span class="math-container">$$f=AB^{-1}C.$$</span> In particular, taking <span class="math-container">$f$</span> &quot;wild&quot; requires <span class="math-container">$B^{-1}$</span> to be &quot;wild&quot; as well.</p>
</blockquote>
<p><em>Proof</em>. Letting <span class="math-container">$e$</span> be a fixed index for <span class="math-container">$f$</span>, we define the required functions as follows:</p>
<ul>
<li><p><span class="math-container">$C\simeq \lambda x.2x$</span>.</p>
</li>
<li><p><span class="math-container">$A$</span> is an appropriately universal function <span class="math-container">$U$</span>, such that whenever <span class="math-container">$y$</span> codes a halting computation of <span class="math-container">$\varphi_e(x)$</span> then <span class="math-container">$U(y)=\varphi_e(x)$</span>. (It's not obvious that this can be done in <span class="math-container">$\mathscr{E}^3$</span>, but it is true.)</p>
</li>
<li><p>Finally, to get <span class="math-container">$B$</span> we consider the set <span class="math-container">$E$</span> of numbers which code the (halting) computation of <span class="math-container">$f$</span> (via the fixed index <span class="math-container">$e$</span>) on some input. The characteristic function of <span class="math-container">$E$</span> is in <span class="math-container">$\mathscr{E}^3$</span>, and so the permutation sending <span class="math-container">$y$</span> to <span class="math-container">$2x$</span> if <span class="math-container">$y\in E$</span> and <span class="math-container">$y$</span> codes the behavior of <span class="math-container">$f(x)$</span>, and sending <span class="math-container">$y$</span> to <span class="math-container">$$\max\{0,2\left(\sum_{k\le y}\chi_E(k)\right)-1\}$$</span> otherwise. This permutation is our <span class="math-container">$B$</span>.</p>
</li>
</ul>
<p>Cannonito/Finkelstein go on to derive some neat group-theoretic consequences of the above.</p>

CC BY-SA 4.0
2024-05-12T00:36:05.217Z
2024-06-10T02:30:52.600Z
2024-06-10T02:30:52.600Z
Noah Schweber
<p>How to show that the inverse of a primitive recursive permutation of <span class="math-container">$\mathbb{N}$</span> is not necessarily a primitive recursive function?</p>

CC BY-SA 4.0
2024-05-09T14:15:37.107Z
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).
Anupam Das
CC BY-SA 4.0
2024-05-10T09:30:22.760Z
@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
CC BY-SA 4.0
2024-05-10T20:11:41.447Z
I had not seen this before, but a quick search led to descriptions of (essentially the same) counterexamples here (https://math.stackexchange.com/questions/2975305/inverse-of-a-primitive-recursive-bijection) and here (https://ncatlab.org/nlab/show/partial+recursive+function#inverse).
Noam Zeilberger
CC BY-SA 4.0
2024-05-14T20:32:16.133Z
@NoamZeilberger Thanks!
ijon
<computability>
Primitive recursive permutations
ijon
# Primitive recursive permutations

(Asked by: username_0 on 2024-05-08)

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

**Tags:** computability

> **Comments:**
> **username_1**: 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).  
> **username_0**: @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.  
> **username_2**: I had not seen this before, but a quick search led to descriptions of (essentially the same) counterexamples here (https://math.stackexchange.com/questions/2975305/inverse-of-a-primitive-recursive-bijection) and here (https://ncatlab.org/nlab/show/partial+recursive+function#inverse).  
> **username_0**: @NoamZeilberger Thanks!  

---

## 1 answers

### Answer by username_3 on 2024-05-12. Score: 5 | Accepted answer

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.

---

EDIT: I just learned of an old strengthening of the above, due to Cannonito and Finkelstein ("[On primitive recursive permutations and their inverses](https://www.jstor.org/stable/2270855)"). The argument is short enough to reproduce here.

> **Theorem** *(Cannonito/Finkelstein, improving on Kuznecov/Kent/J. Robinson)*: Let $\mathscr{E}^i$ be the $i$th level of the Grzegorczyk hierarchy. Then there are $A,C\in\mathscr{E}^3$ such that, for every total recursive unary $f$, there is a permutation $B\in\mathscr{E}^3$ with $$f=AB^{-1}C.$$ In particular, taking $f$ "wild" requires $B^{-1}$ to be "wild" as well.

*Proof*. Letting $e$ be a fixed index for $f$, we define the required functions as follows:

* $C\simeq \lambda x.2x$.
* $A$ is an appropriately universal function $U$, such that whenever $y$ codes a halting computation of $\varphi\_e(x)$ then $U(y)=\varphi\_e(x)$. (It's not obvious that this can be done in $\mathscr{E}^3$, but it is true.)
* Finally, to get $B$ we consider the set $E$ of numbers which code the (halting) computation of $f$ (via the fixed index $e$) on some input. The characteristic function of $E$ is in $\mathscr{E}^3$, and so the permutation sending $y$ to $2x$ if $y\in E$ and $y$ codes the behavior of $f(x)$, and sending $y$ to $$\max\{0,2\left(\sum\_{k\le y}\chi\_E(k)\right)-1\}$$ otherwise. This permutation is our $B$.

Cannonito/Finkelstein go on to derive some neat group-theoretic consequences of the above.


---

