Quantifiers

For all versus there exists: read the quantifiers, negate them by flipping each one, and remember that the order they appear in changes the claim.

The idea

A quantifier turns a condition on a variable into a definite statement about a whole collection of objects.

A sentence such as "$x$ is prime" is neither true nor false on its own, because its truth depends on $x$; such a sentence is a predicate, written $P(x)$. Fix a domain, the collection of objects that $x$ ranges over. There are two quantifiers. $\forall x\, P(x)$ is the universal statement, read as for all $x$, $P(x)$. It asserts that every object in the domain satisfies $P$. $\exists x\, P(x)$ is the existential statement, read as there exists an $x$ such that $P(x)$. It asserts that at least one object in the domain satisfies $P$.

The domain is part of the claim. The statement $\forall n\ (n \geq 0)$ is true over the natural numbers and false over the integers, so when the context does not fix the domain we write it into the statement, as in $\forall n \in \mathbb{N}$.

Quantifiers can be nested, as in $\forall x\, \exists y\ Q(x, y)$. Read a nested statement from left to right, each quantifier inside the ones before it; exchanging two quantifiers can change the claim entirely. The figure shows why: $\forall x\, \exists y$ lets $y$ be chosen afresh for each $x$, while $\exists y\, \forall x$ demands one $y$ that works for every $x$.

Ways to work on it

• Walkthrough. Meet and , negate a universal with a counterexample, and see why nested-quantifier order matters.
• Practice. Negate a quantified statement, judge whether a quantified claim is true over a stated domain, or supply a counterexample.
• Hardest. Evaluate a nested quantified statement under both orders, then negate it correctly.

Not sure where to start? Take the ten-question placement test.