Quantifiers

Propositional logic alone cannot say 'every integer has a successor'. Propositional logic only talks about whole sentences, it cannot reach inside a sentence to talk about every object or some object. To express the bulk of real mathematical statements, "every continuous function is integrable," "there exists a prime between $n$ and $2n$," "for every $\varepsilon > 0$ there is a $\delta > 0$ such that…", we need quantifiers. The two quantifiers $\forall$ ("for all") and $\exists$ ("there exists") are the gateway from propositional to predicate logic, and once their order rules are nailed down, you can read essentially any modern mathematical text.

Universal and existential quantifiers

The universal quantifier $\forall$ means "for all" or "for every." The formula $\forall x,; P(x)$ asserts that the predicate $P(x)$ is true for every value $x$ in the domain of discourse. To prove a universal statement, you must establish $P(x)$ for an arbitrary $x$; to disprove it, a single counterexample suffices.

The existential quantifier $\exists$ means "there exists" or "for some." The formula $\exists x,; P(x)$ asserts that there is at least one $x$ in the domain for which $P(x)$ is true. To prove an existential statement, you must exhibit a witness, a specific $x$ that works; to disprove it, you must show $P(x)$ fails for every $x$.

Bounded quantifiers

Real mathematics almost always quantifies over a specific domain, not the entire universe. We write bounded quantifiers as $\forall x \in D, P(x)$ or $\exists x \in D, P(x)$. The unwritten translation is:

The universal uses an implication (the property only has to hold for the $x$'s that are in $D$) while the existential uses a conjunction (you need an $x$ that both lies in $D$ and satisfies the property). Notice how the connective differs, that asymmetry has a habit of biting students.

Order matters: $\forall \exists$ vs. $\exists \forall$

Quantifier order is non-commutative in a way that bites every undergraduate. To see the bite directly, the widget below shows two panels side by side: $\forall x \exists y , P(x, y)$ on the left and $\exists y \forall x , P(x, y)$ on the right, both for the same $P$. Cycle through the four presets, including the ε–δ definition of continuity, where the order of the quantifiers is what separates a usable definition from a degenerate one, and the everyday "every student has a favourite course" example.

The single subtlest move in predicate logic is the order of nested quantifiers. Consider two superficially similar statements about $\mathbb{R}$:

"For every $x$, there is some $y$ with $x + y = 0$." This is true: given $x$, choose $y = -x$. The witness $y$ is allowed to depend on $x$.

"There is some $y$ such that, for every $x$, $x + y = 0$." This is false: it demands a single $y$ that works for every $x$ at once. Any choice of $y$ would have to satisfy $1 + y = 0$ and $2 + y = 0$ simultaneously, which is impossible.

The pattern $\forall x \exists y$ allows $y$ to depend on $x$; the pattern $\exists y \forall x$ demands a single $y$ that works for every $x$. These two patterns are not interchangeable, and almost every "$\varepsilon$-$\delta$" definition in analysis hinges on this distinction.

Pause and think: In the ε–δ definition of limit, we say $\forall \varepsilon > 0,; \exists \delta > 0,; \forall x,;(0 < |x - a| < \delta \Rightarrow |f(x) - L| < \varepsilon)$. Why is the $\delta$ allowed to depend on $\varepsilon$? What would change if we swapped to $\exists \delta, \forall \varepsilon$? (Hint: that swap is too strong to be useful, it would force a single δ to work for all ε. The genuine strengthening is uniform continuity, ∀ε ∃δ ∀x,y with one δ working at every point at once, a global property of the function, not something at a single point a.)

Try it

• Before translating: identify whether "There is a real number whose square is $-1$" is true or false. Then write it symbolically and double-check by inspection.
• Predict first: is $\forall x \in \mathbb{R},; \exists y \in \mathbb{R},; y > x$ true? Now is $\exists y \in \mathbb{R},; \forall x \in \mathbb{R},; y > x$ true? Explain the difference.
• Translate into symbols: "Every nonzero real number has a multiplicative inverse." Then "There is an integer that divides every integer." Both statements should use a quantifier; check whether each is true.
• Find a witness: prove $\exists n \in \mathbb{Z},; n^2 = 16$ by exhibiting one.
• Find a counterexample: disprove $\forall n \in \mathbb{N},; n^2 > n$.

A trap to watch for

The most damaging mistake in early predicate logic is treating $\forall x \exists y$ as if it meant the same as $\exists y \forall x$. They are not the same. The give-away phrasing is "there exists a… for every…", English word order can mask which quantifier is on the outside. A single example to keep in mind: "for every person there is a mother" (true, everyone has a mother) versus "there is a person who is the mother of everyone" (false). Same words, different quantifier order, opposite truth values. Whenever you read a multi-quantifier statement, draw an arrow from each variable to its scope: the $y$ in $\forall x \exists y$ depends on $x$; the $y$ in $\exists y \forall x$ does not.

What you now know

You can read, write, and translate quantified statements with bounded domains, and you know that quantifier order is load-bearing, $\forall x \exists y$ and $\exists y \forall x$ usually say different things. The next section attacks the operations on quantifiers: how to negate them, push negations through them, and recognize logically equivalent quantified statements.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 2.
• Enderton, H. B. (2001). A Mathematical Introduction to Logic (2nd ed.). Academic Press, ch. 2.
• Smullyan, R. M. (1995). First-Order Logic. Dover Publications, ch. 2.
• Mendelson, E. (2015). Introduction to Mathematical Logic (6th ed.). Chapman and Hall/CRC, ch. 2.