MUCHNIK DEGREES AND CARDINAL CHARACTERISTICS
| Autor: | Benoit Monin, André Nies |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | The Journal of Symbolic Logic. 86:471-498 |
| ISSN: | 1943-5886 0022-4812 |
| Popis: | For $p \in [0,1]$ 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 bit sequence $ x \leftrightarrow y$ has asymptotic lower density at most $p$ (where $x \leftrightarrow y$ has a $1$ in position $n$ iff $x(n) = y(n)$). We show that all members of this family of mass problems parameterized by a real $p$ with $0 < p p$ for each computable set~$x$. We prove that the Medvedev (and hence Muchnik) complexity of the mass problems $\mathcal B(p)$ is the same for all $p \in (0, 1/2)$, by showing that they are Medvedev equivalent to the mass problem of functions bounded by $2^{2^ n}$ that are almost everywhere different from each computable function. Together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type $\mathrm{IOE}$: We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above. Updated April 2020, to appear in J. Symb. Logic |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|