Quantifiers

Precise definition

A predicate $P(x)$ becomes a proposition when its variables are bound. The universal statement $\forall x\in D\,P(x)$ says $P$ holds for every element of domain $D$; the existential statement $\exists x\in D\,P(x)$ says at least one element of $D$ satisfies it. The uniqueness quantifier $\exists!x$ asserts exactly one.

Notation and mathematical language

Quantifier scope determines which formula is governed. Negations switch quantifiers: $\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)$ and $\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)$. Order matters: $\forall x\exists y$ permits $y$ to depend on $x$, while $\exists y\forall x$ demands one $y$ work for all $x$.

Conceptual picture

Quantifiers encode a game of choices. In $\forall x\exists y$, an opponent chooses $x$ and then you may respond with a suitable $y$. In $\exists y\forall x$, you must choose one $y$ before seeing any $x$, a much stronger requirement.

Conditions and key results

The domain is indispensable: $\exists x(x^2=2)$ is true over $\mathbb R$ but false over $\mathbb Q$. To prove a universal claim, use an arbitrary domain element; to prove existence, construct a witness or invoke a theorem that guarantees one. An example cannot prove a universal claim.

A reliable strategy

1. State every variable's domain and mark the scope of each quantifier with parentheses.
2. Translate the statement in words, preserving quantifier order and dependency.
3. For proof, choose an arbitrary object for $\forall$ or a valid witness for $\exists$.
4. For negation, switch each quantifier, negate the predicate, and then test the translation on a concrete domain.

Fully worked example

Interpretation and application

Quantifiers specify database constraints, function properties, limits, and software requirements. 'Every request eventually receives some response' differs from 'there is one response suitable for every request'; precise scope prevents an implementation from satisfying the wrong requirement.

Common mistakes

Verification and reasonableness

• Try to refute a universal statement with one domain element and to verify an existential statement with one legal witness.
• Read nested quantifiers as an ordered choice game.
• After negating, check that the original and negation cannot both be true and cannot both be false in classical logic.

Practice

1. Negate $\forall n\in\mathbb Z, n^2\ge0$.
2. Is $\exists n\in\mathbb Z\,(n^2=9)$ true?
3. Which is stronger: $\forall x\exists y\,P(x,y)$ or $\exists y\forall x\,P(x,y)$?

Further deduction

The definition of a sequence limit shows why order matters: $a_n\to L$ means $\forall\varepsilon>0\,\exists N\,\forall n\ge N$, $|a_n-L|<\varepsilon$. The index threshold $N$ may depend on the demanded tolerance $\varepsilon$, but once chosen it must work for every later $n$. Reversing the first two quantifiers would demand one universal $N$ that works for all positive tolerances, an unjustifiably stronger statement for most convergent sequences.

Related topics

• Logic and Statements
• Proof by Contradiction
• Functions in Discrete Mathematics