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

DOI10.1090/S0002-9947-98-01800-5zbMATH Open0904.03029OpenAlexW1924972752MaRDI QIDQ4211072FDOQ4211072

Authors: 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

Recommendations

• The Π₃-theory of the -enumeration degrees is undecidable
• The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees
• Undecidability and 1-types in intervals of the computably enumerable degrees
• Undecidability and 1-types in the recursively enumerable degrees

zbMATH Keywords

undecidabilityTuring degreescomputably enumerable degreesrecursively enumerable degrees\(\Pi_3\)-theoryfragment of first-order theory

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (20)

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

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

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