INTERPRETING TRUE ARITHMETIC IN THE THEORY OF THE RE TRUTH TABLE DEGREES

Authors
NIES A SHORE RA
Citation
A. Nies et Ra. Shore, INTERPRETING TRUE ARITHMETIC IN THE THEORY OF THE RE TRUTH TABLE DEGREES, Annals of pure and applied Logic, 75(3), 1995, pp. 269-311
Citations number
18
Categorie Soggetti
Mathematics, Pure",Mathematics,Mathematics,Mathematics
Journal title
Annals of pure and applied Logic → ACNP
ISSN journal
01680072
Volume
75
Issue
3
Year of publication
1995
Pages
269 - 311
Database
ISI
SICI code
0168-0072(1995)75:3<269:ITAITT>2.0.ZU;2-L
Abstract
We show that the elementary theory of the recursively enumerable tt-de grees has the same computational complexity as true first-order arithm etic. As auxiliary results, we prove theorems about exact pairs and in itial segments in the tt-degrees.