The MSO counting-logic conjecture for bounded arithmetic
The MSO counting-logic conjecture for bounded arithmetic
Let 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 denote bounded arithmetic, containing equalities between polynomial terms, Boolean operations, and bounded numerical quantifiers of the form
where is a polynomial term. The MSO counting-logic conjecture. The arithmetical predicates directly definable in can be defined in . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.