Equivalences Involving Quantifiers

To disprove 'every prime is odd' you find a single even prime. To disprove 'some integer is between $5$ and $6$' you must rule out every integer. The two refutation styles are dual to each other, and that duality is captured by the negation rules for quantifiers. This section turns the duality into a calculus: you can push a negation through any string of $\forall$'s and $\exists$'s mechanically, flipping each quantifier as you go. Mastering this mechanical move is what separates students who can read a proof from students who can write one.

The two negation rules

The fundamental dualities of quantifier negation are:

In words: the negation of "for all" is "there exists one that fails," and the negation of "there exists" is "for all, it is not the case." The negation flips the quantifier and slides past it onto the body.

These two rules are powerful because they let you reduce any refutation to a positive task. Want to refute $\forall x, P(x)$? Prove the equivalent existential $\exists x, \neg P(x)$ — that is, exhibit one counterexample. Want to refute $\exists x, P(x)$? Prove the universal $\forall x, \neg P(x)$ — show no element works.

Nested quantifiers

For multiple stacked quantifiers, push the negation in one quantifier at a time, flipping each one as you cross it. Example:

This is exactly the same as De Morgan, generalized to quantifiers. To negate a statement with $n$ alternating quantifiers, walk through them left to right and flip each one. The internal predicate at the end picks up the leading $\neg$.

Negating bounded quantifiers

Bounded quantifiers expand into the connectives $\Rightarrow$ and $\wedge$:

The domain $D$ stays put — only the inside flips. Writing it out:

This is just what your intuition says: to refute "every element of $D$ satisfies $P$," find an element of $D$ that fails $P$.

Vacuous truth

The universal $\forall x \in A,; P(x)$ is vacuously true when $A = \emptyset$: there are no elements to falsify the claim, so it holds trivially. This is initially uncomfortable — "every element of the empty set is a unicorn" is technically true — but it is the only convention that makes the negation rules consistent. The dual existential $\exists x \in A,; P(x)$ over an empty domain is false: with no elements, there is no possible witness.

Vacuous truth is not just a curiosity. The base case of many induction proofs in Chapter 6 relies on it; so does the convention that the empty intersection of subsets of $X$ equals $X$. Get used to it now.

Pause and think: Negate "every continuous function on $[0, 1]$ is bounded." Push the negation all the way in. What concrete object would a refutation provide? (Hint: a witness to the negated statement is a single function that is continuous on $[0,1]$ AND not bounded.)

Try it

• Before writing: predict the negation of "All birds can fly." Then translate to symbols, push the negation in, and check that the English version matches your prediction.
• Negate $\forall x \in \mathbb{Z},; (x \text{ is prime} \Rightarrow x \text{ is odd})$ step by step. Find a concrete witness to the negation.
• Predict first: what is the negation of $\exists n \in \mathbb{N},; \forall k \in \mathbb{N},; n \geq k$? Push the negation in two steps, then state what kind of object would witness the negation.
• Is $\forall x \in \emptyset,; x = x + 1$ true or false? Justify using the bounded-quantifier expansion $\forall x,;(x \in \emptyset \Rightarrow x = x + 1)$.
• Negate the ε–δ definition of continuity at $a$: $\forall \varepsilon > 0,;\exists \delta > 0,;\forall x,;(|x - a| < \delta \Rightarrow |f(x) - f(a)| < \varepsilon)$. Describe in words what a discontinuous function at $a$ looks like.

A trap to watch for

The most painful mistake when negating a bounded conditional is forgetting to flip the implication. Students often see $\neg \forall x \in D,; (P(x) \Rightarrow Q(x))$ and write $\exists x \in D,; (P(x) \Rightarrow \neg Q(x))$. Wrong. The correct negation is $\exists x \in D,; (P(x) \wedge \neg Q(x))$, because $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$. The implication itself collapses into a conjunction when negated; it does not survive on the other side. A safe routine: expand the bounded quantifier first, then push $\neg$ inward, applying the standard logic rules at each step.

What you now know

You can negate any quantified statement by pushing $\neg$ through, flipping each quantifier, and applying the connective rules at the bottom. You understand vacuous truth and why bounded universal statements over the empty set are true. The next section returns to sets to introduce indexed unions, intersections, power sets, and Cartesian products — the larger building blocks that future chapters will pile on top of.

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.