In mathematical logic, quantifiers are formal counterparts of natural-language adjectives like all, some, most, few, etc. which indicate the number of objects satisfying a given property. More precisely, 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 ∀ x x ≥ 0 {\displaystyle \forall x\;x\geq 0} expresses that all numbers in the domain are non-negative; this formula is true for the natural numbers domain, but false for the integer domain. On the other hand, the existential quantifier ∃ {\displaystyle \exists } in the formula ∃ x x 2 − 5 x + 6 = 0 {\displaystyle \exists x\;x^{2}-5x+6=0} expresses that some numbers in the domain satisfy the given quadratic equation; indeed, both 2 and 3 do. The most commonly used quantifiers are ∀ {\displaystyle \forall } and ∃ {\displaystyle \exists } . 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. In contrast, the exchange of quantifications in different types changes the meaning. As an example for the latter, the only difference in the definition of uniform continuity and (ordinary) continuity is the order of quantifications.
Relations to logical conjunction and disjunction For a finite domain of discourse D = { a 1 , . . . a n } {\displaystyle D=\{a_{1},...a_{n}\}} , the universally quantified formula ∀ x ∈ D P ( x ) {\displaystyle \forall x\in D\;P(x)} is equivalent to the logical conjunction P ( a 1 ) ∧ . . . ∧ P ( a n ) {\displaystyle P(a_{1})\land ...\land P(a_{n})} . Dually, the existentially quantified formula ∃ x ∈ D P ( x ) {\displaystyle \exists x\in D\;P(x)} is equivalent to the logical disjunction P ( a 1 ) ∨ . . . ∨ P ( a n ) {\displaystyle P(a_{1})\lor ...\lor P(a_{n})} . For example, if B = { 0 , 1 } {\displaystyle B=\{0,1\}} is the set of binary digits, the formula ∀ x ∈ B x = x 2 {\displaystyle \forall x\in B\;x=x^{2}} abbreviates 0 = 0 2 ∧ 1 = 1 2 {\displaystyle 0=0^{2}\land 1=1^{2}} , which evaluates to true.
Infinite domain of discourse 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,
which can be rephrased using existential quantification:
Algebraic approaches to quantification It is possible to devise abstract algebras whose models include formal languages with quantification, but progress has been slow and interest in such algebra has been limited. Three approaches have been devised to date:
Relation algebra, invented by Augustus De Morgan, and developed by Charles Sanders Peirce, Ernst Schröder, Alfred Tarski, and Tarski's students. Relation algebra cannot represent any formula with quantifiers nested more than three deep. Surprisingly, the models of relation algebra include the axiomatic set theory ZFC and Peano arithmetic; Cylindric algebra, devised by Alfred Tarski, Leon Henkin, and others; The polyadic algebra of Paul Halmos.
… excerpt ends here. Continue reading the full article.
