Density of the Medvedev lattice of \(\Pi^0_1\) classes (Q1407612): Difference between revisions

The Medvedev reducibility is a binary relation between sets of infinite binary sequences. One such subset \(P \subseteq \{0,1\}^\omega\) is reducible to another subset \(Q \subseteq \{0,1\}^\omega\) (notation \(P \leq_M Q\)) if there is a partial computable functional \(\Phi\) which maps \(P\) into \(Q\) (thus, given an element of \(Q\), one can find an element of \(P\)). A \(\Pi^0_1\) class \(P \subseteq \{0,1\}^\omega\) is a set that can be viewed as the set of infinite paths in a computable binary tree. This paper studies the lattice of degrees induced by the Medvedev reducibility on the \(\Pi^0_1\) classes of sets. The main result is that the partial ordering \(\leq_M\) is dense. For two disjoint computably enumerable sets, the class of separating sets form a \(\Pi^0_1\) class, called a ``c.e. separating class.'' It is shown that the above density result holds in the sublattice generated by c.e. separating classes.