Open Problems in Mathematical Logic — Problem 47

Definitions and mathematical statement

Let $M$ be a model of \[ \mathrm{RCA}_0+\mathrm{B}\Sigma_n+\neg\mathrm{I}\Sigma_n, \] and let $D$ denote its number domain (also denoted by $M$ in the source). Here $\mathrm{RCA}_0$ is the usual base theory of recursive comprehension, $\mathrm{B}\Sigma_n$ is the bounding scheme for $\Sigma_n$ formulas, and $\mathrm{I}\Sigma_n$ is the induction scheme for $\Sigma_n$ formulas. The negated induction assumption means that the induction scheme fails in the model. The source does not specify the value or range of $n$.

Fix a $\Pi_n$-definable subset $X\subseteq D$. Suppose that $\langle A_s:s\in D\rangle$ is a sequence of pairwise disjoint $M$-finite subsets of $D$, with \[ \forall s,t\in D\;\left(s\ne t\Longrightarrow A_s\cap A_t=\varnothing\right) \quad\text{and}\quad \forall s\in D\;\left(A_s\cap X\ne\varnothing\right). \] Here $M$-finite is understood in its usual internal sense: each set is represented in the model as finite, possibly with nonstandard finite size. The source does not specify the coding convention.

Question. For every model, subset, and sequence satisfying these hypotheses, does there exist a total function \[ f:D\longrightarrow D \] whose graph is definable in $M$ and which satisfies \[ \forall s\in D\qquad f(s)\in A_s\cap X\,? \] Definability of the graph means that a formula in the intended language of $M$, with whatever parameters are permitted, defines exactly one output for every input. No bound on the complexity of this formula is stated.

Unresolved qualifications. The supplied statement does not specify whether parameters are allowed in the definitions of $X$ or $f$, which parameters would be allowed, or the language in which definability is intended. It also does not specify whether the sequence is internally coded, uniformly definable, part of the second-order structure, or an arbitrary externally given family. These conventions, together with the intended range of $n$, must be fixed before this becomes a fully determined formal assertion.

Short English statement

For a model satisfying the stated bounding and induction-failure assumptions, suppose a $\Pi_n$ set meets every member of a pairwise disjoint family of internally finite sets. Must there be a function definable in the model that selects an element of each intersection? The range of $n$, the representation of the family, and the permitted definability parameters remain unspecified.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $801035$, source code catalogue entry, title "Open Problems in Mathematical Logic --- Problem 47." The registry attributes the record to Barmpalias, Gao et al., with proposed year $2026$, and labels its status as open. This is a supplied status label, not an independently verified assessment.
• Supplied source attribution: Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 47, 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; the source and its contents have not been independently checked here.