Coding true arithmetic in the Medvedev degrees of Π10 classes

摘要

Let 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.