A Survey of Muchnik and Medvedev degrees

2010/07/14 by Hinman, Peter G.
#03D25 #03D30 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1007.2376

Abstract

We survey the theory of Muchnik (weak) and Medvedev (strong) degrees of subsets of ^ωω with particular attention to the degrees of Π⁰₁ subsets of ^ω2. Later sections present proofs, some more complete than others, of the major results of the subject.

Related

• Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions
• Medvedev degrees of two-dimensional subshifts of finite type
• Intuitionistic Logic and Muchnik Degrees
• Comparing the degrees of enumerability and the closed Medvedev degrees
• Strong reducibilities and set theory