Counting quantification: Difference between revisions

Revision as of 20:34, 4 September 2020

Revision as of 15:39, 21 September 2020

Line 1:

A '''counting quantifier''' is a [[Mathematics|mathematical]] term for a [[Quantifier (logic)|quantifier]] of the form "there exists at least ''k'' elements that satisfy property ''X''".

A '''counting quantifier''' is a [[Mathematics|mathematical]] term for a [[Quantifier (logic)|quantifier]] of the form "there exists at least ''k'' elements that satisfy property ''X''", sometimes denoted by <math>\exists_{\ge k}\, x</math>.<ref>{{Cite web|date=2020-04-06|title=Comprehensive List of Logic Symbols|url=https://mathvault.ca/hub/higher-math/math-symbols/logic-symbols/|access-date=2020-09-04|website=Math Vault|language=en-US}}</ref> 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.<ref>{{Cite web|last=Cohen|first=Mark|date=2004|title=Chapter 14: More on Quantification|url=https://faculty.washington.edu/smcohen/120/Chapter14.pdf|url-status=live|archive-url=|archive-date=|access-date=September 4, 2020|website=faculty.washington.edu}}</ref><ref>{{Cite web|last=Helman|first=Glen|date=August 1, 2013|title=8.3. Numerical quantification|url=http://persweb.wabash.edu/facstaff/helmang/phi270-1314F/phi270PDF/phi270text/phi270txt8/phi270txt83/phi270txt83(4up).pdf|url-status=live|archive-url=|archive-date=|access-date=September 4, 2020|website=persweb.wabash.edu}}</ref> However, they are interesting in the context of logics such as [[two-variable logic with counting]], which restrict the number of variables in formulas.

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]] that 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]]

== References ==

<references />

== 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. [http://www-mgi.informatik.rwth-aachen.de/Publications/pub/graedel/gorc2.ps Postscript file] {{oclc|282402933}}