8
$\begingroup$

Let $g(a), h(a,n,b), p(a)$ be primitive recursive functions. Consider the function $\phi(a,n)$ defined recursively by $$ \phi(a,0) = g(a) \\ \phi(a,sn) = h(a,n,\phi(p(a), n)) $$ Question: Is $\phi$ primitive recursive?

Usually, the construction of primitive recursive functions only permits constructions using the recursive scheme $\phi(a,sn) = h(a,n,\phi(a,n))$, so I'm wondering if this modified scheme (which includes $p$) still produces primitive recursive functions. It seems like it should work, since we're still decreasing the index every time, but I can't quite work out a proof.

Context: this problem came up in some research I'm doing involving natural numbers objects. As such, I'm hoping to translate any solution into a categorical context.

Attempt: I've noticed that I can define the function $\hat{\phi}(m,a,n)$ recursively by $$ \hat{\phi}(m,a,0) = g(p^m(a)) \\ \hat{\phi}(m,a,sn) = h(p^{m-sn}(a), n, \hat{\phi}(m,a,n)) $$ (where subtraction can't go lower than $0$), and then setting $\phi(a,n) = \hat{\phi}(n,a,n)$ should work. However, I can't prove (categorically) that this construction does indeed satisfy $\phi(a,sn) = h(a,n,\phi(p(a),n))$. It seems to require showing that $\hat{\phi}(sn,a,n) = \hat{\phi}(n,p(a),n)$, which is difficult to do inductively, and the more general statement $\hat{\phi}(sm,a,n) = \hat{\phi}(m,p(a),n)$ only holds for $m \geq n$, which makes induction on $n$ tricky.

$\endgroup$
2
  • $\begingroup$ Here's a high level idea of why this might be pr. You basically compute all iterates of $p$ and slowly unfold them. More concretely, consider a function that on input $a$ and $n$, returns the godel encoding of the all iterates of $p$ until $n$, that is the code of the tuple $(a,p(a),p^2(a),\dots,p^n(a))$. Then you do an unfolding operation on the tuple, that is on input $b,k$ ($b$ is a code), you output $g(\text{$k$-th element of code $b$})$ if $k=0$ or output $h(\text{$k$-th element of code $b$},k,\text{unfold on $b,k-1$})$. Finally you define a function that passes $a$ and $n$... $\endgroup$ Commented May 28 at 19:00
  • $\begingroup$ to the unfolding operation via $s(a,n)$ and $n$. I think this should be your original function, but I am not a 100% sure. $\endgroup$ Commented May 28 at 19:02

2 Answers 2

Reset to default
5
$\begingroup$

I suspect you have got a bit of symbol overload. I think your attempt looks about right - there is a straightforward way to compute $\phi(a, n)$ without resorting to any finite sequence encodings. I think it helps a lot to think of primitive recursive functions imperatively, as "programs that only use for -loops, where the number of iterations is known before entering the loop". From this perspective I think it's quite easy to convince yourself that this function is primitive recursive.

Indeed, suppose we're given $g(a)$, $h(a, n, b)$ and $p(a)$. Here is a procedure very similar to yours, but with slightly more suggestive notation, that will compute $\phi(a, n)$:

Fix $a$ and $n$. Define $x_0 = g(p^n(a))$. Let $x_{i + 1} = h(p^{n - i - 1}(a), i, x_i)$ (I hope you agree that this is just a normal primitive recursion). Then $x_n = \phi(a, n)$.

I think it's easiest to convince yourself this is correct by just expanding the definition of $\phi(a, n)$ by hand for a bit and seeing the pattern (this is just a "bottom-up calculation"). But I'll give you a more formal argument as well.

Write $x_i(a, n)$ for the $x_i$ as defined above (I'm having to make the parameters explicit as I'll have to talk about varying $a$). First, observe this fact: that for $i \le n$, we have $x_i(a, n + 1) = x_i(p(a), n)$. This is easy to see by induction on $i$:

  • Clearly $x_0(a, n + 1) = g(p^{n + 1}(a)) = x_0(p(a), n)$.
  • Moreover, then $x_{i + 1}(a, n + 1) = h(p^{n - i}(a), i, x_i(a, n + 1))$ and $x_{i + 1}(p(a), n) = h(p^{n - i}(a), i, x_i(p(a), n))$. The inductive hypothesis tells us these are equal. (We needed the assumption $i + 1 \le n$ to ensure that $p^{n - i - 1}(p(a)) = p^{n - i}(a)$). This finishes the proof of the fact.

I'll now prove the final result by induction on $n$: that for all $a$, we have $x_n(a, n) = \phi(a, n)$.

  • Indeed, $x_0(a, 0) = g(p^0(a)) = g(a) = \phi(a, 0)$.
  • But also, \begin{align*} x_{n + 1}(a, n + 1) &= h(a, n, x_n(a, n + 1)) \\ &= h(a, n, x_n(p(a), n)) \\ &= h(a, n, \phi(p(a), n)) \\ &= \phi(a, n + 1) \end{align*} Where we used the definition of $x_{n + 1}$, the fact above with $i = n$, the inductive hypothesis, and the definition of $\phi(a, n + 1)$ respectively. This finishes the proof.

I guess the reason you struggled is because of the "double induction" required. This related to the fact that the definition of $\phi$ being well-founded relies on the fact that $\omega^2$ is well-ordered.

