Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes (Q701736)

This paper deals with Medvedev reducibility, as well as a weaker reducibility due to Muchnik. In both cases, if one restricts the reducibility to nonempty \(\Pi^0_1\) classes, the resulting degrees constitute a countable distributive lattice. The authors show that for the Muchnik version, the free countable Boolean algebra (and hence any countable distributive lattice) is embeddable into the lattice below any nonzero element. They conjecture that the same holds for the Medvedev version and prove that the free countable distributive lattice (and hence any finite distributive lattice) is so embeddable.