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

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?

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.

• Note that in the denouement there's nothing special about $R$ being =, we just need $R$ to have infinitely many classes. Jun 14, 2015 at 3:46
• I was just wondering, what's c.e and r.e? I'm guessing r.e is recursively enumerable? But I haven't got to that part of the book if this is the case. Jun 14, 2015 at 4:21
• C.e. and r.e. stand for "computably enumerable" and "recursively enumerable," respectively, and mean exactly the same thing (personally I prefer "c.e." but both are used frequently). My only point is that, if I'm trying to write an algorithm, I can't have steps like "If $\Phi_e(k)$ halts, then . . . otherwise, . . . ", since in general there is no way to know that a program won't halt (this is a fancy way of saying "the halting problem is non-computable"). Jun 14, 2015 at 4:44
• Sorry, I usually take at least 2 days to accept an answer. But before I accept I'd like to ask a few more questions in response to your edit. First of all, what does it mean to put $e$ into $\Phi_e$ if $\Phi_e$ is just some turing machine? How is it that you can put numbers in it? Also, I'm guessing $\omega$ has something to do with ordinals? Is this just the same as saying $e$ is a natural number? Second, what did you mean by the $\downarrow$? Sorry, I should have stated my background as part of the question! Jun 16, 2015 at 5:45
• If $\Phi_e$ is a Turing machine, and $n$ is a natural number, then $\Phi_e(n)$ - the machine $\Phi_e$ run on input $n$ - just refers to when you run $\Phi_e$ on a tape starting with $n$ consecutive 1s, and then all zeros after. That is, we think of a Turing machine as being a description of a partial computable/recursive function. (We could in principle start with something else written on the tape, but we don't care for now.) $\omega$ is just $\mathbb{N}$ (logicians tend to use "$\omega$" instead of "$\mathbb{N}$"). The "$\downarrow$" just means "halts" (or "converges," or "is defined," etc.) Jun 16, 2015 at 5:52