Open Problems in Mathematical Logic — Problem 9

Definitions and mathematical statement

The supplied record asks for a classification of quantifier patterns at the fourth level of the arithmetical hierarchy. Write $\mathcal P_{\Sigma^0_4}$ and $\mathcal P_{\Pi^0_4}$ for the source-intended collections of $\Sigma^0_4$ and $\Pi^0_4$ quantifier patterns, respectively. These symbols are placeholders: the supplied record does not define what constitutes a quantifier pattern or specify the relations denoted by $\equiv_m$ and $\equiv_{dm}$.

Provided the intended collections and equivalence relations are specified, write \[ [P]_{\sim}=\{Q\in\mathcal P:Q\sim P\},\qquad \mathcal P/{\sim}=\{[P]_{\sim}:P\in\mathcal P\}. \] The requested problems are:

1. Determine the number of $\equiv_m$-equivalence classes of $\Sigma^0_4$ quantifier patterns, namely \[ \left|\mathcal P_{\Sigma^0_4}/{\equiv_m}\right|. \]
2. Determine the number of $\equiv_m$-equivalence classes of $\Pi^0_4$ quantifier patterns, namely \[ \left|\mathcal P_{\Pi^0_4}/{\equiv_m}\right|. \]
3. Determine the number of $\equiv_{dm}$-equivalence classes of $\Sigma^0_4$ quantifier patterns, namely \[ \left|\mathcal P_{\Sigma^0_4}/{\equiv_{dm}}\right|. \]

No finiteness assumption is supplied. The meanings of the pattern collections and both equivalence relations must be recovered from the source before these questions have a fully specified mathematical interpretation. In particular, no interpretation of the subscripts $m$ or $dm$ is imposed here.

Short English statement

Determine how many equivalence classes the fourth-level arithmetical quantifier patterns have: for $\Sigma^0_4$ and $\Pi^0_4$ under $\equiv_m$, and for $\Sigma^0_4$ under $\equiv_{dm}$. The supplied excerpt does not define the patterns or the equivalence relations, so this draft retains those unresolved source-dependent terms.

Sources

• Local UnsolvedMath registry, permanent ID $800997$, exact source problem code catalogue entry, titled Open Problems in Mathematical Logic --- Problem 9. The supplied registry labels the problem open; this is a supplied status, not an independently verified mathematical assessment.
• Supplied source attribution: Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 9, https://arxiv.org/abs/2608.26628. The registry also lists Barmpalias, Gao et al. in its proposer field, with proposed year 2026; the excerpt does not distinguish collection authorship from original proposal attribution.
• Supplied provenance: source accessed 2026-10-16; extraction method arxiv_latex; upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. The access date and provenance are supplied metadata; no independent source visit or verification is asserted.