# Primitive recursive functions definition (understanding “composition” and “primitive recursion”)

$\newcommand{\N}{\Bbb{N}}$ I am trying to understand the concept of primitive recursive functions, using the definition in the Open Logic Text (Definition 14.3):

The set of primitive recursive functions is [...] the smallest set containing the constant 0, the successor function, and projection functions, and closed under composition and primitive recursion.

My question is about the way composition is defined in OL, which does not seem very intuitive to me (see Definition 14.1):

If $f$ is a $k$-ary function and $g_0, \dots,g_{k-1}$ are $l$-ary functions on the natural numbers, the composition of $f$ with $g_0, \dots,g_{k-1}$ is the $l$-ary function $h$ defined by $$h(x_0,\dots,x_{l-1}) = f(g_0(x_0,\dots,x_{l-1}),\dots,g_{k-1}(x_0,\dots,x_{l-1})) .$$

Is this just another (a very formal) way of stating composition as one may understand it in real analysis: that if we have $$g\colon\N^l\to\N^k\quad\text {and}\quad f\colon\N^k\to\N,$$ then we can define some composed function $$h\colon\N^l\to\N?$$ Or, would there be any "risk" at looking at the definition in this simplistic way?

The same question applies to the OL definition of primitive recursion (14.2): can this be simply seen as defining the function for $0$, and then defining it for $x+1$ using the function evaluated at $x$? (I note that there are no restrictions mentioned, aside from arities, on $f$ and $g$.)

## 1 Answer

It's a matter of technical convenience. You could define the primitive recursive functions to be a set of functions from $\Bbb{N}$ to $\Bbb{N}$, but then to deal with functions of more than one argument (like addition and multiplication), you'd have to show how to represent pairs of natural numbers as natural numbers. Alternatively, you could define the primitive recursive functions to be functions from $\Bbb{N}^m$ to $\Bbb{N}^n$ for arbitrary $m$ and $n$ (so your $g$ would be a possible primitive recursive function), but any such function would really just comprise $n$ functions from $\Bbb{N}^m$ to $\Bbb{N}$. Your text is taking the standard compromise of defining primitive recursive functions to map $\Bbb{N}^m$ to $\Bbb{N}$. This means that to construct a function like $(x, y) \mapsto x^2 + y^3$ you need a notion of functional composition that lets you view it as a composition of the pair of functions $(x \mapsto x^2,y \mapsto y^3)$ with the function $(a, b) \mapsto a + b$.