Coding true arithmetic in the Medvedev degrees of Π10 classes

AbstractLet Es denote the lattice of Medvedev degrees of non-empty Π10 subsets of 2ω, and let Ew denote the lattice of Muchnik degrees of non-empty Π10 subsets of 2ω. We prove that the first-order theory of Es as a partial order is recursively isomorphic to the first-order theory of true arithmetic. Our coding of arithmetic in Es also shows that the Σ30-theory of Es as a lattice and the Σ40-theory of Es as a partial order are undecidable. Moreover, we show that the degree of Es as a lattice is 0‴ in the sense that 0‴ computes a presentation of Es and that every presentation of Es computes 0‴. Finally, we show that the Σ30-theory of Ew as a lattice and the Σ40-theory of Ew as a partial order are undecidable