Open Problems in Mathematical Logic — Problem 30

Definitions and mathematical statement

Write $\omega=\{0,1,2,\ldots\}$. For a tree $T$, let $[T]$ denote its set of infinite paths. The supplied record does not specify the ambient class of trees or define the adjective "positive." Accordingly, retain $\operatorname{Pos}(T)$ as an unresolved predicate expressing the source's intended positivity condition. With these qualifications, the supplied principle is \[ P^-:\quad \forall T\,\left(\operatorname{Pos}(T)\ \longrightarrow\ \exists (X_n)_{n\in\omega}\,\left[(\forall n\in\omega\;X_n\in[T])\ \land\ (\forall m,n\in\omega\;(m\ne n\longrightarrow X_m\ne X_n))\right]\right). \] Here the existential quantifier asks for a single sequence of pairwise distinct paths. Its precise coding in second-order arithmetic depends on the missing source definitions.

The target question is whether \[ \mathrm{RCA}_0\vdash (P^-\longrightarrow P), \] where $\mathrm{RCA}_0$ is the usual recursive comprehension base theory of second-order arithmetic. Crucially, the supplied excerpt does not define $P$; it also uses an undefined principle $P^+$. Thus this is an explicitly incomplete formulation of the intended provability question, and no definition of either principle is inferred here.

For context, the supplied excerpt reports the following relationships: \[ \mathrm{WKL}_0\vdash P^+, \] \[ \mathrm{RCA}_0\vdash P^+\to P\to P^-\to\mathrm{1\text{-}RAN}\leftrightarrow\mathrm{WWKL}_0, \] and \[ P^+\nvdash\mathrm{WKL}_0,\qquad \mathrm{RCA}_0\nvdash(P\to P^+),\qquad \mathrm{RCA}_0\nvdash(\mathrm{1\text{-}RAN}\to P^-). \] Here $\mathrm{WKL}_0$ and $\mathrm{WWKL}_0$ denote the usual weak and weak weak König's lemma systems. These displays preserve the source's notation and are supplied background claims, not independently verified assertions. The excerpt glosses $\mathrm{1\text{-}RAN}$ as "there exists a 1-random," but does not specify its relativization or formal quantifiers. It also does not specify the background theory implicit in $P^+\nvdash\mathrm{WKL}_0$. These omissions must be resolved before the background relationships or the target can receive a fully precise formal interpretation.

Short English statement

The supplied question asks whether $\mathrm{RCA}_0$ proves that every positive tree having a sequence of pairwise distinct infinite paths, as expressed by $P^-$, implies the principle $P$. The excerpt does not define $P$ or positivity, so the intended implication cannot yet be stated completely. The registry labels the problem open; this is a supplied status, not an independently verified assessment.

Sources

• Local UnsolvedMath registry: supplied complete record with permanent ID $801018$, exact source problem code catalogue entry, title "Open Problems in Mathematical Logic --- Problem 30," in the AMR Open Problem Lists collection, Logic category. The registry attributes the record to Barmpalias, Gao et al., gives proposed year 2026, and labels its status open.
• Supplied source attribution: Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 30, https://arxiv.org/abs/2608.26628. The source metadata reports access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance details; the source and its mathematical claims have not been independently checked here.