I'm currently working through a few books on computability and I am having a little bit of trouble with the primitive recursive scheme. When defining the primitive recursive scheme for unary functions most authors give something like the following:

$\text{For function $h$ which is primitive recursive, the function $f$ defined by}$ $$f(0)=m $$ $$f(n+1)=h(n,f(n))$$ is primitive recursive where $m$ is a zero-ary constant function and where $h$ is a binary function.

My question is can we view $h$ as a unary function since it seems to depend on only $n$? I feel like I could define $g(n)=h(n,f(n))$ where g is unary. This would then violate the requirement that the arity of $h$ be $k+1$ if the arity of $f$ is $k$. I'm just a little confused about how the arity requirement works in the unary case.

Edit: In addition to the above question, I'm curious about performing primitive recursion on zero-ary functions. For example, one of the authors I'm reading defines the zero-ary constant function $o'()=0$. He then proceeds to define the family of zero-ary constant functions $c_i'()=i$ as follows: $$c_0'(0)=o'()$$ and $$c_{n+1}'()=S((c_{n}'())$$ where S is the successor function. It seems like this violates the primitive recursive scheme conditions as well with $c_0'(0)$ having arity 1 and $c_{n+1}'()$ having the same arity as $S((c_{n}'())$ . I'm guessing something is going on in the background, but I can't seem to see it.


2 Answers 2


You can indeed define $g(n)=h(n,f(n))$ (as I assume you intended to write) -- but in order to argue that this $g$ is primitive recursive, you need to already know that $f$ (as well as $h$) is primitive recursive, and for that you need to apply the primitive recursion rule, which depends on knowing that $h$ is primitive recursive.

Note well that what the primitive recursion rule demands as a premise is that $h$ is primitive recursive as a two-argument function. That is the function that describes how to combine $n$ and $f(n)$ in order to find the number you want to be $f(n+1)$. In principle this $h$ needs to be applicable to every pair of numbers, not just ones where the second element happens to be $f$ applied to the first one. If you can't give such a general rule for $h$, the primitive recursion construction does not -- by definition -- necessarily produce a primitive recursive $f$.

In response to the added material headed "edit": The construction you're quoting seems to arguing for the theorem that every constant function is primitive recursive. This conclusion is certainly true, but the argument you're quoting does not use the primitive recursion rule at all. It works by induction at the metalevel, but does not use recursion as a building block for functions.

In fact the same argument would work to prove this:

Define the class of supersimple function by the following rules:

  1. The zero function is supersimple.
  2. The successor function is supersimple.
  3. All $n$-ary projection functions are supersimple.
  4. Every function that arises by composition of supersimple function is supersimple.
  5. No other functions are supersimple.

Theorem. Every constant function $\mathbb N^n\to\mathbb N$ (where $n\ge 0$) is supersimple.

You should recognize rules 1-4 as exactly the same as the corresponding parts of the definition of primitive recursive functions. The primitive recursion rule is missing, but it should be clear that every "supersimple" function is necessarily also "primitive recursive".

And the reason why the constant functions are supersimple is exactly the same as the reason why they are primitive recursive.

  • $\begingroup$ So it isn't possible to perform primitive recursion on a zero-ary function? $\endgroup$
    – Newman
    Apr 2, 2019 at 0:28
  • $\begingroup$ @Newman: zero-ary function $\equiv$ constant? $\endgroup$
    – hardmath
    Apr 2, 2019 at 1:00
  • $\begingroup$ @hardmath Yes, I believe that's the convention this author is using. He actually defines a zero-ary zero function $c_0'()=0$ and a unary zero function $c_0(n)=0$ for every n. $\endgroup$
    – Newman
    Apr 2, 2019 at 1:06

Any function $f$ that is obtained from primitive recursion is constructed from two prim. rec. functions g,h. If $g \colon \mathbb{N}^k \rightarrow \mathbb{N}$ and $h \colon \mathbb{N}^{k + 2} \rightarrow \mathbb{N}$ are both primitive recursive then there is a unique function $f \colon \mathbb{N}^{k + 1} \rightarrow \mathbb{N}$ such that $$ f(x,0) = g(x)\\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x \in \mathbb{N}^k, y \in \mathbb{N}$. $g$ tells us where we start the recursion, $h$ is the recursive rule.

Technically, however, in primitive recursion all functions are total (i.e. are defined on all inputs and always converge). So, in particular, $h$ is really defined for all $z \in \mathbb{N}$, not only for previous values of $f$! That is, we define $h(x,y,z)$ rather than $h(x,y,f(x,y))$. To answer your second question, recursion is based on the idea of defining the next value of a function given the previous input and, crucially, the previous value of said function. So no, $h$ must be of arity $\mathbb{N}^{k + 2}$. Also note that you cannot use $f$ in the definition of $h$ as the existence of $f$ is implied by the existence and primitive recursiveness of both $g$ and $h$.

  • $\begingroup$ @hardmath Indeed, fixed it -- thanks! $\endgroup$
    – MacRance
    Apr 2, 2019 at 1:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .