Coding true arithmetic in the Medvedev and Muchnik degrees

DOI10.2178/jsl/1294171000zbMath1222.03049OpenAlexW2113097178MaRDI QIDQ3083139

Paul Shafer

Publication date: 18 March 2011

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1294171000

zbMATH Keywords

first-order theoryMuchnik degreesMedvedev degreestrue arithmeticreducibilities

Mathematics Subject Classification ID

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

Related Items

A Survey of Mučnik and Medvedev Degrees, Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism, Degrees of Unsolvability: A Tutorial, Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes, Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intermediate logics and factors of the Medvedev lattice
• First-order theory of the degrees of recursive unsolvability
• Embedding Brouwer algebra in the Medvedev lattice
• Some Quotient Lattices of the Medvedev Lattice
• Some remarks on the algebraic structure of the Medvedev Lattice
• Interpretability and Definability in the Recursively Enumerable Degrees
• ON SOME PROPERTIES OF THE MEDVEDEV LATTICE
• A Note on Closed Degrees of Difficulty of the Medvedev Lattice
• THE CALCULUS OF THE WEAK "LAW OF EXCLUDED MIDDLE"