Title: Muchnik degrees and cardinal characteristics,
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.