7. Recursive and Semi-Recursive Relations

Kevin T. Kelly
Department of Philosophy
Carnegie Mellon University

(Rogers chapter 5, Cutland Chapters 6, 7.)

The characteristic function Char_R for a k-ary relation R is a function f: N^k® 2 such that for all x,

R(x) Þ f(x) = 1 Ù ØR(x) Þf(x) = 0.
A verifying function for a relation R is a partial function f: N^k® 2 such that
R(x) Ûf(x) » 1.
A refuting function for a relation R is a partial function f: N^k® 2 such that
ØR(x) Ûf(x) » 1.
A computably decidable or recursive relation is a relation whose characteristic function is total recursive.
A computably verifiable or semi-recursive relation is a relation with a partial recursive verifying function.
A computably refutable or co-semi-recursive relation is a relation with a partial recursive refuting function.

The "computably decidable, verifiable, refutable" notation is not standard, but is much closer to the truth than the standard "recursive, semi-recursive" notation.

Examples:
computationally decidable: Godel numbers of valid formulas in a propositional language.
computationally verifiable: Godel numbers of valid formulas in the language of arithmetic.
computationally refutable: first-order consistancy in the language of arithmetic.
none of the above: the complete theory of arithmetic.

Arity and Clutter Reduction

From now on, we will drop the arity parameter when working with unary functions.

f[n] = f[n, 1].

We can handle k-ary functions and relations by using a k-ary coding function.

f[n, k](x) » f[m, k](<x>).
R(x) » S(<x>).

Exercise 1: Show that there is an effective conversion from index n to index m and conversely. That is, there exist total recursive f, g such that for all k-ary x,

f[n, k](x) » f[f(n)](<x>).
f[g(n), k](x) » f[n](<x>).

Big hint: use the universal construction to set up the application of an index to a coded sequence of arguments like this:

y(i, x) » d(mzU(i, d(z, 0), d(z, 1), <<x>>), 1).

Apply the s-m-n theorem and see what you get. For the other side, apply the universal construction in a manner that eliminates coding brackets instead of adding them. All the exercises will be like this. Get in the habit of casting for the "right" application of the universal construction and then applying s-m-n to the index position.

Alternate Characterizations of Verifiability

The following results and concepts must become second nature to you. Here is some standard, but curious notation:

W[n] = dom(f[n]).
E[n] = rng(f[n]).

Proposition 1: R is formally verifiable Û there exists an n, such that for all x,

R(x) ÛW[n](<x>).

Exercise 2. Prove it. Hint: Use a m operator to produce infinite loops in the right places and conversely, use sg to cut outputs higher than 1 down to 1.

You know from set theory that

A set is enumerable just in case there exists a bijection from N to the set (i.e., an enumeration).
A set is denumerable just in case it is enumerable or finite. This is equivalent to the existence of a surjection from N to the set.

What if we "motorize" the concept of enumerability, requiring that the enumeration be a total recursive function? Then we arrive at the concept of a recursively enumerable set:

S is recursively enumerable (r.e.) Û S = Æ Ú $ total recursive f,S = rng(f).

The following result says that this amounts to the same thing as computable verifiability.

Proposition 2 (fundamental theorem of r.e. sets):

S is r.e.

there exists an n such that S = W[n].

Proof: Suppose that S is r.e. If S = Æ, then S = dom(Æ). But Æ = the function defined by mz, x¹ x, and hence is partial recursive.

Now suppose that S ¹Æ. We must show that S = rng(f), where f is total recursive. Define:

y(x) = mz f(z) = x.

This is partial recursive since f is recursive. And S = dom(y).

Conversely, suppose that S = W[w] = dom(f[n]). If S = Æ, then we are done. So suppose S ¹Æ. So there is at least one k such that S(k). Now we need to produce a total recursive enumeration of S. We can't assume that W[w] is infinite, so perhaps at some point we run out of new things to enumerate. We must therefore continue to output some previously enumerated number until a new element of W[w] is detected.

f(0) = k;
f(n + 1) =
d(n, 2) if "z £ n, d(n, 2) ¹ f(z) Ù U(w, d(n, 0), d(n, 1), <d(n, 2)>)
f(n) otherwise.

This is a course of values recursion over partial recursive constructions and hence is partial recursive.

Corollary 3: The sequence

W[0], W[1], ..., W[n], ...

is an enumeration of the computably verifiable sets.

The corollary is central to the theory of computability. It provides a way of using our effective numbering of Part to number the verifiable sets without having to do it again from scratch. According to the following result, there is an equivalent, effectively intercompilable enumeration based on ranges instead of domains.

Proposition 4: Effective conversions between domains and ranges.

$ total recursive f "nW[n] = E[f(n)].
$ total recursive g "nW[g(n)] = E[n].

Exercise 3: Prove it. Hint: use the s-m-n theorem over a universal dovetailing construction analogous to the one given in the preceding exercise. Good practice in doing things the elegant, formally valid way!

Corollary 5: The sequence

E[0], E[1], ..., E[n], ...

is also an enumeration of the computably verifiable sets.

Recall that the primitive recursive relations are closed under bounded existential quantification. The computably verifiable relations are closed under full existential quantification over N. And every partial recursive relation results from an unbounded existential quantification over a (primitive) recursive relation.

