scientific article; zbMATH DE number 1390016
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].
- Cappable recursively enumerable degrees and Post's program
- Conjectures and questions from Gerald Sacks's \textit{Degrees of unsolvability}
- Cellular automata and intermediate degrees.
- Interpreting true arithmetic in the theory of the r.e. truth table degrees
- scientific article; zbMATH DE number 5000253 (Why is no real title available?)
- A hierarchy of families of recursively enumerable degrees
- Cupping the Recursively Enumerable Degrees by D.R.E. Degrees
- The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
- An extension of the recursively enumerable Turing degrees
- Weak density and cupping in the d-r.e. degrees
- Undecidability and 1-types in the recursively enumerable degrees
- Model-theoretic properties of Turing degrees in the Ershov difference hierarchy
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4934281)