5.2 R.E. Sets and Recursive Sets 239
We will see in the next section (Corollary 5.20) that there exist sets that
are r.e. but not recursive.
Example 5.16 Show that if A and B are recursive sets, then A U B, A n B
and A are all reczarsiue.
Proof. This result can be proved by simple simulation algorithms. Here, we
present the proof by the characterization of Theorem - 5.15.
First, since XA (z> = 1 A XA (z), we see that A is also recursive. Now, since
A, B, A and B are all r.e., it follows that A U B, A U B = A n ??, A n B and
A n B = AuB are all r.e. It follows from Theorem 5.15 that AU B and An B
are recursive. cl
A total function f : {O,l} + {O,l} is increasing if f(z) < - f(z + 1) for
all x.
Theorem 5.17 A nonempty set A is recursive if and only if it is the range
of an increasing recursive function f : (0, 1)” + (0, l}*.
Prove. Assume that A is recursive. Let x0 be the least string in A under the
lexicographic ordering. Define f(0) = x0 and
f(x + 1) = {x+1 if&@+I)=1,
f( X ) otherwise.We can see that f is recursive, since f(x) can be expressed as follows (to avoid
the recursive definition) :
f(x) = if x 5 x0 then x0 else (maxy)y&A(y) - = 11.
Furthermore, it is easy to see that the range off is A, and that f is increasing.
Conversely, assume that f is an increasing recursive function and A is the
range of f. Then, from Theorem 5.13, we know that A is r.e. Now, if A is
finite, then A is recursive and so A is r.e. Otherwise, if A is infinite, then we
have
A = {x I x < f(O) Or (3Y)[f(Y) < x < f(Y + l)l),
since f is increasing. So, A is also r.e. We conclude from Theorem 5.15 that
A is recursive. cl
Exercise 5.2
- Assume that A, B, C C - { 0, 1}* are r.e. sets. Let
D=(AnB)u(BnC)U(CnA).(a) Construct a DTM that simulates the three DTM’s accepting sets
A, B, and C in parallel and accepts set D.