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.

*cohesive*, and r.e. sets whose complements are cohesive are called

*maximal*. For question 4 you are showing that maximal sets exist, a result first proven by Friedberg in 1958.

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