Abstract

The object of this paper is to explain a certain type of construction which occurs in priority proofs and illustrate it with two examples due to Lachlan and Harrington. The proofs in the examples are essentially the original proofs; our main contribution is to isolate the common part of these proofs. The key ideas in this common part are due to Lachlan; we include several improvements due to Harrington, Soare, Slaman, and the author.Our notation is fairly standard. If X is an r.e. set, Xs is the finite set of elements enumerated in X before step s. if Ф is a recursive functional, Фs is the approximation to Ф at step s; it only queries the oracle about numbers xi and iless-than-or-equals, slantx; and right-pointing angle bracketx0,...,xk−1right-pointing angle bracket is an increasing function of each of its arguments. Sets are sometimes identified with their characteristic functions. Wj isthe jth r.e. set. Xc is the complement of X