The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable

DOI10.1090/S0002-9947-98-01800-5zbMath0904.03029OpenAlexW1924972752MaRDI QIDQ4211072

Steffen Lempp, André Nies, Theodore A. Slaman

Publication date: 10 September 1998

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-98-01800-5

zbMATH Keywords

undecidabilitycomputably enumerable degreesTuring degreesrecursively enumerable degrees\(\Pi_3\)-theoryfragment of first-order theory

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (16)

Maximal contiguous degrees ⋮ Extensions of two constructions of Ahmad ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable ⋮ Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ Continuity of capping in \(\mathcal C_{\text{bT}}\) ⋮ A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees preserving greatest element ⋮ Fragments of the theory of the enumeration degrees ⋮ 1998–99 Annual Meeting of the Association for Symbolic Logic ⋮ Turing computability: structural theory ⋮ Principal filters definable by parameters in 𝓔_bT ⋮ Degree Structures: Local and Global Investigations ⋮ The Π₃-theory of the -enumeration degrees is undecidable ⋮ A necessary and sufficient condition for embedding ranked finite partial lattices into the computably enumerable degrees ⋮ On the existence of a strong minimal pair ⋮ Undecidability and 1-types in intervals of the computably enumerable degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undecidability and 1-types in the recursively enumerable degrees
• A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees
• Undecidable fragments of elementary theories
• The recursively enumerable degrees are dense
• The undecidability of the recursively enumerable degrees
• The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees
• Degrees of Unsolvability. (AM-55)
• A minimal pair of recursively enumerable degrees
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Recursively enumerable sets of positive integers and their decision problems
• Extension of embeddings in the computably enumerable degrees

This page was built for publication: The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable