The result of substituting recursive total functions in a recursive relation.

Question

In the book Computability and Logic by Boolos, Burgess and Jeffrey it defines a recursive function as follows:

The functions that can be obtained from the basic functions $z, s, id^i_n$ by the processes $Cn, Pr$, and $Mn$ are called the recursive (total or partial) functions. (In the literature, ‘recursive function’ is often used to mean more specifically ‘recursive total function’, and ‘partial recursive function’ is then used to mean ‘recursive total or partial function’.)

It also defines a characteristic function for a relation $R$ to be a $k$-argument relation that takes the value $1$ for a $k$-tuple if the relation holds of that $k$-tuple, and the value $0$ if it does not.

It then defines a relation to be recursive if its characteristic function is recursive. (So I'm assuming recursive in the sense of including either a total or partial function).

Given the background, here's my question: (This is in page 75 of the book)

Given a relation $R(y_1,\dots,y_m)$ and total functions $f_1(x_1,...,x_n),\dots, f_m(x_1,\dots, x_n)$, the relation defined by substitution of the $f_i$ in $R$ is the relation $R^*(x_1,\dots, x_n) $ that holds of $x_1,\dots,x_n$ if and only if $R$ holds of $f_1(x_1,\dots,x_n),\dots, f_m(x_1,\dots,x_n)$, or in symbols,

$R^∗(x_1,\dots,x_n)\leftrightarrow R(f_1(x_1,\dots,x_n),\dots, f_m(x_1,\dots,x_n))$

If the relation $R^∗$ is thus obtained by substituting functions $f_i$ in the relation $R$, then the characteristic function $c^∗$ of $R^∗$ is obtainable by composition from the $f_i$ and the characteristic function $c$ of $R$:

$c^∗(x_1,\dots,x_n)=c(f_1(x_1,\dots,x_n),\dots, f_m(x_1,\dots,x_n)).$

Therefore, the result of substituting recursive total functions in a recursive relation is itself a recursive relation. (Note that it is important here that the functions be $\underline{total}$.)

Why is it important that the functions be total?

Thoughts: So is the only reason why it has to be total is because a characteristic function by definition has to return $1$ if $(x_1,\cdots,x_n)$ holds in $R$ and $0$ if $(x_1,\cdots,x_n)$ does not hold in $R$? So if the $f_i$ weren't total then $c^*$ wouldn't necessarily be total. Is this the only reason or is there something else going on?

Answer 1

You've basically got it right - restricting to arity 1 for simplicity, if $f$ isn't total then neither is $c\circ f$, so $c\circ f$ isn't the characteristic function of any relation (let alone a recursive one).

There's a bit more to be said, though. There are a bunch of ways we could try to define a relation gotten from $R$ (with characteristic function $c$) by substitution with a non-total function $f$: for instance, say $R_f(x)$ holds if

• $f(x)$ is defined, and

• $R(f(x))$ holds.

This is now a well-defined relation (well, set); however, even if $f$ and $R$ are recursive, $R_f$ may not be! This could happen because telling that $f(x)$ is defined is a c.e. (or r.e.) event: you can't computably tell that $f(x)$ isn't defined, in general.

And in fact there's no way to fix this:

There is a recursive relation $R$ and a recursive (partial!) $f$ such that no recursive relation $S$ has the property: "$f(x)$ defined implies $S(x)\iff R(f(x))$."

Proof: let $R$ be =, let $\{\Phi_e: e\in\omega\}$ be some standard enumeration of Turing machines, and let $f$ be a recursive partial function satisfying:

• $f(2k)=2k$ for every $k$,

• If $\Phi_e(e)\downarrow=1$, then $f(2e+1)=2e+1$, and

• If $\Phi_e(e)\downarrow = 0$, then $f(2e+1)=2e$.

If such a recursive $S$ existed, then the characteristic function of the set $D=\{e: \langle 2e, 2e+1\rangle\in S\}$ will be recursive - say, with characteristic function $\Phi_c$. But then $$c\in D\iff \Phi_c(c)\downarrow=1\implies c\not\in D$$ and $$c\not\in D\iff\Phi_c(c)\downarrow=0\implies c\in D$$ . . . Oops.