Comparing the degrees of enumerability and the closed Medvedev degrees (Q2312080): Difference between revisions

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.''