Math 557 Nov 5
Definability of Computable Functions
We now extend the connection between arithmetical formulas and computable functions significantly. Our goal is to show that the recursive relations on \(\mathbb{N}\) are precisely those that are \(\Delta_1\)-definable. At the core of this connection is the Definability Theorem. For a partial function \(f\), let \(\Gamma_f\) denote the graph of \(f\), i.e., the relation \[ \Gamma_f(\vec{x},y): \iff f(\vec{x})=y. \]
The Definability Theorem
The direction (\(\Leftarrow\)) is relatively straightforward: Let \(\theta = \exists z \, \psi\) be a \(\Sigma_1\)-formula that defines the graph \(\Gamma_f\) of a partial function \(f\), where \(\psi(x, y, z)\) is a \(\Delta_0\)-formula. As \(\Delta_0\)-formulas define primitive recursive relations, we obtain a computable function \(g\) by letting
\[ g(x) = \mu z \, \psi( x, (z)_0, (z)_1). \]
Then \((g(x))_0\) is the smallest \(y\) with \(\mathbb{N} \models \theta[x, y]\), if such a \(y\) exists, and undefined otherwise, since for each \(x \in \mathbb{N}\) there is at most one \(y\) with \(\mathbb{N} \models \theta[x, y]\). Thus \((g(x))_0 \cong f(x)\), and therefore \(f\) is partial computable.
For the proof of (\(\Rightarrow\)), we call partial functions \(f\) whose graph can be defined by a \(\Sigma_1\)-formula over the natural numbers functions with a \(\Sigma_1\)-graph. The obvious strategy is to show that the set of these functions contains the initial functions and is closed under composition, primitive recursion, and the \(\mu\)-operator.
Most cases are straightforward (just by writing out the definitions), but when we get to closure under primitive recursion, we run into difficulties: Suppose the function \(f\) arises from functions \(g, h\) by primitive recursion:
\[ \begin{aligned} f(x, 0) &\cong g(x) \\ f(x, y+1) &\cong h(x, y, f(x, y)) \end{aligned} \]
We may assume that the graphs of \(g\) and \(h\) are definable by \(\Sigma_1\)-formulas. To describe the graph of \(f\) with this, we note that the value of \(f(x, y)\) is computed through the preceding values
\[ u_0 = f(x, 0), \, u_1 = f(x, 1), \, \ldots, \, u_y = f(x, y), \]
We somehow have to eliminate the function \(f\) from this sequence to obtain an explicit definition (in the language of arithmetic).
The idea is to express the following through a formula:
There exists a code \(u\) such that \(u\) codes a sequence of numbers \((u_0, \dots, u_y)\) in which the \(u_{i+1}\) is obtained from \(u_i\) using a valid application of the primitive recursion scheme with respect to \(g\) and \(h\).
The problem is that we do not know a priori how long the sequence coded by \(u\) is. We therefore cannot use the preferred coding scheme
\[ \langle u_0, \dots, u_y \rangle \]
which is \(\Delta_0\)-definable. The coding scheme \[ (n_0, n_1, \ldots, n_k) \quad \text{by} \quad p_0^{n_0+1} \cdot p_1^{n_1+1}\cdot \ldots \cdot p_k^{n_k+1}. \] on the other hand is uniform independent of the length of the sequence, but it uses exponentiation, which is not present in \(\mathsf{PA}^-\) (and would have to be defined via recursion).
This is where Gödel, according to Mostowski, “had a phone call with God”.
Gödel’s Lemma
Proof. Let \(x_0,x_1,\ldots x_{k-1}\) be a sequence of natural numbers.
Set \(m:=b!\) where \(b: = \max(k,x_0,x_1,\ldots x_{k-1})\). Then the sequence of numbers \[ m+1, 2m+1, \ldots k \cdot m+1 \] are pairwise coprime. By the theorem on simultaneous congruences (Chinese Remainder Theorem), there exists a natural number \(a\) with \[ a \equiv x_i \pmod{(i+1)m+1} \quad \text{for all } i < k. \] Now we can choose \(\langle a,m \rangle\) as a code for the sequence \(x_0,x_1,\ldots x_{k-1}\), because from this we can recover each \(x_i\) for every \(i<k\) as the remainder of the division of \(a\) by the number \((i+1)m+1\). If \(rem(x:y)= z\) denotes the remainder of the division of \(x\) by \(y\) (when \(y \ne 0\) and \(rem(x:0)=0\)), then this is a p.r. function with a \(\Delta_0\)-definition. We obtain another p.r. function by \[ \alpha(a,m,i) =rem(a: (1+i)m+1). \] Let \(p_1,p_2\) denote the inverse functions of the pairing function \(\langle x,y \rangle\) above, for which \[ \langle p_1(x),p_2(x) \rangle = x , \quad \text{where} \; p_1(x),p_2(x) \le x, \] these are also p.r., and we finally obtain the Gödel beta function as \[ \beta(c,i) = \alpha(p_1(c),p_2(c),i). \]
Completing the proof of the Definability Theorem
Returning to the sequence
\[ u_0 = f(x, 0), \, u_1 = f(x, 1), \, \ldots, \, u_y = f(x, y), \]
we can now use the \(\beta\)-function to encode this by a single number \(u\). The first value \(u_0\) is determined by the graph of \(g\), and the further values \(u_{i+1}\) are determined from \(u_i\) according to the recursion conditions via the graph of \(h\):
\[ \forall i < y \, \exists r, s \, [\beta(u, i) = r \wedge \beta(u, i+1) = s \wedge \Gamma_h(\vec{x}, i, r, s)] \]
This formula can be transformed (by choosing a sufficiently large \(w\)) into
\[ \exists w \, \forall i < y \, \exists r, s < w \, [\beta(u, i) = r \wedge \beta(u, i+1) = s \wedge \Gamma_h(\vec{x}, i, r, s)]. \]
The last value of the sequence encoded by \(u\) is the function value of \(f\) at the point \((x, y)\). Thus we obtain the following description of the graph of \(f\):
\[ \begin{aligned} \Gamma_f(\vec{x}, y, z) \iff \; & \exists u, v, w \, (\Gamma_g(\vec{x}, v) \wedge \beta(u, 0) = v \wedge \beta(u, y) = z \; \wedge \\ & \forall i < y \, \exists r, s < w \, [\beta(u, i) = r \wedge \beta(u, i+1) = s \wedge \Gamma_h(\vec{x}, i, r, s)]), \end{aligned} \]
It is not hard to transform this into an equivalent \(\Sigma_1\)-formula.
Characterization of the Arithmetic Hierarchy
If we call a set \(A \subseteq \mathbb{N}^k\) that is definable by a formula in \(\Gamma\) over the natural numbers a \(\Gamma\)-set, we obtain a new characterization of the first levels of the arithmetic hierarchy:
We leave the short proof of (1) as an exercise. (2) follows from (1) by using negation, and for (3) use the fact that a set is computable if and only if the st and its complement are r.e.