Interfacing Logic and Counting
Johan van Benthem, Thomas Icard

Abstract:
Reasoning with generalized quantifiers in natural language combines logical and arithmetical features, transcending divides between qualitative and quantitative. This practice blends with inference patterns in ‘grassroots mathematics’ such as pigeon-hole principles. Our topic is this cooperation of logic and counting, studied with small systems and gradually moving upward. We start with monadic first-order logic with counting. We provide normal forms that allow for axiomatization, determine which arithmetical notions are definable, and conversely, discuss which logical notions can be defined out of arithmetical ones, and what sort of (non-)classical logics are induced. Next we study a series of strengthenings in the same style, including second-order versions, systems with multiple counting, and a new modal logic with counting. As a complement to our fragment approach, we also discuss another way of controlling complexity: changing the semantics of counting to reason about ‘mass’ or other aggregating notions than cardinalities. Finally, we return to natural language, confronting the architecture of our formal systems with linguistic quantifier vocabulary, natural modules such as monotonicity reasoning, and procedural semantics via semantic automata. The paper concludes with some thoughts on on empirical aspects of our findings, further entanglements of logic and counting in the syntax of formal systems, and on rethinking the qualitative/quantitative divide.