Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes (Q409326): Difference between revisions

Let \({\mathcal E}_{s}\) and \({\mathcal E}_{w}\) denote, respectively, the lattice of Medvedev degrees and the lattice of Muchnik degrees of non-empty \(\Pi^{0}_{1}\) subsets of \(2^{\omega}\). It is shown in the paper that (1) the first-order theory of \({\mathcal E}_{s}\) as a partial order is recursively isomorphic to the first-order theory of true arithmetic; (2) the \(\Sigma^{0}_{3}\)-theory of \({\mathcal E}_{s}\) as a lattice and the \(\Sigma^{0}_{4}\)-theory of \({\mathcal E}_{s}\) as a partial order are undecidable; (3) the degree of \({\mathcal E}_{s}\) as a lattice is \({\mathbf 0}'''\) in the sense that \({\mathbf 0}'''\) computes a presentation of \({\mathcal E}_{s}\) and that every presentation of \({\mathcal E}_{s}\) computes \({\mathbf 0}'''\); (4) the \(\Sigma^{0}_{3}\)-theory of \({\mathcal E}_{w}\) as a lattice and the \(\Sigma^{0}_{4}\)-theory of \({\mathcal E}_{w}\) as a partial order are undecidable.