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. (shrink)

In this paper, we first prove that there exist computably enumerable (c.e.) degrees a and b such that ${\bf a\not\leq b}$ , and for any c.e. degree u, if ${\bf u\leq a}$ and u is cappable, then ${\bf u\leq b}$ , so refuting a conjecture of Lempp (in Slaman [1996]); secondly, we prove that: (A. Li and D. Wang) there is no uniform construction to build nonzero cappable degree below a nonzero c.e. degree, that is, there is no computable function (...) $f$ such that for all $e\in\omega,$ (i) $W_{f(e)}\leq_{\rm T}W_e$ , (ii) $W_{f(e)}$ has a cappable degree, and (iii) $W_{f(e)}\not\leq_{\rm T}\emptyset$ unless $W_e\leq_{\rm T}\emptyset.$. (shrink)

It will be shown that there exist computably enumerable degrees a and b such that a $>$ b, and for any computably enumerable degree u, if u $\leq$ a and u is cappable, then u $<$ b.

A computably enumerable degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below a is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possible so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC, and show that (...) there exists a minimal pair which join to a plus cupping degree, so that PC ⊈ NB. This gives a first known difference between NB and PC. (shrink)

We prove that every non-computable incomplete computably enumerable degree is locally non-cappable, and use this result to show that there is no maximal non-bounding computably enumerable degree.

A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about (...) the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory. (shrink)

In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces.

We prove that for any computably enumerable degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c d = 0′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.

We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, ${{\bf 0' = b \lor x}}$ if and only if (...) ${{\bf 0' = a \lor x}}$ . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively. (shrink)

We study the jump hierarchy of d.c.e. Turing degrees and show that there exists a high d.c.e. degree d which does not bound any minimal pair of d.c.e. degrees.

We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models, and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey’s Theorem for Pairs.