Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes (Q409326): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.apal.2011.10.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2071777661 / rank | |||
Normal rank |
Revision as of 01:12, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes |
scientific article |
Statements
Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes (English)
0 references
13 April 2012
0 references
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.
0 references
Medvedev degrees
0 references
Muchnik degrees
0 references
true arithmetic
0 references