Open Problems in Mathematical Logic — Problem 1 (Levin, private communications)

Definitions and mathematical statement

For a conventional degree-theoretic transcription, represent reals by elements of $2^{{\mathbb{N}}}$. Write $x\leq_T y$ when $x$ is computable with oracle $y$, and write $\deg_T(x)$ for the Turing degree of $x$. Let $\mathcal D_T$ be the partially ordered set of Turing degrees. Let $\mathcal R\subseteq 2^{{\mathbb{N}}}$ denote the intended class of random reals, and put \[ \mathcal D_{\mathcal R}=\{\deg_T(x):x\in\mathcal R\}. \] The source does not specify the randomness notion defining $\mathcal R$; this parameter remains unresolved.

A chain is a subset $C\subseteq\mathcal D_T$ such that any two members are comparable under $\leq_T$. A Turing ideal is a nonempty subset of $\mathcal D_T$ that is downward closed under $\leq_T$ and closed under finite joins. Here $\mathbf a\vee\mathbf b$ is the least upper bound of the two degrees, represented by the interleaving of representatives. For $S\subseteq\mathcal D_T$, write \[ \langle S\rangle_T =\left\{\mathbf d\in\mathcal D_T: \exists\text{ finite }F\subseteq S\quad \mathbf d\leq_T\bigvee F\right\}, \] where the empty join is the computable degree. Thus an ideal generated by random reals has the form $\langle S\rangle_T$ for some $S\subseteq\mathcal D_{\mathcal R}$.

Fix a computable bijection $\pi:{\mathbb{N}}\times{\mathbb{N}}\to{\mathbb{N}}$. For $y\in2^{{\mathbb{N}}}$, its $n$th column is the real $y_n$ given by $y_n(k)=y(\pi(n,k))$.

1. The first source question asks whether every chain of random reals in the Turing degrees can be combined into a single random real. If "combined" means that the resulting random real computes a representative of every degree in the chain, the unrestricted formulation would be \[ \forall C\subseteq\mathcal D_{\mathcal R}\quad \left[C\text{ is a chain}\ \Longrightarrow\ \exists y\in\mathcal R\ \forall\mathbf d\in C\quad \mathbf d\leq_T\deg_T(y)\right]. \] This is a conditional interpretation: the source does not define "combined" or state whether chains are required to be countable.
2. The second source question asks whether every Turing ideal generated by random reals can be generated by the columns of a single random real. With the conventions above, its unrestricted formulation would be \[ \forall S\subseteq\mathcal D_{\mathcal R}\quad \exists y\in\mathcal R\quad \langle S\rangle_T =\left\langle\{\deg_T(y_n):n\in{\mathbb{N}}\}\right\rangle_T. \] The source does not state whether only countably generated ideals are intended. The displayed quantification over arbitrary $S$ records an unrestricted reading, pending clarification.

Both questions require a specified randomness notion and confirmation of the intended quantifier scopes before these conditional transcriptions can be treated as definitive mathematical statements.

Short English statement

The questions attributed to Levin ask whether a chain of random Turing degrees can be combined into one random real, and whether every ideal generated by random reals is generated by the columns of one random real. The meaning of randomness, the meaning of "combined", and possible countability restrictions remain unspecified.

Sources

• Local UnsolvedMath registry: supplied complete source record, permanent ID $800989$, exact source problem code catalogue entry, upstream ID $800989$, upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. The registry labels the record open; this is a supplied status label, not an independently verified mathematical assessment.
• Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 1, https://arxiv.org/abs/2608.26628. The supplied provenance records access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance details, not a claim of independent access or verification.
• Attribution/context supplied in the record: Levin, private communications. The registry lists Barmpalias, Gao et al. in its proposer field and 2026 as its proposed year. No separate public reference for Levin's private communications is supplied.