Bdtyk

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.

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 recursion, 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 be confusing at best. Note that primitive recursion does not define a sequence of functions, but a single function. And it does not make sense to use primitive recursion without having an argument to recurse over.

The best way I can get what you quote to make sense is to say that "$c'_i()$" must be merely an obfuscated way to write "$c'(i)$". The construction defines a complete unary function $c'$ all at once. One may then prefer to speak about this function like an infinite sequence of constants, but that does not change what was "really" going on at the formal level.

Alternatively, the author you quote is doing model theory, and is using recursion at the metalevel to define meanings for an infinity of new constant symbols. Then there's a priori nothing that constrains him to be using primitive recursion, or even recursion at all -- indeed, any way of defining the meanings in the (usually informal) style of reasoning he's using at the metalevel would work.

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$.