5.3 Diagonalization 241
- Recall that AB = {zyIx~A,y~l3}. DefineA+B={n+mInE
A, ti E l?}.
(a) Show that if A and B are r.e. sets then Al?, A + B and A are
also r.e.
(b) Show that if A and B are recursive sets then AB, A + B and A
are also recursive. - Define a set C = {(x, y) 1 there exists a partial recursive function f such
that f(z) is defined and f(z) = y}.
(a) Prove that C is r.e.
(b) Is C recursive? why? - Show that the following function is partial recursive:
k: if (3-t) [&(n) = #)j(n) = k],
‘(“” Ic) = { t otherwise.5.3 Diagonalization
In the last section, we studied how to prove that a set is r.e. or is recursive.
The main tools are simulation algorithms and the projection theorem. In this
and the next sections, we develop proof techniques to show that a set is not
recursive or is not r.e.
The first proof technique is diagonalization. Suppose that we are given
an infinite number of objects (sets or functions) Al, AZ,... and want to
construct a new object B that is different from each of the given objects.
Also suppose that the object B consists of an infinite number of parts. The
diagonalization technique constructs B one part at a time, making the ith
part different from the corresponding part of Ai. When the infinite number
of steps of construction are done, we obtain an object B that is different from
every Ai, i > 0. - The following is a simple example.Example '5.18 Show thut the set F offunctions from N to (0, 1) is uncount-
able.Proof. Suppose otherwise that F is countable; that is, it can be listed as fo,
fl, f2, l ** * Define a new function f : N + (0, 1) by f(n) =^11 fn (n). Then,
f E F and f # fn for every n > 0, because f(n) = 1 A fn(n) # fn(n). Thus,
we have found a contradiction tO the assumption that F consists of fo, fi,....In the above example, we are given a list of functions fo, fi, f2,... , and
need to find a new function f E F such that f is different from every fn,
n > 0. - That is, we need to satisfy an infinite number of requirements:Ri: f#fi, i=O,l,....