Coding true arithmetic in the Medvedev degrees of classes

Let Es denote the lattice of Medvedev degrees of non-empty subsets of 2ω, and let Ew denote the lattice of Muchnik degrees of non-empty 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 -theory of Es as a lattice and the -theory of Es as a partial order are undecidable. Moreover, we show that the degree of Es as a lattice is in the sense that computes a presentation of Es and that every presentation of Es computes . Finally, we show that the -theory of Ew as a lattice and the -theory of Ew as a partial order are undecidable.