(Notes from Chapter 3, Sections 4 - 6 plus more)
The following is a list of primitive recursive functions.
\(x + y\) (addition)
\(x \cdot y\) (multiplication)
\(x^y\) (exponentiation)
\(x!\)
\(p(x)\), the predecessor function, can be defined using primitive recursion: \begin{eqnarray*} p(0) & = & 0 \\ p(t+1) & = & t \end{eqnarray*}
\(x~\dot{-}~y\) (truncated subtraction)
\(\lvert x - y \rvert\)
\(\operatorname{sg}(x) = \left\{\begin{array}{ll} 0 & \text{if } x = 0, \\ 1 & \text{otherwise.} \end{array}\right.\) (signum function)
Proof. The function can be defined using primitive recursion: \begin{eqnarray*} \operatorname{sg}(0) = 0 \\ \operatorname{sg}(x+1) = 1 \end{eqnarray*}
\(\overline{\operatorname{sg}}(x) = \left\{\begin{array}{ll} 1 & \text{if } x = 0, \\ 0 & \text{otherwise.} \end{array}\right.\) (denoted \(\alpha(x)\) in the textbook)
\(\min(x,y)\) (the minimum of \(x\) and \(y\))
Proof. \(\min(x,y) = x~\dot{-}~(x~\dot{-}y)\)
\(\max(x,y)\) (the maximum of \(x\) and \(y\))
\(\operatorname{rem}(x,y)\) (the reminder of \(y\) divided by \(x\) with the convention that \(\operatorname{rem}(0,y) = y\))
Proof. The function can be defined using primitive recursion: \begin{eqnarray*} \operatorname{rem}(x,0) & = & 0 \\ \operatorname{rem}(x,t+1) & = & (\operatorname{rem}(x,t) + 1)\operatorname{sg}( \lvert x - (\operatorname{rem}(x,t) + 1)\rvert ). \\ \end{eqnarray*}
\(\operatorname{quo}(x,y)\) (the quotient of \(y\) divided by \(x\) with the convention that \(\operatorname{quo}(0,y) = 0\))
Proof. The function can be defined using primitive recursion: \begin{eqnarray*} \operatorname{quo}(x,0) & = & 0 \\ \operatorname{quo}(x,t+1) & = & \operatorname{quo}(x,t) + \overline{\operatorname{sg}}( \lvert x - (\operatorname{rem}(x,t) + 1)\rvert ). \\ \end{eqnarray*}
For our purposes, a predicate on \(\mathbb{N}^n\) is a Boolean-valued total function.
Theorem 5.1. Let \({\cal C}\) be a PRC class. If \(P,Q\) are predicates that belong to \({\cal C}\), then so are \(\neg P\), \(P \vee Q\), and \(P \& Q\).
Corollary 5.2. If \(P,Q\) are primitive recursive predicates, then so are \(\neg P\), \(P \vee Q\), and \(P \& Q\).
Corollary 5.3. If \(P,Q\) are computable predicates, then so are \(\neg P\), \(P \vee Q\), and \(P \& Q\).
Recall that a computable predicate is a predicate such that there exists a program that computes it and halts on all inputs.
All of the following are primitive recursive predicates:
\(x = y\) is given by \(\overline{sg}(\lvert x - y \rvert)\).
\(x \leq y\) is given by \(\overline{sg}(x~\dot{-}~ y)\).
\(x \lt y\) is given by \((x \leq y)~\&~\neg (x = y)\).
Theorem 5.4 (Definition by Cases). Let \({\cal C}\) be a PRC class. Let the functions \(g,h\) and the predicate \(P\) belong to \({\cal C}\). Let \[f(x_1,\ldots,x_n) = \left\{ \begin{array}{ll} g(x_1,\ldots,x_n) & \text{if } P(x_1,\ldots,x_n) \\ h(x_1,\ldots,x_n) & \text{otherwise}. \end{array} \right.\] Then \(f\) belongs to \({\cal C}\).
Corollary 5.5. Let \({\cal C}\) be a PRC class. Let \(n\)-ary functions \(g_1,\ldots,g_m,h\) and predicates \(P_1,\ldots,P_m\) belong to \({\cal C}\). Let \[P_i(x_1,\ldots,x_n)~\&~P_j(x_1,\ldots,x_m) = 0\] for all \(1\leq i \lt j \leq m\) and all \(x_1,\ldots,x_n \in \mathbb{N}\). If \[f(x_1,\ldots,x_n) = \left\{ \begin{array}{ll} g_1(x_1,\ldots,x_n) & \text{if } P_1(x_1,\ldots,x_n) \\ ~~~~~~\vdots & ~~~~~~\vdots \\ g_m(x_1,\ldots,x_n) & \text{if } P_m(x_1,\ldots,x_n) \\ h(x_1,\ldots,x_n) & \text{otherwise}, \end{array} \right.\] then \(f\) belongs to \({\cal C}\).
Theorem 6.1. Let \({\cal C}\) be a PRC class. If \(f(t,x_1,\ldots,x_n)\) belongs to \({\cal C}\), then so do the functions \[ g(y,x_1,\ldots,x_n) = \sum_{t=0}^y f(t,x_1,\ldots,x_n)\] and \[ h(y,x_1,\ldots,x_n) = \prod_{t=0}^y f(t,x_1,\ldots,x_n).\]
Corollary 6.2. Let \({\cal C}\) be a PRC class. If \(f(t,x_1,\ldots,x_n)\) belongs to \({\cal C}\), then so do the functions \[ g(y,x_1,\ldots,x_n) = \sum_{t=1}^y f(t,x_1,\ldots,x_n)\] and \[ h(y,x_1,\ldots,x_n) = \prod_{t=1}^y f(t,x_1,\ldots,x_n).\] (Note that a vacuous sum is defined to be 0 and a vacuous product is defined to be 1.)
Theorem 6.3. If the predicate \(P(t,x_1,\ldots,x_n)\) belongs to some PRC class \({\cal C}\), then so do the predicates \[ (\forall t)_{\leq y} P(t,x_1,\ldots,x_n)~~~~~~\text{and}~~~~~ (\exists t)_{\leq y} P(t,x_1,\ldots,x_n). \]
All of the following are primitive recursive predicates:
\(y \mid x\) is given by \((\exists t)_{\leq x} (y\cdot t = x)\).
\(\operatorname{Prime}(x)\) is given by \((x \geq 2)~\&~ (\forall t)_{\leq x} (t =1 \vee t =x \vee \neg (t \mid x)).\)