Interpreting true arithmetic in the theory of the r.e. truth table degrees
André Nies, Richard A. Shore · Annals of Pure and Applied Logic · 1995
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.