A theorem on intermediate reducibilities
Thomas G. McLaughlin · Proceedings of the American Mathematical Society · 1968
Let a, f3 be two sets of natural numbers. Then [2] the least upper bound of (the Turing degrees of) oa and ,B is the (Turing degree of the) set J(a, B) = {2x I x Ca J U { 2x + ?1 x C1 }. In general, we shall denote by l al T the Turing degree of a set a of natural numbers, and by I a I M and I af tt the many-one and truth-table degrees, respectively, of a [5]. It is a trivial fact that IJ(a, 3)IM and IJ(a, O)I tt are least upper bounds for the pairs I al M, I 11 M and I al tt, I |1 tt, respectively. We denote by < T, M, and < tt the partial order of degrees in the Turing, many-one, and truth-table semilattices, respectively. The following fact about the semilattice of Turing degrees is well known and easy to prove: