Arithmetic, First-Order Logic, and Counting Quantifiers
| dc.creator | Schweikardt, Nicole | |
| dc.date | 2002-11-19 | |
| dc.date.accessioned | 2026-07-07T03:19:01Z | |
| dc.date.available | 2026-07-07T03:19:01Z | |
| dc.description | 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. | |
| dc.description | 39 pages, 5 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0211022 | |
| dc.identifier | http://arxiv.org/abs/cs/0211022 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31348 | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.4.1 | |
| dc.title | Arithmetic, First-Order Logic, and Counting Quantifiers | |
| dc.type | text |