$\endgroup$
6
  • 1
    $\begingroup$ Ah this is much simpler than what I did. I was looking at it more from a machine-perspective and had to go through a lot of separate functions. This is much more elegant! $\endgroup$ Commented May 28 at 20:37
  • 1
    $\begingroup$ @HackR, I like your answer too - the "sledgehammer approach" really shows why $\phi$ had no hope at all of not being primitive recursive. I posted this one as well as I was halfway through writing it and it seems that Sambo may have use for different arguments in the category-theoretic setting. $\endgroup$ Commented May 28 at 20:45
  • $\begingroup$ This seems to pretty much be the argument I had in mind. The part I'm struggling with is the proof that, if $i \leq n$, then $x_i(a,n+1) = x_i(p(a),n)$. I can certainly follow your argument, and it makes sense to me - but this sort of "finite induction" is hard to handle categorically. $\endgroup$ Commented May 28 at 20:48
  • $\begingroup$ I am grateful for your answer, though - it's a good sanity check, and it suggests that I just need a clever way to handle this finite induction in order to finish the proof. $\endgroup$ Commented May 28 at 20:49
  • $\begingroup$ In case it's of any interest, I did find a trick to solve this categorically. Instead of showing $x_i(a,n+1) = x_i(p(a),n)$ for $i \leq n$ (which uses finite induction on $i$), I showed that $x_{\min(i,n)}(a,n+1) = x_{\min(i,n)}(p(a),n)$ for all $i$ (which can be done with regular infinite induction). $\endgroup$ Commented May 28 at 21:13
3
$\begingroup$

I believe the outline of the proof in the comment works. Here's a more detailed account of it. I will write $n+1$ for the $sn$ in your setup just for clarity.

In what follows, fix a Godel encoding of finite sequences/tuples, preferably the prime-power coding. I insist on it because it makes it easy to see why the functions $$\text{append}(t,x) : \text{takes in a tuple's encoding $t$ and appends $x$ at the end}$$ $$\text{last}(t) : \text{takes in the encoding of a tuple and outputs the last element of the tuple}$$ $$\text{elt}(t,k): \text{takes in the encoding of a tuple and outputs its $k$-th element}$$ $$\text{tail}(t) : \text{takes in the encoding of a tuple and returns the encoding of a tuple without the first element}$$ are primitive recursive.

Well, now we do the following. Define the function \begin{align*}s(a,0)&=\langle a\rangle\\ s(a,n+1)&=\text{append}(s(a,n),p(\text{last}(s(a,n))))\end{align*}

This function basically returns the code of the first $n$ iterates of $p$ on $a$. More cleanly $$s(a,n)=\langle a, p(a),p^2(a),\dots, p^n(a)\rangle$$

Now we get to defining the unfolding of a tuple and applying $g$ to it, then stepping back through the tuple applying $h$ at each stage. Formally, define $$\text{unfold}_h(t,k)=\begin{cases}g(\text{elt}(t,k))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{if $k=0$}\\ h(\text{elt}(t,0),k-1,\text{unfold}_h(\text{tail}(t),k-1))\ \ \text{if $k>0$}\end{cases}$$

Now we glue them together $$\psi(a,n)=\text{unfold}_h(s(a,n),n)$$

I claim that $$\phi(a,n)=\psi(a,n)$$

The base case is $n=0$. By definition of $s$, we have $$s(a,0)=\langle a\rangle$$ and $$\text{elt}(s(a,0),0)=a$$ Thus we have $$\psi(a,0)=\text{unfold}_h(s(a,0),0)=g(\text{elt}(s(a,0),0))=g(a)=\phi(a,0)$$

Now assume this is true for some $n\ge 0$. That is, assume $$\phi(a,n)=\psi(a,n)$$ Then for $n+1$, we have $$\psi(a,n+1)=\text{unfold}_h(s(a,n+1),n+1)$$ Now $\text{elt}(s(a,n+1),0)=a$, we get \begin{align*}\psi(a,n+1)&= \text{unfold}_h(s(a,n+1),n+1)\\&=h(\text{elt}(s(a,n+1),0),n,\text{unfold}_h(\text{tail}(s(a,n+1)),n))\\&=h(a,n,\text{unfold}_h(\text{tail}(s(a,n+1)),n))\\&=h(a,n,\text{unfold}_h(s(p(a),n),n))\\&=h(a,n,\psi(p(a),n))\\&=h(a,n,\phi(p(a),n))\\&=\phi(a,n+1)\end{align*}

This finishes the induction.

$\endgroup$
3
  • $\begingroup$ Interesting. This suggests to me that, if we want to interpret this in a categorical context, we need to assume that we're working in a category with list objects, unless there's a simpler solution. $\endgroup$ Commented May 28 at 20:29
  • 1
    $\begingroup$ (In my question, I made the domains of all functions be powers of $\Bbb{N}$, for simplicity. Categorically, this corresponds to working inside a Skolem theory, i.e. a category whose objects are finite products of $\Bbb{N}$, and these have list objects precisely by the Gödel encoding argument. This work was originally done by Joyal in unpublished notes/lectures, but is noted in "Joyal's arithmetic universe as list-arithmetic pretopos" by Maietti.) $\endgroup$ Commented May 28 at 20:34
  • $\begingroup$ I don't really think you need to store all the iterates of p. You can calculate them up as you need. Izaak's answer shows you how to take an extra index to do it. $\endgroup$ Commented May 28 at 20:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.