Content deleted Content added
removed Category:Quantification (science); added Category:Quantifier (logic) using HotCat |
Definition in terms of ordinary quantifiers |
||
Line 3:
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 [[recursive definition|recursively]] in terms of ordinary quantifiers.
Let <math>\exists_{= k}</math> denote "there exist exactly <math>k</math>". Then
:<math>\begin{align}
\exists^{= 0} x F(x) &\leftrightarrow \neg \exists x F(x) \\
\exists^{= k+1} x F(x) &\leftrightarrow \exists x (F(x) \land \exists^{= k} y (y \neq x \land F(y)))
\end{align}</math>
Let <math>\exists_{\geq k}</math> denote "there exist at least <math>k</math>". Then
:<math>\begin{align}
\exists^{\geq 0} x F(x) &\leftrightarrow \top \\
\exists^{\geq k+1} x F(x) &\leftrightarrow \exists x (F(x) \land \exists^{\geq k} y (y \neq x \land F(y)))
\end{align}</math>
== See also ==
| |||