×
Shafer, Paul

Coding true arithmetic in the Medvedev and Muchnik degrees. (English) Zbl 1222.03049

J. Symb. Log. 76, No. 1, 267-288 (2011).
The author proves that the first-order theories of the Medvedev degrees and the Muchnik degrees are recursively isomorphic to the third-order theory of true arithmetic. Further, the author proves that the first-order theories of the closed Medvedev degrees and of the compact Medvedev degrees are recursively isomorphic to the second-order theory of true arithmetic. At last, it is proved that neither the closed Medvedev degrees nor the compact Medvedev degrees are elementarily equivalent to either the closed Muchnik degrees or the compact Muchnik degrees.
Reviewer: Marat M. Arslanov (Kazan)

Cited in 5 Documents

MSC:

03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03C57 Computable structure theory, computable model theory
03C62 Models of arithmetic and set theory
03C85 Second- and higher-order model theory
03D30 Other degrees and reducibilities in computability and recursion theory

Keywords:

Medvedev degrees; Muchnik degrees; reducibilities; true arithmetic; first-order theory
PDF BibTeX XML Cite
\textit{P. Shafer}, J. Symb. Log. 76, No. 1, 267--288 (2011; Zbl 1222.03049)
Full Text: DOI

References:

[1] DOI: 10.1002/malq.19910370905 · Zbl 0702.03021
[2] DOI: 10.1016/j.apal.2008.03.002 · Zbl 1156.03026
[3] Doklady Akademii Nauk SSSR (NS) 104 pp 501– (1955)
[4] 5th Conference on Computability in Europe, CiE 2009 5635 pp 324– (2009)
[5] Degrees of unsolvability (1983) · Zbl 0542.03023
[6] DOI: 10.1070/IM1968v002n05ABEH000690 · Zbl 0187.26306
[7] A shorter model theory (1997) · Zbl 0873.03036
[8] Matematicheskie Zametki 28 pp 899– (1980)
[9] Computability, enumerability, unsolvability: Directions in recursion theory 224 pp 289– (1996)
[10] DOI: 10.1070/SM1976v030n03ABEH002277 · Zbl 0382.03028
[11] DOI: 10.1002/malq.19960420111 · Zbl 0845.03020
[12] Some remarks on the algebraic structure of the Medvedev lattice 55 pp 831– (1990) · Zbl 0703.03022
[13] Recursively enumerable sets and degrees (1987)
[14] Sibirskii Matematicheskii Zhurnal 29 pp 171– (1988)
[15] Subsystems of second order arithmetic (2009) · Zbl 1181.03001
[16] DOI: 10.2307/1971028 · Zbl 0349.02035
[17] Journal of the London Mathematical Society 24 pp 1– (1981)
[18] Notre Dame Journal of Formal Logic
[19] DOI: 10.1112/S002461159800046X · Zbl 0904.03028
[20] Sibirskii Matematkheskii Zhurnal 4 pp 1328– (1963)
[21] Doklady Akademii Nauk SSSR (NS) 142 pp 1015– (1962)
[22] DOI: 10.1305/ndjfl/1093635751 · Zbl 0737.06009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.