On reducibility by recursive functions
Paul R. Young · Proceedings of the American Mathematical Society · 1964
Throughout this paper, the word "set" means set of nonnegative integers. Definition (Kleene-Post).The join of two sets A and B (J(A,B)) is {2x\xEA}VJ{2x+l\xEB}.1. Introduction.In [5], Kleene and Post show that J(A, B) determines a least upper bound of the degrees of A and B in the partial ordering of Turing degrees of unsolvability.It is easily shown (and well known) that I (A, B) determines a least upper bound of the degrees of A and B in the partial orderings of truth-table degrees, bounded-truth-table degrees, and many-one degrees.Thus the partial orderings of these degrees are all upper semi-lattices.The principal result of this paper (Corollary 2) is that the partial ordering of oneone degrees is not an upper semi-lattice.A second result is that there is a pseudocreative set P and a simple set 5 such that P is many-one reducible to 5 but 5 is not Turing reducible to P. 2. Notation.We write A ^x B to indicate that there is a 1-1 recursive function/ such that x£A if and only if f(x)£B, and we write A ¿i B if there is no such function.If both A ^i B and B ^i A, we write A =\B, and if neither A ^\B nor B 1i\A we say that A and B are 1-1 incomparable.We write A ^m B if there is some recursive function g such that x£A if and only if g(x)E.B.If A ;Sm B and B ¿m A, we write A =m B. N is the set of all nonnegative inte-