We present a necessary and sufficient condition for the embeddability of a principally decomposable finite lattice into the computably enumerable degrees. This improves a previous result which required that, in addition, the lattice be ranked. The same condition is also necessary and sufficient for a finite lattice to be embeddable below every non-zero computably enumerable degree.

We define a class of finite partial lattices which admit a notion of rank compatible with embedding constructions, and present a necessary and sufficient condition for the embeddability of a finite ranked partial lattice into the computably enumerable degrees.

Working in the language of first-order arithmetic we consider models of the base theory P - . Suppose M is a model of P - and let M satisfy induction for σ 1 -formulas. First it is shown that the Friedberg-Muchnik finite injury argument can be performed inside M, and then, using a blocking method for the requirements, we prove that the Sacks splitting construction can be done in M. So, the "amount" of induction needed to perform the known finite (...) injury priority arguments is Σ 1 -induction. (shrink)

Our ultimate purpose is to give an axiomatic treatment of recursion theory sufficient to develop the priority method. The direct or abstract approach is to keep in mind as clearly as possible the methods actually used in recursion theory, and then to formulate them explicitly. The indirect or experimental approach is to look first for other mathematical theories which seem similar to recursion theory, to formulate the analogies precisely, and then to search for an axiomatic treatment which covers not only (...) recursion theory but also the analogous theories as particular cases.The first approach is more general because it does not depend on the existence of analogues. A concrete mathematical theory, it seems, need have no such analogues and still be important, as e.g. classical number theory. In such a case, an axiomatic treatment may still be useful for exhibiting the mathematical structure of the theory considered and the assumptions on which it rests. However, it will lack one of the most heavily advertised advantages of the axiomatic method, namely, the “economy of thought” which results from an uniform theory for several different and interesting cases: we cannot hope for this if, by hypothesis, we know of only one particular case. In contrast, the second approach, if successful at all, is bound to achieve such “economy” because we start out with several interesting particular cases. Another possible virtue of the second approach is that of field work over insight: the abstract pattern that we are looking for and hoping to formalize in axioms, may not be evident in any one mathematical theory, but may spring to the eye if one happens to look simultaneously at several theories which happen to realize the pattern. (shrink)

We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.

We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0'. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice E of recursively enumerable sets with inclusion. (...) We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions. (shrink)