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

&
Annals of Pure and Applied Logic 75 (3):269-311 (1995)
  Copy   BIBTEX

Abstract

We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(94)00048-8

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,752

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On the structures inside truth-table degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
Coding true arithmetic in the Medvedev and Muchnik degrees.Paul Shafer - 2011 - Journal of Symbolic Logic 76 (1):267 - 288.
Interpreting N in the computably enumerable weak truth table degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.
Interpreting true arithmetic in the local structure of the enumeration degrees.Hristo Ganchev & Mariya Soskova - 2012 - Journal of Symbolic Logic 77 (4):1184-1194.
Interpreting true arithmetic in the [image] degrees.Thomas F. Kent - 2010 - Journal of Symbolic Logic 75 (2):522 - 550.
The theory of the recursively enumerable weak truth-table degrees is undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
The undecidability of the II4 theory for the R. E. wtt and Turing degrees.Steffen Lempp & André Nies - 1995 - Journal of Symbolic Logic 60 (4):1118 - 1136.
The Undecidability of the II$^_4$ Theory for the R. E. Wtt and Turing Degrees.Steffen Lempp & André Nies - 1995 - Journal of Symbolic Logic 60 (4):1118-1136.
Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (3):880-905.
Differences between Resource Bounded Degree Structures.Theodore A. Slaman & Michael~E. Mytilinaios - 2003 - Notre Dame Journal of Formal Logic 44 (1):1-12.
The Hypersimple-Free C.E. WTT Degrees Are Dense in the C.E. WTT Degrees.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (3):361-370.
Automorphisms of the truth-table degrees are fixed on a cone.Bernard A. Anderson - 2009 - Journal of Symbolic Logic 74 (2):679-688.
Review: David Marker, J. Stern, Degrees of Models of True Arithmetic; Julia Knight, Alistair H. Lachlan, Robert I. Soare, Two Theorems on Degrees of Models of True Arithmetic. [REVIEW]Terrence S. Millar - 1987 - Journal of Symbolic Logic 52 (2):562-563.
Hypersimplicity and semicomputability in the weak truth table degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
Truth.Bradley Dowden - 2004 - Internet Encyclopedia of Philosophy.

Analytics

Added to PP
2014-01-16

Downloads
15 (#943,292)

6 months
6 (#510,793)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Interpreting N in the computably enumerable weak truth table degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.
Effective embeddings into strong degree structures.Timothy H. McNicholl - 2003 - Mathematical Logic Quarterly 49 (3):219.

Add more citations

References found in this work

Infima of recursively enumerable truth table degrees.Peter A. Fejer & Richard A. Shore - 1988 - Notre Dame Journal of Formal Logic 29 (3):420-437.

Add more references