On a theorem of Lachlan and Martin
Gerald E. Sacks · Proceedings of the American Mathematical Society · 1967
In [3] we raised the following question: does there exist a recursively enumerable degree d such that 0(n)< <(n) < O(n+1) for all n ?0? This question was answered affirmatively by Lachlan [I] and by Martin [21. Lachlan's proof combines a familiar priority argument with the fixed point theorem of Kleene. Martin's proof is a new form of priority argument based on Theorem 3 of section 6 of [3]. In this paper we give a vanishingly short proof of the Lachlan-Martin result without any use of priority. Our argument is an exercise in the fixed point theorem. We exploit, possibly for the first time, a uniformity concealed in most proofs of the fixed point theorem. Let A be an arbitrary set of natural numbers, and let WA, WA, W2, be a standard simultaneous enumeration of all sets recursively enumerable in A. For each e ? 0, let