Proposition 5 (the projection theorem): S is computably verifiable Û $elementary [r.e.] R such that "x

S(x) Û $yR(x, y).

Proof: Let S be computably verifiable. By the fundamental theorem of r.e. sets, $nS = W[n]. Thus, for all x,

S(x) ÛW[n](x) ) Ûf[n](x)¯ Û $zU(n, d(z, 0), d(z, 1), <x>).

Recall that a U is elementary.
Conversely, suppose

S(x) Û$zR(z, x),

where R is r.e. So for some n, R(<z, x>) = W[n](<z, x>). Define

y(x) »mwU(n, d(w, 0), d(w, 1), <d(w, 2), x>).

This is partial recursive, so for some m,

f[m] = y.

Now

W[m](x) Û
f[m](x)¯Û
y(x)¯Û
mwU(n, d(w, 0), d(w, 1), <d(w, 2), x>) Û
$wU(n, d(w, 0), d(w, 1), <d(w, 2), x>) Û
$z f[n](<z, x>)¯ Û
$z W[n](<z, x>) Û
$zR(z, x) Û
S(x)

So S is r.e.

Corollary 6 (Summary): The following are equivalent:

S is computably verifiable;
S is r.e.;
$nS = E[n];
$nS = W[n];
$ elementary [recursive, r.e.] R such that "xS(x) Û$y R(x, y).

The Halting Problem

What can we do with the W[n] notation? Well, by Corollary 6, we have a nice, effective enumeration of the computationally verifiable sets. Thus, we can form A two-dimensional table of zeros and ones as follows:

T[n, m] = Char_W[n](m).

Thus, each row of the table is the characteristic function of a computably verifiable set and the characterisitic function of each computably verifiable set occurs at least once in the table (infinitely often, actually).
Now define the set K whose characteristic function is the diagonal of the table:

Char_K (n) = T[n, n] = Char_W[n](n).

Then the characteristic function of ØK is the counter-diagonal of the table:

Char_ØK (n) = -sg(T[n, n]) = -sg(Char_W[n](n)).

Evidently, ØK is not a computably verifiable set, since its characteristic function is concocted to differ from each row of the table along the diagonal. Thus:

Proposition 7: ØK is not r.e.

Notice that the proof of proposition 7 is almost the same as Cantor's argument that the power set of N is not enumerable. The difference is that in Cantor's argument, we now that the diagonal characteristic function yields a subset of N so the enumeration assumption is rejected. In this case, we know from the fundamental theorem of r.e. sets that the effective enumeration W[0], W[1], ... exists, so the diagonal characteristic function yields a non-r.e. set.

Unwinding the definition of K we have:

K(n) Û
Char_W[n](n) = 1 Û
W[n](n) Û
n Î dom(f[n]) Û
f[n](n)¯.

Thus, K is the set of all indices that return an output or "halt" when given themselves as input. For this reason, K is called the halting problem.

Alternate Characterizations of the Recursive Sets

Decision intuitively requires that one be able to verify whether yes and verify whether no.

Proposition 8: S is recursive Û S, ØS are both r.e.

Exercise 4: Prove it. Hint: One way is immediate using results proved above. The other requires a nice dovetailing construction, because you don't want to commit a suki by focusing on S forever before checking ØS.But you can count on one or the other halting because each number is either in S or ØS.

Corollary 9: K,ØK are not recursive.

The next result is very interesting because it links the straightforwardly epistemological concept of decidability with the function theoretic concept of monotonicity. The idea is that you can use a monotone enumeration to decide the set: once you see a bigger thing than what you are looking for, you know you won't ever find what you are looking for. Conversely, if you can decide, a set, then you can make sure that nothing smaller than x will have to be added to the enumeration before you add x. Compare this with the fundamental theorem for r.e. sets. In that case, you can't

Proposition 10: S is recursive ÛS is finite Ú $ monotone, total recursive f. S = rng(f).

Proof: Suppose S is recursive. If S is finite, we are done. So suppose that S is infinite. Define

f(0) = mx Char_S(x) = 1.
f(n + 1) = mx [Char_S(x) = 1 Ù "z £ n, f(n) ¹x].

Conversely, suppose that S is finite. Then a case definition (using one case per element) yields a program for the characteristic function of S, so S is primitive recursive, and hence recursive.

Finally, suppose that S is the range of monotone, total recursive f.

Exercise 5: complete the proof. Hint: refer to the intuitive motivation above.

Closure Laws

These will be very important for hierarchy theory.

Proposition 11:

The r.e. sets form a Boolean algebra that is also closed under unbounded existential quantification.
The recursive sets form a Boolean algebra.
The recursive and r.e. relations are both closed under Cartesian product ´.

Exercise 6: Prove it. Hint: For a Boolean algebra it suffices to show closure under Ù, Ø. The conjunction case requires dovetailing in the r.e. case. And doesn't the $ case sound familiar?

Exercise 7 (optional): You already know how to show that the recursive sets are not closed under $ and the r.e. sets are not closed under ". Try showing these facts using only results on the table. Hint: express the halting problem and its complement using quantifiers over the Kleene predicate.