Splitting Sets

Can every infinite set in P be partitioned into two infinite subsets, each also in P? Uwe Schöning answers this question in the affirmative in the Winter 1982 SIGACT News.

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:

1. 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?
2. Show there is an infinite recursive set that cannot be split by any regular language.
3. Prove Schöning's result above: Every infinite recursive set can be split by a set in P.
4. For a real challenge, show that there is an infinite co-r.e. set that cannot be split by any r.e. set.

In recursion theory, sets that cannot be split by r.e. sets are called 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.