On some properties of the Medvedev lattice
Unknown
Submitted 1976 | SovietRxiv: ru-197601.09698 | Original in English

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

On some properties of the Medvedev lattice