The ∀∃-theory of ℛ(≤,∨,∧) is undecidable

DOI10.1090/S0002-9947-03-03406-8zbMath1054.03029OpenAlexW1956375874MaRDI QIDQ4813796

Richard A. Shore, André Nies, Russell G. Miller

Publication date: 13 August 2004

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0002-9947-03-03406-8

zbMATH Keywords

undecidabilitydecidabilityrecursively enumerable degreeTuring reducibilitycomputably enumerable degree

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28)

Related Items (4)

Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ Lattice initial segments of the hyperdegrees ⋮ Extensions of embeddings below computably enumerable degrees ⋮ Degree Structures: Local and Global Investigations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Incomparable prime ideals of recursively enumerable degrees
• Degrees of unsolvability: structure and theory
• On degrees of recursive unsolvability
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical
• First-order theory of the degrees of recursive unsolvability
• A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees
• The recursively enumerable degrees are dense
• Initial segments of the degrees of unsolvability
• The upper semi-lattice of degrees of recursive unsolvability
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Decidability and Invariant Classes for Degree Structures
• The undecidability of the recursively enumerable degrees
• Interpretability and Definability in the Recursively Enumerable Degrees
• The Theory of the Degrees below 0 ′
• A recursively enumerable degree which will not split over all lesser ones
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• Embedding finite lattices into the ideals of computably enumerable turing degrees
• PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES
• On the Σ₂-theory of the upper semilattice of Turing degrees
• On the Degrees of Index Sets
• The impossibility of finding relative complements for recursively enumerable degrees
• Distributive Initial Segments of the Degrees of Unsolvability
• Recursive Enumerability and the Jump Operator
• Computability of Recursive Functions
• Extension of embeddings in the computably enumerable degrees

This page was built for publication: The ∀∃-theory of ℛ(≤,∨,∧) is undecidable