Suppose we want to build functions with domain \(\mathbb{N}^n\) and codomain \(\mathbb{N}\) starting from some basic functions using simple mechanical rules. What would we need at the minimum?
As it stands, the question is unanswerable because it is too vague. What is considered basic? What is considered mechanical? Nevertheless, let us look at some common functions and see what should be included.
At the very least, we should be able to add. Therefore, \(f(x_1,x_2) = x_1 + x_2\) could be a candidate for a basic function. But this function is already problematic by itself as evidenced by how long it takes children to learn addition. A more basic function would be the successor function \(s(x) = x+1\). It is quite easy to count up by one. With \(s\), \(5+3\) is simply \(s(s(s(5)))\).
To obtain the function \(f(x_1,x_2) = x_1 + x_2\) from the successor function, we need to be able to define functions using a simple form of recursion: \begin{eqnarray*} f(x,0) & = & x \\ f(x,y+1) & = & s(f(x,y)). \end{eqnarray*}
Then \(f\) as defined above will give the sum of its arguments.
What if we want to obtain the function \(g(x,y,z) = x+y+z\)? We can do this if we can compose functions: \[g(x,y,z) = f(x,f(y,z)).\]
Once we can add two numbers, we can multiply two numbers as well: \begin{eqnarray*} h(x,0) & = & 0 \\ h(x,y+1) & = & f(x,h(x,y)). \end{eqnarray*}
The next thing we should be able to do is subtraction.
Note that we need to be careful about what we mean by subtraction. It cannot be in the regular sense because the codomain has no negative numbers. We will adopt the convention that \(x - y = 0\) if \(x\) is less than \(y\). We use the symbol \(\dot{-}\) to denote this version of “subtraction” and call it truncated subtraction. Before we define truncated subtraction, we first define the predecessor function recursively: \begin{eqnarray*} p(0) & = & 0 \\ p(y+1) & = & y. \end{eqnarray*} Then \(d(x,y) = x ~\dot{-} ~y\) can be defined recursively: \begin{eqnarray*} d(x,0) & = & x \\ d(x,y+1) & = & p(d(x,y)). \end{eqnarray*}
Let us look at functions that are even simpler: the constant functions. Since we have the successor function already, we just need to have the zero functions; that is \begin{eqnarray*} \operatorname{n}(x_1,\ldots,x_n) = 0 \end{eqnarray*}
Remark. In fact, constants can be treated as 0-ary functions; i.e. functions with no arguments. In this case, the number 0 is represented by the 0-ary zero function \(\operatorname{n}()\).
So far, we have seen how we can build up some of the most basic arithmetic functions from the successor function, the zero function, composition, and a simple form of recursion. However, we are still unable to build polynomial functions such as \(q(x,y) = x^2 + y\). Having projections functions will solve the problem: \begin{eqnarray*} u_i^n (x_1,\ldots,x_n) = x_i~~~~1 \leq i \leq n. \end{eqnarray*} Then \[q(x,y) = f(h( u_1^2(x,y), u_1^2(x,y)), u_2^2(x,y))\] since \(u_1^2(x,y) = x\) and \(u_2^2(x,y) = y\). Note that with projection functions, we do not really need zero functions with more than one argument. We can just take the zero function with one argument (\(\operatorname{n}(x) = 0\)) and compose with a projection function.
The projection functions, the zero function, and the successor functions are called initial functions. Starting from these initial functions, we can build many nontrivial functions using composition and (primitive) recursion. More formally, we have the following:
The class of primitive recursive functions is the smallest class of functions
containing the initial functions \begin{eqnarray*} \operatorname{n}(x_1,\ldots,x_n) & = & 0 \\ s(x) & = & x+1 \\ u_i^n(x_1,\ldots,x_n) & = & x_i~~~(1\leq i \leq n) \end{eqnarray*}
closed under composition; that is, given primitive recursive functions \(g_1,\ldots,g_m : \mathbb{N}^n \rightarrow \mathbb{N}\) and \(h : \mathbb{N}^m \rightarrow \mathbb{N}\), the function \[f(x_1,\ldots,x_n) = h(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n)\] is again primitive recursive
closed under primitive recursion; that is, given primitive recursive functions \(g : \mathbb{N}^{n-1} \rightarrow \mathbb{N}\) and \(h : \mathbb{N}^{n+1} \rightarrow \mathbb{N}\), the function defined by \begin{eqnarray*} f(x_1,\ldots,x_{n-1},0) & = & g(x_1,\ldots,x_{n-1}) \\ f(x_1,\ldots,x_{n-1},y+1) & = & h(x_1,\ldots,x_{n-1},y,f(x_1,\ldots,x_{n-1},y)) \end{eqnarray*}
We will see from the textbook that a primitive recursive function can be obtained from the initial functions by a finite number of applications of composition and primitive recursion.
A proof that the equations for primitive recursion define a unique function \(f\) can be found in Section 3.7 in Cohen's Computability and Logic.
Note that the schema for primitive recursion as stated above seems somewhat restrictive. For example, it does not immediately let us write the recursive definition for addition as we have done for \(f\) above. Fortunately, once certain shortcuts are established, certain amount of sloppiness can be tolerated.
Given a primitive recursive function \(g(x_1,\ldots,x_{n},y)\), it is not difficult to show that \[f(x_1,\ldots,x_n, k) = \sum_{i = 0}^k g(x_1,\ldots,x_{n-1}, i)\] and \[f(x_1,\ldots,x_n, k) = \prod_{i = 0}^k g(x_1,\ldots,x_{n-1}, i)\] are primitive recursive
The class of primitive recursive functions seem quite simple. Even so, we will later see that primality testing can be shown primitive recursive. To facilitate defining functions involving conditionals, we will work with predicates.
A predicate on \(\mathbb{N}^n\) is simply a function \(P : \mathbb{N}^n \rightarrow \{0,1\}\). We can think of the value \(1\) as true and \(0\) as false. Thus, \(P(x_1,\ldots,x_n)\) is either true or false, depending on the values of \(x_1,\ldots,x_n\). (We omit writing “on \(\mathbb{N}^n\)” from now on unless we need to work in more general contexts.)
Predicates are often used in specifying sets. For example, for the predicate \[ P(x_1,x_2) = \left \{ \begin{array}{ll} 1 & \text{ if } x_1 = x_2 \\ 0 & \text{ otherwise, }\end{array} \right. \] \(\{ (x_1,x_2) \in \mathbb{N}^2 \mid P(x_1,x_2)\}\) is the set \(\{ (a,a) \mid a \in \mathbb{N}\} \).
A primitive recursive predicate is a predicate that is primitive recursive as a function. In other words, primitive recursive predicates are simply primitive recursive binary functions.
The predicate \[Pos(x) = \left \{ \begin{array}{ll} 1 & \text{ if } x \gt 0 \\ 0 & \text{ otherwise} \end{array}\right.\] is primitive recursive because it can be defined recursively: \begin{eqnarray*} Pos(0) & = & 0 \\ Pos(y+1) & = & 1. \\ \end{eqnarray*}
\(AtLeast(x_1, x_2) = 1~\dot{-}~ (x_2 ~\dot{-}~ x_1) \) is primitive recursive. Note that \(AtLeast(x_1,x_2) = 1\) if and only if \(x_1 \geq x_2\).
\(Eq(x_1, x_2) = AtLeast(x_1,x_2) \cdot AtLeast(x_2,x_1)\) is primitive recursive. Note that \(Eq(x_1,x_2) = 1\) if and only if \(x_1 = x_2\).
\(\min(x,y)\) is primitive recursive since \[ \min(x,y) = y \cdot AtLeast(x,y) + x \cdot (1~\dot{-}~AtLeast(x,y))\]
More complex predicates can be built from simpler ones by logical connectives. For example, if \(P\) and \(Q\) are predicates, \(\neg P\) is true if and only if \(P\) is false; \(P \& Q\) is true if and only if both \(P\) and \(Q\) are true; \(P \vee Q\) is false if and only if both \(P\) and \(Q\) are false.
It is easy to check that if \(P\) and \(Q\) are primitive recursive predicates, so are \(\neg P\), \(P \& Q\), and \(P \vee Q\).
Let \(P_1,\ldots, P_k\) be mutually exclusive predicates on \(\mathbb{N}^n\); i.e. for all \(i \neq j\), \(P_i\) and \(P_j\) do not hold for the same tuple. Let \(g_1,\ldots, g_{k+1} : \mathbb{N}^n \rightarrow \mathbb{N}\) be primitive recursive functions. Then the function \(f:\mathbb{N}^n \rightarrow \mathbb{N}\) given by \[f(x_1,\ldots,x_n) = \left \{ \begin{array}{ll} g_1(x_1,\ldots,x_n) & \textbf{ if } P_1(x_1,\ldots,x_n) \\ g_2(x_1,\ldots,x_n) & \textbf{ if } P_2(x_1,\ldots,x_n) \\ \vdots & \vdots \\ g_k(x_1,\ldots,x_n) & \textbf{ if } P_k(x_1,\ldots,x_n) \\ g_{k+1}(x_1,\ldots,x_n) & \textbf{ otherwise } \end{array}\right. \] is primitive recursive. This is easy to see because \(f\) is given by \[\sum_{i = 1}^k P_i(x_1,\ldots, x_n) g_i(x_1,\ldots,x_n) + \left(\prod_{i=1}^k \left(1-P_i(x_1,\ldots, x_n)\right)\right) g_{k+1}(x_1,\ldots,x_n).\] In the case when \(k = 1\), it is sometimes more expressive to use the syntax \begin{eqnarray*} f(x_1,\ldots,x_n) & = & \textbf{if } P_1(x_1,\ldots, x_n) \textbf{ then } g_1(x_1,\ldots,x_n) \\ & & \textbf{else } g_2(x_1,\ldots,x_n). \end{eqnarray*} This syntax should be familiar to those who know Haskell or F#.
We now see that natural number division is primitive recursive. In particular, we define two functions: \(Quo(n,d)\) gives the quotient of \(n\) divided by \(d\) and \(Rem(n,d)\) gives the remainder of \(n\) divided by \(d\).
One can show that the predicate \(Div(n,d)=1\) if and only if \(d\) divides \(n\) is primitive recursive. Then \[Rem(n,d) = \sum_{i = 0}^{d-1} i\cdot Div(n-i,d)\] is therefore primitive recursive.
Then \[Quo(n,d) = \sum_{i = 0}^{n-1} Pos( (n~\dot{-}~(i+1)\cdot d)\] is therefore primitive recursive. Thus, \[Rem(n,d) = n- d\cdot Quo(n,d)\] is also primitive recursive.
The definition of primitive recursion seems a bit restrictive. We now look at another form of recursive definition that also defines primitive recursive functions. Consider the schema \begin{eqnarray*} f(x,0) & = & g(x) \\ f(x,y+1) & = & f(h(x,y),y) \\ \end{eqnarray*}
We will show that there is a unique primitive recursive function satisfying the above recursive definition.
To get a handle on what we need to accomplish, we list the function values for a few values of the second argument: \begin{eqnarray*} f(x,1) & = & f(h(x,0),0) = g(h(x,0)) \\ f(x,2) & = & f(h(x,1),1) = g(h(h(x,1),0)) \\ f(x,3) & = & f(h(x,2),2) = g(h(h(h(x,2),1),0)) \end{eqnarray*}
So we need a way to handle the iterated nestings of \(h\). We introduce an auxiliary function that uses a “counter” to keep track of the number of nestings as well as the second argument that needs to go into \(h\). To this end, define \begin{eqnarray*} P(x,y,0) & = & x \\ P(x,y,n+1) & = & h(P(x, y, n), y ~\dot{-}~(n+1)) \end{eqnarray*}
Claim: \[P(x,y+1,n+1) = P(h(x,y), y, n) \] for all \(x,y \in \mathbb{N}\) with \(y \leq n\).
Once the claim is established, we will see that setting \[f(x,y) = g(P(x,y,y))\] gives us what we want.
We prove the claim by induction on \(n\).
When \(n = 0\), the only value \(y \leq n\) is \(y = 0\). Then, \(P(x,y+1,n+1) = P(x,1,1) = h(P(x,1,0), 0) = h(x,0)\). But \(P(h(x,y), y, n) = P(h(x,0), 0, 0) = h(x,0)\). Hence, the statement holds for \(n = 0\).
Suppose that the statement holds for all \(n = 0,\ldots, N\) where \(N \in \mathbb{N}\).
Consider \(P(x,y+1,N+2)\) with \(y \leq N+1\). Note that \begin{eqnarray*} P(x,y+1,N+2) & = & h(P(x,y+1, N+1), y+1~\dot{-}~(N+2)) \\ & = & h(P(x,y+1, N+1), y~\dot{-}~(N+1)) \\ & = & h(P(x,y+1, N+1), 0) \\ & = & h(P(h(x,y),y, N), 0) ~~\text{ by the induction hypothesis}\\ \end{eqnarray*}
But \begin{eqnarray*} P(h(x,y), y, N+1) & = & h(P(h(x,y) ,y,N), y~\dot{-}~(N+1)) \\ & = & h(P(h(x,y) ,y,N), 0) \end{eqnarray*}
Hence, \( P(x,y+1,N+2) = P(h(x,y),y,N+1)\). Thus, the statement holds for \(n = N+1\). This completes the induction.
Note that setting \(f(x,y) = g(P(x,y,y))\), we have \begin{eqnarray*} f(x,0) & = & P(x,0,0) = g(x) \\ f(x,y+1) & = & g(P(x,y+1,y+1)) = g( P( h(x,y) ,y,y)) = f(h(x,y), y) \end{eqnarray*} Hence, \(f\) satisfies the recursive definition, thus establishing the existence of a primitive recursive function satisfying the recursive definition.
We now establish uniqueness. Suppose that \(f'\) is another primitive recursive function satisfying the recursive definition. It is easily shown by induction on \(y\) that \(f(x,y) = f'(x,y)\) for all \(x \in \mathbb{N}\).
There are many schemata of recursive definitions that also define primitive recursive functions. The interested reader is referred to Recursive Functions by Rósza Péter.