John Martin Introduction to Languages and the Theory of Computation book

Question

Show that if L ⊆ Σ* and L is infinite and recursively enumerable, then L has an infinite subset that is not recursively enumerable and an infinite subset that is recursively enumerable but not recursive.

Answer 1

We don't need to rely on the fact that L is recursively enumerable to show these things; all infinite sets of strings have subsets that are not recursively enumerable and that are recursively enumerable but not recursive. There are lots of different ways to think about this but the following is pretty straightforward.

The cardinality of the infinite set ?* is the same as that of the natural numbers. This is the "smallest" infinity in the sense that the set of natural numbers can map into any other infinite set (though the reverse is not necessarily true; e.g., the reals cannot map into the naturals without substantial overlap). It follows that any infinite subset of ?* must also have the same cardinality; that is, any infinite set of strings can be put into direct one-to-one correspondence with the natural numbers. We can construct such a mapping for ?* as follows: take the strings of ?* in increasing lexicographical order and map the first to 0, the second to 1, and so on. By assigning each symbol in ? some value from 0 to |?| - 1, we could even devise a procedure to calculate the corresponding natural number for a string. Consider ? = {a, b, c} for instance, then the strings of ?* are:

string    position
e         0
a         1
b         2
c         3
aa        4
ab        5
ac        6
ba        7
bb        8
bc        9
ca        10
cb        11
cc        12

This suggests assigning values of 1, 2 and 3 to a, b and c, respectively, and then calculating for word w the sum of 3^(|w| - i) * di for i = 1 to |w|. So, the string abcabc would correspond to the natural number 13^5 + 23^4 + 33^3 + 13^2 + 23^1 + 33^0 = 243 + 162 + 81 + 9 + 6 + 3 = 504.

Similarly, because the cardinality of any infinite subset of ?* must be |?*|, there exists some mapping between the strings of the subset and the natural numbers; equivalently, between the strings of the subset and the strings of ?*. Figuring this out for a particular subset might be hard, maybe even impossible. And if you figure it out, actually computing the mapping might be hard or impossible. But, in the Platonic universe of ideal forms, such mappings exist, and that is enough for our present purpose. Let us refer to using the symbol f some mapping that takes ?* to the recursively enumerable subset hypothesized in the problem statement.

Take any non-recursively-enumerable subset of ?*. Call this R. Then, let R' be the image of R w.r.t. the mapping f; that is, R' is the set of strings in our subset that are mapped to from strings of R. But then R' must not be recursively enumerable either, since if it were, we could use the inverse of f, f', to recursively enumerate R, as follows: enumerate the strings in R', and for each such string w, output the string f'(w). This enumerates all the strings in R, which we said cannot be done. So, we know that R' must not be recursively enumerable.

Take any recursively-enumerable but non-recursive subset of ?*. Call this S. Then, let S' be the image of S w.r.t. the mapping f; that is, S' is the set of strings in our subset that are mapped to from strings of S. But then S:

1. must be recursively-enumerable. This is true because we can enumerate the strings in S and, for each such string w, output f(w), thus enumerating the strings in S'. So, S' is recursively-enumerable.

2. must not be recursive, since if it were, we could produce a decider for the membership question in S', and use it to decide membership in S as follows: for the query string w whose membership in S we want to ascertain, check whether f(w) belongs to S'; if so, then w is in S, otherwise it is not. But we said S was not recursive, so S' cannot be recursive either.