Muchnik degrees and cardinal characteristics

Benoit Monin, André Nies

Published 2017-12-04Version 1

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.