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

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.