Proofs Involving Quantifiers

How do you prove a statement about every integer when there are infinitely many of them? You take one — any one — and run an argument that uses no special property of that integer beyond its integer-hood. How do you prove that something exists when the universe is enormous? You build it or pick it. These two moves — arbitrary-element for $\forall$, exhibit-a-witness for $\exists$ — are the entire quantifier toolkit. Almost every theorem you will encounter has at least one quantifier in its statement, and the strategy for each comes straight from the truth condition of the quantifier itself.

Proving a universal: let the variable be arbitrary

To prove $\forall x \in D, P(x)$:

1. Begin: "Let $x \in D$ be arbitrary."
2. Use only the fact that $x \in D$ (no special values, no extra assumptions).
3. Derive $P(x)$.
4. Conclude: "Since $x$ was arbitrary, $\forall x \in D, P(x)$." $\blacksquare$

The word "arbitrary" is doing a lot of work. It is a promise to the reader that you will not secretly assume $x$ is special. Once introduced, $x$ is a placeholder representing any possible element of $D$; whatever you derive about it must follow only from $x \in D$.

Proving an existential: exhibit a witness

To prove $\exists x \in D, P(x)$:

1. Produce a specific $c \in D$ (the witness).
2. Verify $P(c)$ by computation or argument.
3. Conclude: "Therefore $\exists x \in D, P(x)$." $\blacksquare$

Sometimes the witness is obvious ("take $n = 1$"). Sometimes finding it is the entire challenge of the proof — the witness might be the root of an equation, the limit of a sequence, or a clever construction. Once you have it, verification is usually mechanical.

There is also a non-constructive existence proof: argue that some object must exist without producing it, typically by contradiction. Non-constructive proofs are perfectly valid but leave the witness implicit.

Disproving a universal: find a counterexample

The negation $\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$ tells you how to disprove a universal: exhibit a single element where the property fails. To disprove "every continuous function is differentiable," produce $f(x) = |x|$. One counterexample beats infinitely many supporting examples — this is the asymmetry between proving universals (you must handle every case) and disproving them (one is enough).

Nested quantifiers: peel from outside in

For a goal like $\forall x, \exists y, P(x, y)$, peel quantifiers in order:

1. Let $x$ be arbitrary.
2. Now, depending on $x$, produce a witness $y$ (possibly different for each $x$).
3. Verify $P(x, y)$.

The order of nested quantifiers is critical. $\forall x, \exists y, x + y = 0$ is true in $\mathbb{R}$ (take $y = -x$). $\exists y, \forall x, x + y = 0$ is false (no single $y$ works for every $x$). When proving, your witness for $\exists y$ may legitimately depend on $x$ if the $\forall x$ comes first. If the $\exists y$ is outermost, the witness must be one fixed $y$ that handles every $x$.

When quantifiers combine with conditionals

The very common form $\forall x, (P(x) \Rightarrow Q(x))$ — "every $x$ with property $P$ also has property $Q$" — peels into: (1) let $x$ be arbitrary; (2) assume $P(x)$; (3) derive $Q(x)$. This is the bread-and-butter shape of subset proofs ($A \subseteq B$), divisibility lemmas, and most "if-then for all" theorems in analysis and algebra.

Pause and think: To prove $\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y^2 = x^2 + 1$, what is your witness $y$ allowed to depend on? Is your witness one specific number, or a formula in $x$? Try writing it.

Try it

• Identify the quantifier shape, then write only the FIRST line of the proof: (a) "Every odd integer is the sum of an even integer and an odd integer." (b) "There exists a real $x$ with $\sin x = 0.5$." (c) "$\forall n \in \mathbb{N}, \exists m \in \mathbb{N}, m > n^2$."
• Predict and verify: is $\exists x \in \mathbb{R}, \forall y \in \mathbb{R}, xy = y$ true? What witness do you propose, and what universal property does it satisfy?
• Spot the flaw: "Claim: $\forall n \in \mathbb{Z}, n^2 > n$. Proof: let $n$ be arbitrary. Take $n = 2$. Then $4 > 2$. So the claim holds for arbitrary $n$." Where is the error, and is the claim even true?
• Disprove or prove: $\forall x \in \mathbb{R}, x^2 \geq x$. If false, give a counterexample; if true, prove it.
• Skeleton: write the first sentence and the conclusion sentence of a proof that "for every set $A$, $\emptyset \subseteq A$." (Hint: peel the $\forall$ and then peel the implication inside the subset definition.)

A trap to watch for

The most common quantifier error is the silent specialisation of an arbitrary variable. A student writes "let $n$ be arbitrary" and three lines later writes "since $n \geq 5$..." with no justification. You can only assume what you have established. If your argument needs a case split (e.g., $n$ even vs odd), you must say so explicitly and handle both cases. The opposite error is also common: trying to prove an existential by an argument that no such object exists is unreasonable rather than by producing one. "Surely there is a prime between 100 and 110" is not a proof — $101$ and $103$ and $107$ and $109$ are. Always verify the witness.

What you now know

You can prove $\forall x, P(x)$ by introducing an arbitrary $x$ and arguing without using any special property of it. You can prove $\exists x, P(x)$ by exhibiting and verifying a witness (which may depend on outer $\forall$-bound variables). You can disprove a universal with a single counterexample and unpack any nested quantifier statement by peeling from the outside in. Quantifier proofs combine naturally with the conditional strategies of the previous section: most real theorems have an outer $\forall$, an inner implication, and require both moves in sequence.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §3.3.
• Polya, G. (1957). How to Solve It: A New Aspect of Mathematical Method. Princeton University Press.
• Hammack, R. (2018). Book of Proof (3rd ed.). Open-source textbook, ch. 8.
• Bloch, E. D. (2011). Proofs and Fundamentals. Springer, ch. 2 (Quantifiers).
• The Univalent Foundations Program (2013). Homotopy Type Theory: Univalent Foundations of Mathematics, ch. 1.11 (Propositions as types).