Market›Counting quantification
Company Profile

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

Definition 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{align} \exists_{= 0} x P x &\leftrightarrow \neg \exists x P x \\ \exists_{= k+1} x P x &\leftrightarrow \exists x (P x \land \exists_{= k} y (P y \land y \neq x)) \end{align} Let \exists_{\geq k} denote "there exist at least k". Then :\begin{align} \exists_{\geq 0} x P x &\leftrightarrow \top \\ \exists_{\geq k+1} x P x &\leftrightarrow \exists x (P x \land \exists_{\geq k} y (P y \land y \neq x)) \end{align} == See also ==
Source: Wikipedia ↗
tickerdossier.comtickerdossier.substack.com