The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility

DOI10.2307/2275452MaRDI QIDQ4032885zbMATH OpenOpenAlexFDO

Authors Steffen Lempp, Manuel Lerman

Publication date 1 April 1993

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275452

zbMATH Keywords

decidabilityTuring jumpTuring reducibilityr.e. degreesembedding of finite partial orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Recursively (computably) enumerable sets and degrees (03D25)

Recommendations

• The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations
• The \(\forall\exists\) theory of \({\mathcal D}(\leq,\vee,{}')\) is undecidable
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• scientific article; zbMATH DE number 3954890

Cites work

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• A limit on relative genericity in the recursively enumerable sets
• A non-inversion theorem for the jump operator
• Distributive Initial Segments of the Degrees of Unsolvability
• First-order theory of the degrees of recursive unsolvability
• Lattice embeddings into the recursively enumerable degrees. II
• On homogeneity and definability in the first-order theory of the Turing degrees
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• The undecidability of the recursively enumerable degrees

Cited in

(4)

• On some reducibility and existential interpretability of structures
• There is no ordering on the classes in the generalized high/low hierarchies
• The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations
• Degree Structures: Local and Global Investigations

This page was built for publication: The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032885)