Clearly and are recursive, and . For and , we have if and only if . Thus is a truth-table reducibility operator. Let P be a nonempty subset of . A splitting function for P is a recursive function such that for all e , if and P e is nonempty, then and are nonempty.
P is said to be productive if there exists a splitting function for P .
There exists a nonempty set such that P is productive. Clearly P is nonempty and . We claim that g is a splitting function for P . To see this, suppose and . Lemma 3.15 Let P and Q be nonempty subsets of .