(Notes from Chapter 3, Sections 7 - 8 plus more)
Let \(P(x_1,\ldots,x_n,t)\) be a predicate that belongs to some given PRC class \({\cal C}\). Then by Theorem 6.1, the function \[ g(x_1,\ldots,x_n,y) = \sum_{u=0}^y \prod_{t=0}^u \alpha(P(x_1,\ldots, x_n,t))\] also belongs to \({\cal C}\).
Recall that \(\alpha(x) = \left\{\begin{array}{ll} 1 & \text{if } x = 0 \\ 0 & \text{otherwise}\end{array}\right. \).
Define \[\min_{t \leq y} P(x_1,\ldots,x_n,t) = \left \{ \begin{array}{ll} g(x_1,\ldots,x_n,y) & \text{if } (\exists t)_{\leq y} P(x_1,\ldots,x_n,t) \\ 0 & \text{otherwise }. \end{array} \right.\] Then \(\displaystyle\min_{t \leq y} P(x_1,\ldots,x_n,t)\) is the least value of \(t \leq y\) for which \(P(x_1,\ldots,x_n,t)\) holds if such exists; otherwise, it takes the value \(0\).
Remarks. Some books use \(y+1\) instead of \(0\) in the definition above. When \(0\) is the function value, one needs to check again if \(P(x_1,\ldots,x_n,0)\) holds to determine if \(0\) is a minimizer. Some books use the notation \(\mu t_{\leq y} P(x_1,\ldots,x_n,t)\) or \(\mu t \leq y~ P(x_1,\ldots,x_n,t)\) instead.
Theorem 7.1 If \(P(x_1,\ldots,x_n,t)\) belongs to some PRC class \({\cal C}\) and \(f(x_1,\ldots,x_n,y) = \min_{t \leq y} P(x_1\ldots,x_n,t)\), then \(f\) also belongs to \({\cal C}\).
We say that \(f\) is obtained by bounded minimization on \(P\).
\(\left\lfloor \frac{x}{y} \right\rfloor\) is given by \[ \min_{t \leq x} (t+1)\cdot y \gt x. \] Note that \(\left\lfloor \frac{x}{y} \right\rfloor\) is also given by \(\operatorname{quo}(y,x)\) from before. Note that \(\left\lfloor \frac{x}{0} \right \rfloor = 0\).
\(R(x,y)\), the remainder of \(x\) divided by \(y\), is given by \[R(x,y) = x~\dot{-}~\left(y \cdot \left \lfloor \frac{x}{y} \right \rfloor \right).\] Note that \(R(x,0) = x\).
\(p_n\), the \(n\)th prime with \(p_0 = 0\), \(p_1 = 2,\ldots,\) is given by \begin{eqnarray*} p_0 & = & 0 \\ p_{n+1} & = & \min_{t \leq p_n ! + 1} (\operatorname{Prime}(t) ~\&~t \gt p_n). \end{eqnarray*}
Sometimes, bounded minimization is defined in terms of a given function \(f(x_1,\ldots,x_n,t)\) on the predicate \(f(x_1,\ldots,x_n,t) = 0\):
If \(f(x_1,\ldots,x_n,t)\) belongs to some given PRC class \({\cal C}\), then \(g(x_1,\ldots,x_n,y) = \min_{t \leq y} (f(x_1\ldots,x_n,t) = 0)\) also belongs to \({\cal C}\). We say that \(g\) is obtained by bounded minimization on \(f\).
The textbook does not make the above definition but it will actually be needed and is defined in other books.
\[\min_{y} P(x_1,\ldots,x_n,y)\] is the least value of \(y\) for which the predicate \(P\) holds if such exists. Otherwise, it is undefined.
For example, \[ x - y = \min_z (y + z = x)\] is undefined for \(x \lt y\).
Theorem 7.2 If \(P(x_1,\ldots,x_n,y)\) is a computable predicate and if \[g(x_1,\ldots,x_n) = \min_y P(x_1,\ldots,x_n,y),\] then \(g\) is partially computable.
We say \(g\) is obtained from the predicate \(P\) via minimization or \(\mu\)-recursion. Some books use the notation \[g(x_1,\ldots,x_n) = \mu y~P(x_1,\ldots,x_n,y).\]
Given a partially computable function \(f(x_1,\ldots,x_n,y)\), define \[\min_y~(f(x_1,\ldots,x_n,y) = 0)\] to be the least \(y\) such that \(f(x_1,\ldots,x_n,z)\) is defined for all \(z \leq y\) and \(f(x_1,\ldots,x_n,y) = 0\), if such \(y\) exists; otherwise undefined.
Theorem 7.2' The function \[g(x_1,\ldots,x_n) = \min_y (f(x_1,\ldots,x_n,y) = 0)\] is partially computable.
Proof. The following program compute \(g\): \[ \begin{array}{ll} [A] & \textbf{if } f(X_1,\ldots,X_n,Y) = 0 \textbf{ goto } E \\ & Y\leftarrow Y+1 \\ & \textbf{goto } A \end{array} \]
Note that without the requirement that \(f(x_1,\ldots,x_n,z)\) be defined for all \(z \leq y\), the proof above is invalid.
We say \(g\) is obtained from \(f\) via minimization or \(\mu\)-recursion. Some books use the notation \[g(x_1,\ldots,x_n) = \mu y~(f(x_1,\ldots,x_n,y) = 0).\]
Define the primitive recursive function \[\langle x, y \rangle = 2^x (2y + 1) ~\dot{-}~ 1.\]
Note that \(\langle \cdot , \cdot \rangle\) is a bijection between \(\mathbb{N}\times \mathbb{N}\) and \(\mathbb{N}\).
Define \[l(z) = \min_{x\leq z} [ (\exists y)_{\leq z} (z = \langle x, y \rangle) ],\] and \[r(z) = \min_{y\leq z} [ (\exists x)_{\leq z} (z = \langle x, y \rangle) ].\] Then \(l(z)\) and \(r(z)\) are primitive recursive functions.
Theorem 8.1 (Pairing Function Theorem) The functions \(\langle x,y \rangle\), \(l(z)\), and \(r(z)\) are primitive recursive functions satisfying:
\(l(\langle x,y\rangle) = x\);
\(r(\langle x,y\rangle) = y\);
\(\langle l(z),r(z)\rangle) = z\);
\(l(z),r(z)\leq z\).
The Gödel Number of the sequence \((a_1,\ldots,a_n)\), denoted \([a_1,\ldots,a_n]\), is defined to be the number \[ \prod_{i=1}^n p_i^{a_i}.\]
For example, \([3,2,4,1] = 2^3 \cdot 3^2 \cdot 5^4 \cdot 7^1 = 315000\) is the Gödel number of the sequence \((3,2,4,1)\).
For each fixed \(n\), the function \([a_1,\ldots,a_n]\) is primitive recursive.
Theorem 8.2 If \([a_1,\ldots,a_n] = [b_1,\ldots,b_n]\), then \[a_i = b_i,~~~~~~i = 1,\ldots,n.\]
An artifact of this definition is that \([a_1,\ldots,a_n] = [a_1,\ldots,a_n,0]\). In other words, adjoining zeros to the right of a sequence does not alter the Gödel number. To allow sequences to terminate with zeros, some books define \([a_1,\ldots,a_n]\) to be \(\displaystyle\prod_{i=1}^n p_i^{a_i+1}\). The textbook simply allows a bit of ambiguity.
The number 1 is the Gödel number of the empty sequence, denoted \([]\).
Define the primitive recusive function \((x)_i\) as follows: \[(x)_i = \min_{t \leq x} \neg (p_i^{t+1} \mid x).\]
Note that \((x)_0 = 0\) and \((0)_i = 0\) for all \(i\).
Clearly, if \(x = [a_1,\ldots,a_n]\), then \((x)_i = a_i\) for \(i = 1,\ldots, n\). If \(i \gt n\), then \((x)_i = 0\). In particular, \((x)_i = 0\) for all \(i \gt x\).
Define \(\operatorname{Lt}(x)\), the length of \(x\), as: \[ \operatorname{Lt}(x) = \min_{i \leq x}~((x)_i \neq 0~\&~(\forall j)_{\leq x} (j \leq i~\vee~(x)_j = 0)). \]
Note that \(\operatorname{Lt}(0) = \operatorname{Lt}(1) = 0\) and \(\operatorname{Lt}([a_1,\ldots,a_n]) = n\) iff \(a_n \neq 0\).
Theorem 8.3 (Sequence Number Theorem).
\(([a_1,\ldots,a_n])_i = \left\{ \begin{array}{ll} a_i & \text{if } 1 \leq i \leq n\\ 0 & \text{otherwise}. \end{array} \right.\)
\([(x)_1,\ldots,(x)_n] = x\) if \(n \geq \operatorname{Lt}(x)\).