Counting quantification

A counting quantifier is a mathematical term for a quantifier of the form "there exists at least k elements that satisfy property X", sometimes denoted by $\exists _{\geq k}\,x$. In first-order logic with equality, counting quantifiers can be defined in terms of ordinary quantifiers, so in this context, they are a notational shorthand. However, they are interesting in the context of logics such as two-variable logic with counting, which restrict the number of variables in formulas. Also, generalized counting quantifiers that say "there exists infinitely many" are not expressible using a finite number of formulas in first-order logic.

See also

• Existential quantification
• Uniqueness quantification
• Lindström quantifier

BIbliography

• Erich Graedel, Martin Otto, and Eric Rosen. "Two-Variable Logic with Counting is Decidable." In Proceedings of 12th IEEE Symposium on Logic in Computer Science LICS `97, Warschau. 1997. Postscript file OCLC 282402933