Let's generalize the question by saying that a set A splits a set B if both A∩B and A∩B are infinite. Schöning really shows the more general result that any infinite recursive set can be split by a polynomial-time computable set.
Playing with this splitting notion yields lots of potential homework questions. Try these:
- Show that every infinite regular language can be split by another regular language. Can every infinite context-free language be split by a regular language?
- Show there is an infinite recursive set that cannot be split by any regular language.
- Prove Schöning's result above: Every infinite recursive set can be split by a set in P.
- For a real challenge, show that there is an infinite co-r.e. set that cannot be split by any r.e. set.
Shall we clam, as a consequence of Schoning's result, that 'there is no recursive set A such that every infinite recursively enumerable subset of A is co-finite in A'?ReplyDelete