THE UN IVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND TE ARTS Department of Philosophy Technical Note INSEPARABLE SETS AND REDUCIBILITY So Tennenbaum.ORA Project 05105 under contract with: DEPARNET OF TEE NAVY OFFICE OF NAVAL R;EEARCH CONTACT NOo Nonr 1224(21) WASHINGTON, DoCa administered through: OFFICE OF RESEARCH ADMINISTRATIO N ANN ABIOR July 1961 (Reprinted November 1961)

Inseparable Sets and Reducibility* Stanley Tennenbaum Recursively inseparable sets have a number of interesting applications to mathematical logic. For example, the existence of undecidable formulas in all merely consistent extensions of classical arithmetic is an immediate consequence of the representability of such sets in that formalism0 This note contains a construction of inseparable sets of a new type and a rather curious application of these to the theory of machine reducibility initiated by E* Posts Two disjoint sets A, B of non-negative integers (in the sequel, simply "numbers") are inseparable if every pair of recursively enumerable sets A', B', with ACAT and BcB', fails to be complementaryo The most direct construction of recursively enumerable sets with this property is as follows: Let Dn be an effective enumeration of all possible partial recursive definitions of 0, 1 functions of one argumenti Let Fn(X) be the partial function defined by Dnq Men Fn(x) is a partial recursive 0, 1 function of the numbers n and xX Taking addition mod 2, let A = xjFx(x) + 1 = 0 and B - XlFx(x) + 1 = lo A and B are clearly recursively enumerable and disjoint In fact, they are inseparable. For every pair of disjoint recursively enumerable sets Al, B1, with AcAC and BcBS, determines in a natural way a partial recursive 0, 1 function, Fk(x) such that A' = xFk(x) = 0 and BI = xlFkjx) = 1l Now kAn. For if keA' then *Support for this research was given through grants from the National Science Foundation and the U0 So Army Signal Corps and through contract funds from the Office of Naval Research. 1

F (k)g = 0 and thus Fk(k) + 1 = 1 But then keB and A' n B n A, contradicting the choice of AK Similarly kOB ThIus kcA' U B iOe. Al and B1 are not complementary The two sets A and B enjcy a further property implicit in the above argumento If Fa (x) and Fb (x) are partial recursive characteristic functions for AC and. B1 (ioeo if Fa, x) and Fb,(y) are defined precisely when xeAc and yeBC and are equal to 1 when they are defined) then an "index" k of the partial function9 Fk(x). used above, can effectively be obtained from a' and bo But k is "witness" to the fact that A' and B' are not complementaryo More precisely; there is associated with the inseparable sets A and B a recursive function h, of two arguments This function attaches to any pair of numbers a', b8 which happen to be indices of partial characteristic functions of disjoint sets A' B' with AcA' and BcBG a witness number h(a, b8) = k such that keA8 UB' o Because of the eiestence of such a functiona A and B are called "effectively" inseparable The question whether there exist inseparable recursively enumerable sets which are not effectively inseparable was raised by Uspenskii4 Schoenfield3 has given examples of such "non-effectively" inseparable setso The sets which we construct are also examples o However; they are non-effectively inseparable in a most extreme senseo We shall call them S and To They are recursively enumerailel- disjoint, and SU T is infiniteO Their special feature is the following: if S T are dis;joint recursively enumerable sets with Sc SI and Tc T then S' S and TP -T are both finite~ ~lhus S and T are obviously inseparable~ To see that they are not effectively inseparable, observe that S U T though in

finite, contains no infinite recursively enumerable subseto (Infinite sets devoid of infinite recursively enumerable subsets are called immuneo Recursively enumerable sets, such as S U T, with immune complements were first discovered by Post and are called simpleo) For if an infinite recursively enumerable set X were contained in S UT, SUX would be recursively enumerable, disjoint from T, and (SUX) - S would be infinite, contradicting the special feature of So However if S and T were effectively inseparable the "witnessingt function h(jx, x2) could trivially be used to produce an infinite recursively enumerable subset of SUTo To construct S and T, we set E, n xlFE(x) I and thus obtain in En an effective enumeration of all recursively enumerable setso We imagine En as being generated in the course of some fixed routine devised to compute Fn(x) for all possible n and so As Fn x) is computed we arrange for each n to have all members of E, greater than 4n recorded in a list Ln in the order in which they are generatedo Next we settle on a schedule of repeatedly inspecting these lists so that as the computation of F,(x) goes on, we will sooner or later see any number which is recorded in any listo Finally a we carry with us a sheet divided into two columns in which we copy numbers from I, according to the following three rules (1) If Ln bears numbers and none of them appears in our columns, copy the smallest number of Ln into first columno (2) If L bears numbers and some but not all of them appear in one of our columns, but none in e oth opy the oth, opy the l umber in Ln not appearing in the one column into the othero

