Quantifier (logic)

In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier ${\displaystyle \forall }$ in the first-order formula ${\displaystyle \forall xP(x)}$ expresses that everything in the domain satisfies the property denoted by ${\displaystyle P}$. On the other hand, the existential quantifier ${\displaystyle \exists }$ in the formula ${\displaystyle \exists xP(x)}$ expresses that there exists something in the domain which satisfies that property. A formula where a quantifier takes widest scope is called a quantified formula. A quantified formula must contain a bound variable and a subformula specifying a property of the referent of that variable.

The most commonly used quantifiers are ${\displaystyle \forall }$ and ${\displaystyle \exists }$. These quantifiers are standardly defined as duals; in classical logic: each can be defined in terms of the other using negation. They can also be used to define more complex quantifiers, as in the formula ${\displaystyle \neg \exists xP(x)}$ which expresses that nothing has the property ${\displaystyle P}$. Other quantifiers are only definable within second-order logic or higher-order logics. Quantifiers have been generalized beginning with the work of Andrzej Mostowski and Per Lindström.

In a first-order logic statement, quantifications in the same type (either universal quantifications or existential quantifications) can be exchanged without changing the meaning of the statement, while the exchange of quantifications in different types changes the meaning. As an example, the only difference in the definition of uniform continuity and (ordinary) continuity is the order of quantifications.

First-order quantifiers approximate the meanings of some natural language quantifiers such as "some" and "all". However, many natural language quantifiers can only be analyzed in terms of generalized quantifiers.

For a finite domain of discourse ${\displaystyle D=\{a_{1},...a_{n}\}}$, the universally quantified formula ${\displaystyle \forall x\in D\;P(x)}$ is equivalent to the logical conjunction ${\displaystyle P(a_{1})\land ...\land P(a_{n})}$. Dually, the existentially quantified formula ${\displaystyle \exists x\in D\;P(x)}$ is equivalent to the logical disjunction ${\displaystyle P(a_{1})\lor ...\lor P(a_{n})}$. For example, if ${\displaystyle B=\{0,1\}}$ is the set of binary digits, the formula ${\displaystyle \forall x\in B\;x=x^{2}}$ abbreviates ${\displaystyle 0=0^{2}\land 1=1^{2}}$, which evaluates to true.

Consider the following statement (using dot notation for multiplication):

This has the appearance of an infinite conjunction of propositions. From the point of view of formal languages, this is immediately a problem, since syntax rules are expected to generate finite statements. A succinct equivalent formulation, which avoids these problems, uses universal quantification:

A similar analysis applies to the disjunction,