Fri Dec 3, 2021
Thomas Icard (Stanford University)
Interleaving Logic and Counting
Reasoning with 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, modules such as monotonicity reasoning, and procedural semantics via semantic automata. We conclude with some thoughts on further entanglements of logic and counting in formal systems, on rethinking the qualitative/quantitative divide, and on empirical aspects of our findings. Joint work with Johan van Benthem.