Comparing the degrees of enumerability and the closed Medvedev degrees
The set $A$ is enumeration reducible to the set $B$ ($A \leq_e B$) if there is an effective procedure by which, given any enumeration of $B$, an enumeration of $A$ can be produced. This relation generates the enumeration degrees. A mass problem $A$ is a subset of $\omega^\omega$. In Hartley Rogers' words, ``it is a collection of functions any one of which can `solve' the `problem' and at least one of which can be obtained from any `solution' to the `problem'. Mass problems are ordered by $A \leq_s B$, which holds iff from any given member of $B$ a member of $A$ can be computed. This relation generates the degrees of difficulty, or Medvedev degrees, a bounded distributive lattice. A Medvedev degree is closed iff it is the degree of a closed subset of $\omega^\omega$. The degrees of solvability are among the enumeration degrees, which in turn can be embedded in the closed Medvedev degrees. Let $\mathcal{E}_A$ be the set of functions with range $A$, the ``problem of enumerability of $A$. Then $A \leq_e B$ iff $\mathcal{E}_A \leq_s \mathcal{E}_B$, where $e$ and $s$ order the degrees of enumerability and Medvedev degrees, respectively. Further: ``There are nonzero degrees that do not bound nonzero closed degrees, and there are degrees that are nontrivially both degrees of enumerability and closed (Medvedev) degrees.
- Comparing the Medvedev and Turing degrees of \(\Pi^{0}_{1}\) classes
- scientific article; zbMATH DE number 1531937
- A Note on Closed Degrees of Difficulty of the Medvedev Lattice
- Theory and Applications of Models of Computation
- Enumeration Degrees and Enumerability of Familes
- scientific article; zbMATH DE number 1048046
- The -Enumeration Degrees
- Enumeration degrees and topology
- The \(n\)-rea enumeration degrees are dense
- Comparisons for numbers of complete mappings
- 1-genericity in the enumeration degrees
- A faithful interpretation of the intuitionistic propositional calculus by means of an initial segment of the Medvedev lattice
- A Note on Closed Degrees of Difficulty of the Medvedev Lattice
- A survey of Mučnik and Medvedev degrees
- Cototal enumeration degrees and their applications to effective mathematics
- Descriptive set theory
- Embedding Brouwer algebra in the Medvedev lattice
- scientific article; zbMATH DE number 3501559 (Why is no real title available?)
- scientific article; zbMATH DE number 3548956 (Why is no real title available?)
- scientific article; zbMATH DE number 841094 (Why is no real title available?)
- scientific article; zbMATH DE number 3264932 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3110190 (Why is no real title available?)
- Mass Problems and Randomness
- Natural factors of the Medvedev lattice capturing IPC
- On cototality and the skip operator in the enumeration degrees
- On some filters and ideals of the Medvedev lattice
- Some remarks on the algebraic structure of the Medvedev Lattice
- Topological aspects of the Medvedev lattice
- ∏ 0 1 Classes and Degrees of Theories
This page was built for publication: Comparing the degrees of enumerability and the closed Medvedev degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2312080)
