Arithmetic, First-Order Logic, and Counting Quantifiers

Details Arithmetic, First-Order Logic, and Counting Quantifiers Arithmetic, First-Order Logic, and Counting Quantifiers

2002-11-19

arxiv.org/abs/cs/0211022v1

Computer Science

Logic in Computer Science

39 pages, 5 figures

Scientific paper

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 (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.

Affiliated with

Also associated with

No associations

Rating

Arithmetic, First-Order Logic, and Counting Quantifiers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Arithmetic, First-Order Logic, and Counting Quantifiers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic, First-Order Logic, and Counting Quantifiers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-241239