The MSO counting-logic conjecture for bounded arithmetic

Let MSOϕ()\mathsf{MSO}^\phi(\sharp) be monadic second-order logic with the Härtig quantifier, and call an arithmetical predicate directly definable when it is defined by the logic in the intended coding structure. Let Δ0\Delta_0 denote bounded arithmetic, containing equalities between polynomial terms, Boolean operations, and bounded numerical quantifiers of the form

x<t.φ(x,y),\exists x < t.\,\varphi(x,\mathbf{y}),

where tt is a polynomial term. The MSO counting-logic conjecture. The arithmetical predicates directly definable in MSOϕ()\mathsf{MSO}^\phi(\sharp) can be defined in Δ0\Delta_0. This conjecture asks whether the direct expressive power of the second-order counting extension remains within bounded arithmetic, despite its ability to define all recursively enumerable trace sets; the source provides no resolution.

Sources & referencesView supporting material

Primary source

Johan van Benthem and Thomas Icard, “Interleaving Logic and Counting”, arXiv:2507.05219 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.