Open Problems in Mathematical Logic — Problem 8

Definitions and mathematical statement

Identify a set $A\subseteq{\mathbb{N}}$ with its characteristic sequence in Cantor space $2^{{\mathbb{N}}}$, and put \[ \mathrm{Rec}=\{A\subseteq{\mathbb{N}}:A\text{ is computable}\}. \] A class $C\subseteq 2^{{\mathbb{N}}}$ is $\Pi^0_1$ if there is a computable tree $T\subseteq 2^{<{\mathbb{N}}}$, closed under initial segments, such that \[ C=[T]=\{X\in 2^{{\mathbb{N}}}:\forall n\in{\mathbb{N}}\ (X\upharpoonright n\in T)\}. \] Under the usual convention, an almost disjoint family consists of infinite subsets of ${\mathbb{N}}$, and distinct members have finite intersection. Such a family of recursive sets is maximal among the infinite recursive sets if every infinite recursive set has infinite intersection with some member of the family.

With these conventions, the supplied question has the following precise candidate formulation: does there exist a $\Pi^0_1$ class $C\subseteq 2^{{\mathbb{N}}}$ such that, writing $\mathcal F=C\cap\mathrm{Rec}$, \[ \begin{gathered} |\mathcal F|=\infty,\\ \forall A\in\mathcal F\quad |A|=\infty,\\ \forall A,B\in\mathcal F\quad \bigl(A\ne B\Longrightarrow |A\cap B|<\infty\bigr),\\ \forall R\in\mathrm{Rec}\quad \bigl(|R|=\infty\Longrightarrow \exists A\in\mathcal F\ (|R\cap A|=\infty)\bigr)? \end{gathered} \] The requirement that every member of $\mathcal F$ be infinite makes explicit the usual almost disjoint family convention. The supplied record does not state that convention or explicitly specify Cantor space as the ambient space. Consequently, this formulation is conditional on those interpretations; in particular, it does not replace $C\cap\mathrm{Rec}$ by only its infinite members.

The record also supplies the separate display \[ A\le_{SJT}B \quad\Longleftrightarrow\quad \forall Y\, \left((Y\text{ is }\omega\text{-c.a.}\ \land\ Y\in\mathrm{MLR}) \Longrightarrow A\le_T B\oplus Y\right). \] For its standard reading with $A,B,Y\subseteq{\mathbb{N}}$, $\le_T$ denotes Turing reducibility and \[ B\oplus Y=\{2n:n\in B\}\cup\{2n+1:n\in Y\}. \] A set $Y$ is $\omega$-computably approximable if there are computable functions $y:{\mathbb{N}}\times{\mathbb{N}}\to\{0,1\}$ and $b:{\mathbb{N}}\to{\mathbb{N}}$ such that, for every $n$, \[ \lim_{s\to\infty}y(n,s)=\mathbf 1_Y(n),\qquad \left|\{s:y(n,s+1)\ne y(n,s)\}\right|\le b(n). \] Under the usual unrelativized interpretation, $\mathrm{MLR}$ is the class of Martin--Löf random binary sequences for the fair-coin measure $\mu$: a sequence belongs to this class if it avoids $\bigcap_n U_n$ for every uniformly effectively open sequence $(U_n)_{n\in{\mathbb{N}}}$ with $\mu(U_n)\le 2^{-n}$. The source does not explain how its displayed relation $\le_{SJT}$ relates to the question about $C$, nor explicitly specify the domains or randomness convention. The display is therefore retained separately and supplies no additional hypothesis on $C$ in the candidate formulation above.

Short English statement

The question asks for an effectively closed class with infinitely many computable members whose computable members form a maximal almost disjoint family. Under the usual convention, all those members must be infinite, distinct members must intersect finitely, and every infinite computable set must intersect some member infinitely. The supplied $\le_{SJT}$ display has no stated connection to this question. The registry labels the problem open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, permanent ID $800996$, exact source problem code catalogue entry; title: Open Problems in Mathematical Logic --- Problem 8. Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Supplied source attribution: Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 8, https://arxiv.org/abs/2608.26628. The registry also records Barmpalias, Gao et al. in its proposer field and gives proposed year 2026; the supplied excerpt does not distinguish compilation authorship from original problem attribution.
• Supplied provenance: accessed 2026-10-16; extraction method arxiv_latex. The registry record was created and updated on 2026-10-16 and labels the problem open. These are supplied provenance and status statements, not independently verified source access or a verified literature assessment.