# Interleaving Logic and Counting

arXiv: https://arxiv.org/abs/2507.05219 · HTML: https://mlsanity.com/paper/2507.05219/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 118 references that are in the map.
- First posted on arXiv 7 Jul 2025.

## Builds on (most cited first, 4 of 4)

- [Is Causal Reasoning Harder than Probabilistic Reasoning?](https://mlsanity.com/paper/2111.13936/) (2021)
- [A Simple Logic of Functional Dependence](https://mlsanity.com/paper/2103.14946/) (2021)
- [The Modal Logic of Stepwise Removal](https://mlsanity.com/paper/2103.05117/) (2021)
- [Model Theory of Monadic Predicate Logic with the Infinity Quantifier](https://mlsanity.com/paper/1809.03262/) (2018)

## Abstract (arXiv)

Reasoning with quantifier expressions in natural language combines logical and arithmetical features, transcending strict divides between qualitative and quantitative. Our topic is this cooperation of styles as it occurs in common linguistic usage and its extension into the broader practice of natural language plus "grassroots mathematics". We begin with a brief review of first-order logic with counting operators and cardinality comparisons. This system is known to be of high complexity, and drowns out finer aspects of the combination of logic and counting. We move to a small fragment that can represent numerical syllogisms and basic reasoning about comparative size: monadic first-order logic with counting. We provide normal forms that allow for axiomatization, determine which arithmetical notions can be defined on finite and on infinite models, and conversely, we discuss which logical notions can be defined out of purely arithmetical ones, and what sort of (non-)classical logics can be induced. Next, we investigate a series of strengthenings, again using normal form methods. The monadic second-order version is close, in a precise sense, to additive Presburger Arithmetic, while versions with the natural device of tuple counting take us to Diophantine equations, making the logic undecidable. We also define a system that combines basic modal logic over binary accessibility relations with counting, needed to formulate ubiquitous reasoning patterns such as the Pigeonhole Principle. We return to our starting point in natural language, confronting the architecture of our formal systems with linguistic quantifier vocabulary and syntax. We conclude with some general thoughts on yet further entanglements of logic and counting in formal systems, on rethinking the qualitative/quantitative divide, and on connecting our analysis to empirical findings in cognitive science.