Open Problems in Mathematical Logic — Problem 10

Definitions and mathematical statement

Let $\Sigma=\{\exists,\forall,\exists^\infty,\forall^\infty\}$ be the alphabet of quantifier symbols displayed in the source, and let $\Sigma^{<\omega}=\bigcup_{n\in{\mathbb{N}}}\Sigma^n$ denote its finite words, including the empty word. A quantifier pattern is a word $\overline P\in\Sigma^{<\omega}$.

The supplied problem asks whether there is a decision procedure which, on every input pair $(\overline P,\overline Q)\in(\Sigma^{<\omega})^2$, halts and answers yes exactly when \[ \langle\overline P\rangle\leq_m\langle\overline Q\rangle. \] Equivalently, under the intended interpretations of the displayed notation, is the set \[ \left\{(\overline P,\overline Q)\in(\Sigma^{<\omega})^2: \langle\overline P\rangle\leq_m\langle\overline Q\rangle\right\} \] decidable?

Unresolved qualifications. The supplied record does not define the objects $\langle\overline P\rangle$, the relation $\leq_m$, the domains over which the quantifiers range, or the semantics of $\exists^\infty$ and $\forall^\infty$. It also gives no interpretation of the empty pattern. Consequently, this expresses the requested decision problem formally but does not determine its underlying mathematical relation. Those definitions must be recovered from the source context before a complete mathematical formulation is possible.

Short English statement

Given two finite patterns built from the four displayed quantifier symbols, can an algorithm always decide the comparison $\langle\overline P\rangle\leq_m\langle\overline Q\rangle$? The record leaves the interpretation of this comparison unspecified. It labels the problem open; that label is supplied metadata, not an independently verified assessment.

Sources

• Local UnsolvedMath registry: permanent ID $800998$, exact source problem code catalogue entry; title: Open Problems in Mathematical Logic --- Problem 10.
• Supplied source attribution: Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 10. Supplied reference: https://arxiv.org/abs/2608.26628. The registry also attributes the proposal to Barmpalias, Gao et al., with proposed year 2026; no more specific individual attribution is supplied.
• Provenance supplied by the registry: accessed 2026-10-16; extraction method arxiv_latex; upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. The access date and provenance are supplied records and have not been independently verified here.