Arithmetic, First-Order Logic, and Counting Quantifiers
<|reference_start|>Arithmetic, First-Order Logic, and Counting Quantifiers: This paper gives a thorough overview of what is known about first-order logic with counting quantifiers and with arithmetic predicates. As a main theorem we show that Presburger arithmetic is closed under unary counting quantifiers. Precisely, this means that for every first-order formula phi(y,z_1,...,z_k) over the signature {<,+} there is a first-order formula psi(x,z_1,...,z_k) which expresses over the structure <Nat,<,+> (respectively, over initial segments of this structure) that the variable x is interpreted exactly by the number of possible interpretations of the variable y for which the formula phi(y,z_1,...,z_k) is satisfied. Applying this theorem, we obtain an easy proof of Ruhl's result that reachability (and similarly, connectivity) in finite graphs is not expressible in first-order logic with unary counting quantifiers and addition. Furthermore, the above result on Presburger arithmetic helps to show the failure of a particular version of the Crane Beach conjecture.<|reference_end|>
@article{schweikardt2002arithmetic,,
    title={Arithmetic, First-Order Logic, and Counting Quantifiers},
    author={Nicole Schweikardt},
    journal={arXiv preprint arXiv:cs/0211022},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0211022},
    primaryClass={cs.LO}
}