There is no ordering on the classes in the generalized high/low hierarchies
The high/low hierarchy studied by Soare and Cooper induces a partition of the Turing degrees below \({\mathbf 0}'\). The generalized high/low hierarchy introduced by Jockusch and Posner induces a partition on all the Turing degrees. For \(n\geq 1\), a degree \(\mathbf x\) is generalized low\(_n(\text{GL}_n)\) if \({\mathbf x}^{(n)}=({\mathbf x}\vee {\mathbf 0}')^{(n-1)}\), generalized high\(_n(\text{GH}_n)\) if \({\mathbf x}^{(n)}=({\mathbf x}\vee {\mathbf 0}')^{(n)}\), and generalized intermediate if neither \(\text{GH}_n\) nor \(\text{GL}_n\) for any \(n\). These classes constitute the generalized hierarchy. The paper's main theorem extends a result of Lerman. It establishes the decidability of the existential theory of the Turing degrees in a language with a constant for the degree \(\mathbf 0\), a binary relation for Turing reducibility, and a 1-place predicate for each of the classes of the generalized hierarchy. A further result gives information about the distribution of Turing degrees within the classes of the hierarchy.
- scientific article; zbMATH DE number 3941523
- Decidability and Invariant Classes for Degree Structures
- Embedding Lattices with Top Preserved Below Non‐GL2 Degrees
- Embedding jump upper semilattices into the Turing degrees
- The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility
- Automorphisms of the lattice of recursively enumerable sets
- Degrees which do not bound minimal degrees
- Double jumps of minimal degrees
- Embedding jump upper semilattices into the Turing degrees
- Generalized high degrees have the complementation property
- scientific article; zbMATH DE number 3861137 (Why is no real title available?)
- scientific article; zbMATH DE number 4091484 (Why is no real title available?)
- Interpolation and embedding in the recursively enumerable degrees
- Jump embeddings in the Turing degrees
- Minimal pairs and high recursively enumerable degrees
- Simple Proofs of Some Theorems on High Degrees of Unsolvability
This page was built for publication: There is no ordering on the classes in the generalized high/low hierarchies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q818520)
