Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Counting quantification

Mathematical logical term

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated January 19, 2025

A counting quantifier is a mathematical term for a quantifier of the form "there exists at least k elements that satisfy property 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 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.

01Definition in terms of ordinary quantifiers

Counting quantifiers can be defined recursively in terms of ordinary quantifiers.

Let \exists _{=k} denote "there exist exactly k". Then

{\begin{aligned}\exists _{=0}xPx&\leftrightarrow \neg \exists xPx\\\exists _{=k+1}xPx&\leftrightarrow \exists x(Px\land \exists _{=k}y(Py\land y\neq x))\end{aligned}}

Let \exists _{\geq k} denote "there exist at least k". Then

{\begin{aligned}\exists _{\geq 0}xPx&\leftrightarrow \top \\\exists _{\geq k+1}xPx&\leftrightarrow \exists x(Px\land \exists _{\geq k}y(Py\land y\neq x))\end{aligned}}
Watch videos about Counting quantificationExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Counting quantification”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Uniqueness quantification

In mathematics and logic, the term "uniqueness" refers to the property of being the one and only object satisfying a certain condition. This sort of quantification is known as uniqueness quantification or unique existential quantification, and is often denoted with the symbols "∃!" or "∃=1".

Lindström quantifier

In mathematical logic, a Lindström quantifier is a generalized polyadic quantifier. Lindström quantifiers generalize first-order quantifiers, such as the existential quantifier, the universal quantifier, and the counting quantifiers.

Spectrum of a sentence

In mathematical logic, the spectrum of a sentence is the set of natural numbers occurring as the size of a finite model in which a given sentence is true.