On some properties of the Medvedev lattice
Abstract
This article investigates the structure of the lattice of degrees of difficulty, introduced by Medvedev. In particular, an answer is given to Rogers' question: Is being a degree of solvability a lattice-theoretic property? It is proved that for every degree except the smallest, the smallest nonrecursive, and the largest degrees, there exists a degree not comparable with it. Also analyzed are conditions under which there are no degrees lying strictly between two given degrees. The final consideration is a topological approach to certain questions about the structure of the Medvedev lattice. Bibliography: 2 titles.
Submission history
[v1] 1976