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

DOI10.1090/S0002-9947-98-01800-5MaRDI QIDQ4211072zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 833149 (Why is no real title available?)
• scientific article; zbMATH DE number 3304986 (Why is no real title available?)
• A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees
• A minimal pair of recursively enumerable degrees
• Degrees of Unsolvability. (AM-55)
• Extension of embeddings in the computably enumerable degrees
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Recursively enumerable sets of positive integers and their decision problems
• 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
• Undecidability and 1-types in the recursively enumerable degrees
• Undecidable fragments of elementary theories

Cited in

(20)

• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• scientific article; zbMATH DE number 761273 (Why is no real title available?)
• 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 ^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 degrees is undecidable
• Turing computability: structural theory
• On the existence of a strong minimal pair
• scientific article; zbMATH DE number 39360 (Why is no real title available?)
• 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}}\)

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)