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

DOI10.2307/2275452zbMATH Open0764.03014OpenAlexW1970784900MaRDI QIDQ4032885FDOQ4032885

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

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

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)

Cites Work

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

Cited In (3)

• 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)