244 COMPUTABILITY THEORY
Finally, we know that f # &cn) for all n 2 0, because f(n) # &(n) (n).
So, f provides us a contradiction to the assumption that TOT is r.e. cl
The above examples are straightforward applications of diagonalization.
The following example is more involved. It shows how to modify the diag-
onalization requirements to create space for the object to be constructed to
have some additional properties.
We say an r.e set S is simple if its complement S is infinite but does not
contain any infinite r.e. subset.
- Example 5.23 Show that there exists a simple set.
Proof. The idea is to construct a set S such that for every n > 0, if VI&
is infinite then we include an element of M& in S. That is, the-first set of
requirements we need to satisfy is
RI ) n: If VVn is infinite, then S fl VVn # (8, n > - 0.
If these requirements are satisfied, then the complem ent S of S does not
contain any infinite VVn as a subset.
In addition to these requirements, we also need to make sure that S is
too big; that is, we need to make 3 infinite. So, we also need to satisfy
R2,n: For every n > - 0, I%? {x 1 x < 2n)l > - n, n > - 0.
It is easy to see that these requirements imply that ;F is infinite.
There is, however, a problem with the above idea. Namely, the set INF =
{n 1 VVn is infinite} is not an r.e. set (see Example 5.34), and so we will not be
able to enumerate all infinite VV& which appears necessary in order to satisfy
the requirements R + by a Turing machine. The solution to this problem is
that we will pretend that every VVn is infinite and try to include an element of
VVn in S for all n > 0. This modification of requirements RI 72 is acceptable
since it does not hurt if we have S n W, # 8 for some finite r/G,.
In the following, we construct set S by enumerating strings of S one at a
time. This make S a Turing-enumerable set and, hence, an r.e. set.
Let A = {(n,z) 1 x E VI&, x > - an}. Then, it is easy to see that A is an
infinite r.e. set. From Theorem 5.13, it is the range of a recursive function g.
We now describe an algorithm that enumerates the set S:
AZgorithm for S. We maintain a finite set B in our construction.
Before stage 0, we let the set B be empty. Then, we go to stage 0.
At stage e, we compute g(e) and let n = E(g(e)) and x = r(g(e));
that is, g(e) = (n, 2). If n 4 B, then we print string IX: and add n
to set B; else we do nothing. Then, we go to stage e + 1.It is clear that each stage e ends in a finite number of steps since g is
recursive. Therefore, by the Church-Turing Thesis, the above construction
can be implemented by a Turing machine and so the output set S is Turing-
enumerable.