No label defined (Q4934281)

This chapter gives a carefully constructed, broad summary of what is known about the r.e. degrees and offers a glimpse of the subject's development and methodology. It articulates the questions and conjectures that have played major roles and illuminates the array of issues that are still unresolved. \({\mathcal R}\) is the structure consisting of the r.e. degrees with partial order induced by Turing reducibility. Shore's survey includes exploration of model-theoretic questions about \({\mathcal R}\). He focuses on embedding problems, and uses them as a springboard to such classical results as the Density, Splitting, and Nondiamond Theorems, and the existence of minimal pairs. He examines questions of undecidability. \({\mathcal R}\)'s theory is recursively isomorphic to the theory of arithmetic. Even its set of \(\Pi_3\) sentences is undecidable, but its \(\forall\exists\)-theory, its true \(\Pi_2\) sentences, is conjectured not to be. Increasing evidence shows \({\mathcal R}\) to be ``as complicated as possible''. Attention is given to the Biinterpretability Conjecture for \({\mathcal R}\), still of interest though disproved in its strong form by the result that \({\mathcal R}\) has a nontrivial automorphism. Shore looks at questions relating externally defined classes to \({\mathcal R}\). The only such classes that have been shown to be naturally definable in \({\mathcal R}\) are the classes of promptly simple and contiguous degrees. It is conjectured that the \(\text{low}_2\) degrees are also so definable. It was Post's search for an ``intermediate degree'' that triggered the entire subject of the r.e. degrees. Interestingly, the question of whether any such degree is naturally definable in \({\mathcal R}\) remains open. There is an ample bibliography. For the entire collection see [Zbl 0923.03001].