Comparing the degrees of enumerability and the closed Medvedev degrees (Q2312080)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Comparing the degrees of enumerability and the closed Medvedev degrees
scientific article

    Statements

    Comparing the degrees of enumerability and the closed Medvedev degrees (English)
    0 references
    0 references
    0 references
    4 July 2019
    0 references
    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.''
    0 references
    0 references
    Medvedev degrees
    0 references
    enumeration degrees
    0 references
    0 references
    0 references
    0 references