(3) Otherwise, pass on to the next list in the schedule. Now let S = set of numbers copied into our first and T = set of numbers copied into our second column. S and T are recursively enumerable. It is an exercise to construct partial recursive characteristic functions for them from the preceding intuitive sketch. (Unfortunately the formal definition of these functions does not expose the simple idea which guides the construction of S and To In fact our construction is just a modification of Post's construction of a simple set2. They are clearly disjoint. Now suppose S' is recursively enumerable and disjoint from T while containing S. S' would be generated by some Es. If.' - S were infinite sooner or later Ls, would contain a number xeS' — S. Rule (2) would apply and S'rT T / A. Therefore S' — S is finite. The same argument shows that if T' contains T and is disjoint from S then T'- T is finite. Finally S UT is infinite since at most 2(n-l) of the numbers up to 4n can be placed in S U T. One set of numbers is said to be reducible to another set of numbers if the characteristic function of the first is recursive in the characteristic function of the second. This means that there exists a machine so programmed that if an outside source supplies it successively with the correct values of the characteristic function of the first set, the machine is able to compute successively the correct values of the characteristic function of the second set, It is readily shown that for recursively enumerable sets A and B, this condition can be simplified so that A is reducible to B just in case there exists a partial recursive function ~x(n) defined for all n when xCA such that

(Vx) x~Ae — )(n)(Pix(n)c B) Here Pm is ary effective enumeration of all finite sets of numbers. Intuitively, this means that for a machine to discover whether xeT7 it computes one by one a sequence of finite sets attached to each x. For every finite set it "asks" the outside source whether all numbers belong to B. If the answer is yes, the machine declares that xeA. If no, it computes the next "round of questions." In this manner, if A is reducible to B, for each x the machine will receive the answer "yes" to some round of questions in which case xeA or else x will turn up in the auxiliary process of generating the recursively enumerable set A. It is important to recognize that, in general, if ~x(n) supplies a "reduction" of A to B there may be no a priori effective upper bound to the number n of rounds,'X (l) Px (2), "' x(n) the machine must compute before either it receives the answer "yes" to some round or x turns up in A. In case each round of a reduction contains just one question, i.e., if ~ x(n) is a single number for every x and each n, we call ~x(n) a Q-reduction of A to B. If B is the set of "indices" in some effective enumeration of those diophantine equations, which have solutions, and if A is an arbitrary recursively enumerable set, then A is reducible to B just in case there is a Q-reduction of A to Be This follows immediately from that fact that there is a trivial mapping which assigns to each finite set of diophantine equations a single equation such that none of the finite set has a solution if, and only if, the single equation has no solution. It seems plausible that more generally for any pair A and B of recursively enumerable sets A is reducible to B just in case A is 5

Q-reducible to B. Indeed, since the number of rounds of single questions in a Q-reduction has no a priori bound, what possible advantage accrues to rounds with more than one question? Nevertheless, there are recursively enumerable sets A and B with A reducible to B but not Q-reducible to B. We first show that no simple set is Q-reducible to S. To this end, let B be an arbitrary such set. To sya that B is Q-reducible to S is equivalent (by birtue of the fact that in Q-reductions each round contains a single question) to asserting the existence of a recursive function 2(x) such that (Vx)(XEB4- Et(x)S E A) where Em is, as before, an effective enumeration of all recursively enumerable sets. Now to each xeB there belongs a recursively enumerable set El(x) (all the rounds of single questions for x). Let B1 = xE (x)n T. A B1 is obviously recursively enumerable, and by the definition of a Q-reduction, B1 B. But since B is simple, B contains no infinite recursively enumerable subset. Therefore B1 is finite, and thus its complement B, is recursively enumerable. Let C = C- El(x). C is recursively enumerable and disjoint from T. Therefore considering the special feature of s, C - S if finite. It follows that B2 = xlEi(x)C - S / / is a recursively enumerable subset of B and accordingly finite. Yet B1 B2 = B. In other words B is finite, so we have a contradiction. Conclusion: There is no simple set Q-reducible to S. On the other hand, Dekkerl has found a natural method of assigning to any 6

recursively enunerable and non-recursive set, a simple set which is reducible to the given set: If A is the given set, let f be any 1-1 recursive function ranging over A. Define A' = nl(ak)(k > n &f(k) < f(n) It is easily shown that A' is simple and reducible to A. Consequently there is a simple set which is reducible to S. If follows that Q is not the most general type of reducibility. 7

Bibliography 1. J. C. E. Dekker, "A Theorem on Hyper-simple sets", Proceedings of the American Mathematical Society, 5, 5, 791-796, 1954. 2. E. L. Post, "Recursively Enumerable Sets of Positive Integers and Their Decision Problems", Bulletin of the American Mathematical Society, 50, 281-316, 1944. 5. J. R. Shoenfield, "Quasicreative Sets," Proceedings of the American Mathematical Society, 8, 5, 964-967, 1957. 4. V. A. Uspensky, "Godel's Theorem and the Theory of Algorithms," Doklady Akademii Nauk S.S.S.P. 91, 4, 737-740, 1953.