5.3 Diagonalization 245
To see that this construction satisfies all requirements, we first check that
for each ?-I such that VI& is infinite, the set A, = {(n,x) 1 (n,z) E A} is
infinite. Let e, = (mine)[g(e) = (n, X) for some z]. Then, at stage e,, n 4 B
and g(e,) = (n,z> f or some E. Therefore, we will include x in S at stage e,.
It follows that S satisfies requirements RI,, , for all n > - 0.
For the second set of requirements Rz,~, we note that for any n > - 0, set
S n {Z 1 x < 2n) contains at most n strings since each of these strings x
must come from g(e) = ( m, X) for some m. < n, and for each such nz, we add
at most one string 2 to S. Therefore, requirements R2,n are satisfied for all
n > 0, and the construction works correctly. 0
Exercises 5.3
1.
2.
3.
4.
5.
6.
Let A be any set (not necessarily countable). Show that there does not
exist a one-to-one correspondence between set A and the set 2A of all
subsets of A.
Show that the set Fl of all one-to-one, increasing functions from N to
N is uncountable.
What are wrong with the following diagonalization x>roofs?( > a
(b)
We show that there exists a partialiecursive function f : (0, l}* +
(0, l}* which is not enumerated in &,&,.... Define f(n) =
q!+Jn) + 1. Then, by the existence of the universal DTM, we can
see that f is partial recursive. Thus, we have obtained a partial
recursive function f that is different from every & at input n,
n > 0.
We- show that the set REC = {X ( PVZ is recursive} is not r.e,
Suppose, by way of contradiction, that REC is r.e. Then, there
exists a recursive function g whose range is equal to REC. Define
A = {Z 1 x 6 ‘w,(,)}. Since each IV+) is recursive, it is decidable
whether x: E I+&). Therefore, A is a recursive set. But this is a
contradiction, since A # IV”(,) for every it: 2 0.Assume that A C N is a set with the following properties: (i) 4n is
recursive for all GE A, and (ii) for all recursive functions f, f = $n for
some n E A. Show that A is not an r.e. set.
(a) Show that the class of primitive recursive functions is effectively
enumerable (in the sense that there is an re. set B such that (i)
4 n is primitive recursive, for all n E I?, and (ii) for all primitive
recursive function g, g = $n for some n E B).
(b) Show that there exists a recursive function that is not primitive
recursive.Show that set A = {n 1 4n halts on n and its output is greater than n}
is not a recursive set.