Interpreting true arithmetic in the theory of the r.e. truth table degrees

DOI10.1016/0168-0072(94)00048-8zbMath0836.03023OpenAlexW1972858266MaRDI QIDQ1902619

Richard A. Shore, André Nies

Publication date: 2 May 1996

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(94)00048-8

zbMATH Keywords

first-order arithmeticrecursively enumerable degreestruth table degreescomplexity of theories

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (3)

The last question on recursively enumerable \(m\)-degrees ⋮ Interpreting true arithmetic in the -enumeration degrees ⋮ Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undecidability and 1-types in the recursively enumerable degrees
• Infima of recursively enumerable truth table degrees
• Classical recursion theory. Vol. II
• Definability in the enumeration degrees
• The last question on recursively enumerable \(m\)-degrees
• The undecidability of the recursively enumerable degrees
• The Theory of the Degrees below 0 ′
• Strong reducibilities
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• Undecidability and initial segments of the (r.e.) tt-degrees
• A Note on the Denumerability of the Rational Numbers

This page was built for publication: Interpreting true arithmetic in the theory of the r.e. truth table degrees