Quantifier (logic)

Quantifiers in mathematical logic are formal versions of words like "all," "some," "most," and "few" from natural language. They act as operators that tell you how many objects within a particular domain satisfy a given condition, which is expressed as an open formula. The two most familiar quantifiers are the universal quantifier (∀) and the existential quantifier (∃).

For example, the formula ∀x x ≥ 0 means that every number in the domain is non-negative. This statement is true when the domain is the natural numbers but false when it is the integers. In contrast, the formula ∃x x² − 5x + 6 = 0 says that at least one number in the domain satisfies the equation, and indeed both 2 and 3 do.

Order of quantifiers (nesting)

Other quantifiers, such as "most" or "few," can only be defined in second-order or higher-order logics. The study of quantifiers was generalized by Andrzej Mostowski and Per Lindström. In first-order logic, swapping two quantifiers of the same type (both universal or both existential) does not change a statement's meaning, but swapping quantifiers of different types does. For instance, the difference between uniform continuity and ordinary continuity lies entirely in the order of the quantifiers.

Relations to logical conjunction and disjunction

When the domain is finite, a universal quantifier is equivalent to a logical conjunction (an "and" statement) of the property for each element, while an existential quantifier is equivalent to a logical disjunction (an "or" statement). For example, if the domain is the binary digits {0, 1}, the formula ∀x ∈ B x = x² is shorthand for 0 = 0² ∧ 1 = 1², which is true.

Infinite domain of discourse

For infinite domains, a statement like "for every number, something holds" looks like an infinite conjunction, but formal languages require finite statements. Universal and existential quantifiers provide a compact way to express these ideas without infinite lists.

Algebraic approaches to quantification

Algebraic approaches to quantification have been limited in progress. Three main methods exist: relation algebra (invented by Augustus De Morgan and developed by others, though it cannot handle quantifiers nested more than three deep, yet its models include ZFC set theory and Peano arithmetic); cylindric algebra (devised by Alfred Tarski and Leon Henkin); and polyadic algebra (by Paul Halmos).