Open Problems in Mathematical Logic — Problem 48

Definitions and mathematical statement

For a tree $T$, write $[T]$ for its set of paths: a path belongs to $[T]$ when each of its finite initial segments belongs to $T$, using the source's intended coding and notion of path. The supplied record does not specify the alphabet of the tree or whether paths and initial segments are interpreted internally or externally to the model $M$.

The notation $\Pi^0_1(\emptyset')$ denotes the first universal level of the arithmetical hierarchy relative to the halting oracle $\emptyset'$. Its interpretation "in $M$" requires an intended internal oracle and definability convention, which the record does not specify. The scheme $\mathrm{B}\Sigma_2$ is bounding for $\Sigma_2$ formulas: for each such formula $\varphi(x,y,\bar p)$ in the relevant language, it asserts the universal closure of \[ \left(\forall x<a\,\exists y\,\varphi(x,y,\bar p)\right) \;\Longrightarrow\; \exists b\,\forall x<a\,\exists y<b\,\varphi(x,y,\bar p). \] The relevant language and permitted parameters depend on the intended meaning of $M[g]$.

Question as supplied. Let $T$ be a tree that is $\Pi^0_1(\emptyset')$ in $M$. Suppose \[ \exists g\in[T]\;\left(M[g]\models\mathrm{B}\Sigma_2\right). \] Must there exist a definable path $h\in[T]$ such that \[ M[h]\models\mathrm{B}\Sigma_2\,? \] Here $M[g]$ and $M[h]$ retain the source notation for the structures obtained by adjoining the respective paths; the construction is not specified in the supplied record. Likewise, "definable" retains the source wording: the structure over which definability is required, the formula complexity, and the permitted parameters are unspecified. No base theory or other hypotheses on $M$ are supplied. Thus this is a transcription of the question with its unresolved qualifications, rather than a fully determined assertion about a specified class of models.

Short English statement

If a tree of complexity $\Pi^0_1(\emptyset')$ in $M$ has a path whose adjunction yields a structure satisfying $\Sigma_2$ bounding, must it have a definable path with the same property? The model assumptions, tree domain, meaning of adjunction, and intended definability require clarification.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $801036$, exact source code catalogue entry, titled Open Problems in Mathematical Logic --- Problem 48; collection: AMR Open Problem Lists. The registry labels the problem open; this is a supplied status, not an independently verified mathematical assessment.
• Supplied attribution: Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 48. Supplied source URL: https://arxiv.org/abs/2608.26628. The record's proposer field also names Barmpalias, Gao et al.; no separate attribution to an original proposer is supplied.
• Supplied provenance: accessed 2026-10-16; extraction method arxiv_latex; upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. These are supplied provenance details, not a claim of independent source access or verification.