{
  "id": "1712.00864",
  "version": "v1",
  "published": "2017-12-04T00:48:13.000Z",
  "updated": "2017-12-04T00:48:13.000Z",
  "title": "Muchnik degrees and cardinal characteristics",
  "authors": [
    "Benoit Monin",
    "André Nies"
  ],
  "categories": [
    "math.LO"
  ],
  "abstract": "We provide a pair of dual results, each stating the coincidence of highness properties from computability theory. We provide an analogous pair of dual results on the coincidence of cardinal characteristics within ZFC. A mass problem is a set of functions on $\\omega$. For mass problems $\\mathcal C, \\mathcal D$, one says that $\\mathcal C$ is Muchnik reducible to $\\mathcal D$ if each function in $\\mathcal D$ computes a function in $\\mathcal C$. In this paper we view highness properties as mass problems, and compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility. Let $\\mathcal D(p)$ be the mass problem of infinite bit sequences $y$ (i.e., 0,1 valued functions) such that for each computable bit sequence $x$, the asymptotic lower density $\\underline \\rho$ of the agreement bit sequence $x \\leftrightarrow y$ is at most $p$ (this sequence takes the value 1 at a bit position iff $x$ and $y$ agree). We show that all members of this family of mass problems parameterized by a real $p$ with $0 < p<1/2 $ have the same complexity in the sense of Muchnik reducibility. This also yields a new version of Monin's affirmative answer to the \"Gamma question\", whether $\\Gamma(A)< 1/2$ implies $\\Gamma(A)=0$ for each Turing oracle $A$. We also show, together with Joseph Miller, that for any order function~$g$ there exists a faster growing order function $h $ such that $\\mathrm{IOE}(g) $ is strictly Muchnik below $\\mathrm{IOE}(h)$. We study cardinal characteristics analogous to the highness properties above. For instance, $\\mathfrak d (p)$ is the least size of a set $G$ of bit sequences so that for each bit sequence $x$ there is a bit sequence $y$ in $G$ so that $\\underline \\rho (x \\leftrightarrow y) >p$. We prove within ZFC all the coincidences of cardinal characteristics that are the analogs of the results above.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-12-04T00:48:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D30",
      "03E17"
    ],
    "keywords": [
      "mass problem",
      "muchnik degrees",
      "muchnik reducibility",
      "dual results",
      "faster growing order function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}