Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes

DOI10.1016/j.apal.2011.10.002zbMath1243.03059OpenAlexW2071777661MaRDI QIDQ409326

Paul Shafer

Publication date: 13 April 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.10.002

zbMATH Keywords

Muchnik degreesMedvedev degreestrue arithmetic

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) First-order arithmetic and fragments (03F30) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Effectively closed mass problems and intuitionism
• Topological aspects of the Medvedev lattice
• Characterizing the join-irreducible Medvedev degrees
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• Mass problems associated with effectively closed sets
• Effectively closed sets and enumerations
• First-order theory of the degrees of recursive unsolvability
• Density of the Medvedev lattice of \(\Pi^0_1\) classes
• The recursively enumerable degrees are dense
• Initial segments of the degrees of unsolvability
• On the degrees less than 0'
• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• A Survey of Mučnik and Medvedev Degrees
• Coding true arithmetic in the Medvedev and Muchnik degrees
• Degree Structures: Local and Global Investigations
• Non-branching degrees in the Medvedev lattice of Π₁⁰ classes
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• MASS PROBLEMS AND HYPERARITHMETICITY
• The First Order Theories of the Medvedev and Muchnik Lattices
• Interpretability and Definability in the Recursively Enumerable Degrees
• The Theory of the Degrees below 0 ′
• ON SOME PROPERTIES OF THE MEDVEDEV LATTICE
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• A splitting theorem for the Medvedev and Muchnik lattices
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• A Note on Closed Degrees of Difficulty of the Medvedev Lattice
• An extension of the recursively enumerable Turing degrees
• ∏ 0 1 Classes and Degrees of Theories
• Recursive Enumerability and the Jump Operator