The negation of '∀x P(x)' is '∃x ¬P(x)', and the negation of '∃x P(x)' is '∀x ¬P(x)'. Understanding how negation interacts with quantifiers is essential for proof by contradiction and logical precision.
Practice with concrete predicates: negating 'all primes > 2 are odd' gives 'there exists a prime > 2 that is not odd'.
From your prerequisite on predicates and quantifiers, you know that ∀x P(x) means "P(x) holds for every x in the domain," and ∃x P(x) means "there exists at least one x for which P(x) holds." Negation of quantified statements follows directly from what it takes to make these claims false. To show ∀x P(x) is false, you only need a single x where P fails — one counterexample. So the negation of a universal statement is existential: ¬(∀x P(x)) = ∃x ¬P(x). To show ∃x P(x) is false, you need to show every single x fails P — no exceptions allowed. So the negation of an existential statement is universal: ¬(∃x P(x)) = ∀x ¬P(x).
The rule is: negation flips the quantifier and pushes inward to the predicate. For nested quantifiers, apply the rule repeatedly from the outside in. For example, ¬(∀x ∃y R(x,y)) = ∃x ∀y ¬R(x,y). Read this step by step: the ∀ flips to ∃, the ∃ flips to ∀, and the predicate R(x,y) becomes ¬R(x,y). Each application of the rule is mechanical. The challenge is keeping track of scope when quantifiers are nested three or four levels deep — working outside-in, one quantifier at a time, prevents errors.
A concrete example shows why this matters in real mathematics. The epsilon-delta definition of continuity says f is continuous at a if: ∀ε > 0 ∃δ > 0 ∀x (|x − a| < δ → |f(x) − f(a)| < ε). The negation — "f is not continuous at a" — is: ∃ε > 0 ∀δ > 0 ∃x (|x − a| < δ ∧ |f(x) − f(a)| ≥ ε). Every quantifier flips, and the implication "P → Q" becomes "P ∧ ¬Q" (since the negation of an implication is not another implication but a conjunction). Without the quantifier-negation rules applied correctly, you cannot even state what it means for a function to be discontinuous, let alone prove it.
These rules are the mechanical backbone of two major proof strategies that build on this topic. Proof by contradiction assumes the negation of the conclusion and derives a contradiction; when the conclusion is a universally quantified statement, its negation is existential, so you have a witness to work with. Disproof by counterexample uses the fact that ¬(∀x P(x)) = ∃x ¬P(x) — one explicit x where P fails completely destroys a universal claim. In both cases, the ability to correctly negate quantified statements is not optional: it is the first move in the proof.