User:IssaRice/Computability and logic/Characteristic function of a semirecursive set

By definition, the characteristic function of a recursive set is recursive (and total). However, semirecursive sets are defined in terms of recursive relations without using the characteristic function terminology. This raises the question of how to phrase semirecursive relations in terms of characteristic functions.

What if we try to define a characteristic function for a semirecursive relation $S$ as follows?

${\chi }_S(x,y)=\{\begin{array}{cc}1& S(x,y)\\ 0& \mathrm{\neg }S(x,y)\end{array}$

Actually we should distinguish between different levels of badness of ${\chi }_S$, and ask separately if it is well-defined, total, and recursive.

First, given any $x$ and $y$, exactly one of $S(x,y)$ or $\mathrm{\neg }S(x,y)$ holds. So it seems ${\chi }_S$ is well-defined. Also in each case, we assign some number to ${\chi }_S(x,y)$, so it is total.

Since $S$ is semirecursive, there is some recursive relation $R$ such that $S(x,y)⟺\mathrm{\exists }t(R(x,y,t))$. And since $R$ is recursive, it has a recursive total characteristic function ${\chi }_R$. Our goal, then, is to try to define ${\chi }_S$ in terms of ${\chi }_R$. A first attempt is to define $g$ as follows:

$g(x,y)=\mu t[{\chi }_{\mathrm{\neg }R}(x,y,t)=0](x,y)=\mathrm{M}\mathrm{n}[{\chi }_{\mathrm{\neg }R}](x,y)$

The problem is that $g$ is only a semicharacteristic function. And it seems there is no way to get a characteristic function for $S$ using the processes for defining recursive functions. (Can we prove this? We shouldn't be able to prove it in general, because recursive sets are semirecursive!)

Semicharacteristic function

• see exercise 8.3 in Boolos, Burgess, Jeffrey.