The infinite injury priority method

• Published in: The Journal of symbolic logic 1976-06, Vol.41 (2), p.513-530
• Main Author: Soare, Robert I.
• Format: Article
• Language: English
• Subjects: Eigenfunctions; Index sets; Interpolation; Logical theorems; Mathematical induction; Mathematical lattices; Mathematical theorems; Recursion; Recursive functions; Recursively enumerable sets
• ISSN: 0022-4812; 1943-5886
• DOI: 10.1017/S0022481200051598

One of the most important and distinctive tools in recursion theory has been the priority method whereby a recursively enumerable (r.e.) set A is constructed by stages to satisfy a sequence of conditions { R n } n ∈ω called requirements . If n < m , requirement R n is given priority over R m and action taken for R m at some stage s may at a later stage t > s be undone for the sake of R n thereby injuring R m at stage t . The first priority method was invented by Friedberg [2] and Muchnik [11] to solve Post's problem and is characterized by the fact that each requirement is injured at most finitely often. Shoenfield [20, Lemma 1], and then independently Sacks [17] and Yates [25] invented a much more powerful method in which a requirement may be injured infinitely often, and the method was applied and refined by Sacks [15], [16], [17], [18], [19] and Yates [25], [26] to obtain many deep results on r.e. sets and their degrees. In spite of numerous simplifications and variations this infinite injury method has never been as well understood as the finite injury method because of its apparently greater complexity. The purpose of this paper is to reduce the Sacks method to two easily understood lemmas whose proofs are very similar to the finite injury case. Using these lemmas we can derive all the results of Sacks on r.e. degrees, and some by Yates and Robinson as well, in a manner accessible to the nonspecialist. The heart of the method is an ingenious observation of Lachlan [7] which is combined with a further simplification of our own.