The partial ordering of Medvedev reducibility restricted to the family of Π0 1 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π0 1 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.

Let w and M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π1 0 subsets of 2ω, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of w . We show that many countable distributive lattices are lattice-embeddable below any non-zero element of M.

We study the connection between factors of the Medvedev lattice and constructive logic. The algebraic properties of these factors determine logics lying in between intuitionistic propositional logic and the logic of the weak law of the excluded middle (also known as De Morgan, or Jankov, logic). We discuss the relation between the weak law of the excluded middle and the algebraic notion of join-reducibility. Finally we discuss autoreducible degrees.

This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible (...) ∃-theories. (shrink)