Negating a quantified statement
“Not every prime is odd.” Rewritten as its own quantified claim, what exactly does that sentence say?
Where you are 4 in Quantifiers
When you reach for it
“Not every prime is odd” and “every prime is not odd” sound like small rewordings of the same idea. They are not. The first says one prime fails to be odd (true, witness 2). The second says every prime fails to be odd (false, since 3 is a counterexample to that). Only one of these is the actual opposite of “every prime is odd,” and getting it right is not a matter of taste: a proof that sets out to disprove a for-all claim has to know exactly what statement it is trying to establish instead.
That is what this skill is for. Given a statement built from \forall and \exists, it produces the one statement that is true exactly when the original is false, and false exactly when the original is true. Reach for it whenever a claim starts “every...” or “there is...” and you need its precise opposite: to test a conjecture, to know what a Counterexample would even have to look like, or to read a definition backwards, the way “the sequence does not converge” has to be unpacked into its own \forall\exists statement before it can be used.
The procedure
Everything rests on two swaps, and each one is forced by what the quantifiers already mean.
The first is allowed because \forall x \in D,\ P(x) is false exactly when P fails somewhere in D, and “P fails somewhere” is precisely what \exists x \in D,\ \neg P(x) says. The second is its mirror: \exists x \in D,\ P(x) is false exactly when P fails everywhere in D, which is \forall x \in D,\ \neg P(x). Neither swap touches the domain D; only the quantifier’s type flips, from \forall to \exists or back, and the negation lands on the predicate instead of on the quantifier.
A small domain makes this concrete. Let D = \{1, 2, 3\} and let P(x) mean “x is odd.” Then \forall x \in D,\ P(x) is false, because 2 fails it, and indeed \exists x \in D,\ \neg P(x) is true with the same witness, 2. The rule is not a trick; it is naming what “false” already meant.
When the predicate is a conjunction or a disjunction, the negation lands on it, and De Morgan’s laws take it from there: \neg(P(x) \land Q(x)) becomes \neg P(x) \lor \neg Q(x), and \neg(P(x) \lor Q(x)) becomes \neg P(x) \land \neg Q(x). A quantified “and” statement therefore negates into an “or” statement with the other quantifier, and an “or” statement negates into an “and” statement.
When the predicate is a conditional, one more fact is needed before the job is done: a conditional P \to Q is false in exactly one case, when P is true and Q is false, so \neg(P \to Q) \equiv P \land \neg Q (more on the conditional itself). A statement of the shape “every x with property P also has property Q,” which is \forall x \in D,\ \big(P(x) \to Q(x)\big), therefore negates to \exists x \in D,\ \big(P(x) \land \neg Q(x)\big): an x with P but without Q. That is the one pattern worth memorizing on sight, because “all A are B” is the commonest shape a claim takes.
When one quantifier sits inside another, push the negation through one layer at a time, working from the outside in. Each pass flips only the outermost quantifier and leaves everything inside it, negation and all, exactly as it was; the inner quantifier does not get touched until its own turn comes. Only once every quantifier has been passed does the innermost predicate get rewritten by De Morgan’s laws or the conditional rule above.
Worked examples
Negating a simple universal statement
Statement: “For every positive integer n, 2^n > n^2.” Write its negation, and decide the truth of each.
SolutionIn symbols the statement is \forall n \in \mathbb{Z}^+,\ 2^n > n^2. Applying the first swap, the negation is
“There is a positive integer whose power of two is at most its square.” The negated predicate is 2^n \le n^2, not 2^n < n^2: the opposite of “greater than” includes the case of equality, and here that case matters. At n = 1 the original holds, since 2^1 = 2 > 1 = 1^2. At n = 2 it fails: both sides are 4, and 4 > 4 is false while 4 \le 4 is true. The number 2 is a witness for the negation, which is therefore true, and the original is false. Had the negation been written with <, the witness 2 would not count, and one would have to go on to n = 3, where 2^3 = 8 < 9 = 3^2.
An existential whose negation needs a proof
Statement: “There is a real number x with x^2 + 2x + 2 = 0.” Write its negation, and decide the truth of each.
SolutionIn symbols, \exists x \in \mathbb{R},\ x^2 + 2x + 2 = 0. The second swap gives
“No real number makes x^2 + 2x + 2 equal to 0.” Trying values will never settle this, because the negation is now a claim about every real number, and it needs an argument that covers them all at once. Rewrite the expression as x^2 + 2x + 2 = (x + 1)^2 + 1. A square of a real number is never negative, so (x + 1)^2 + 1 \ge 1 for every real x, and a number that is at least 1 is not 0. The negation is true, so the original is false. This is the general pattern: negating a “there is” turns a search for one witness into a proof about every member of the domain.
A predicate joined by and
Statement: “Every real number lies between 0 and 10,” meaning \forall x \in \mathbb{R},\ (x \ge 0 \land x \le 10). Write its negation, and decide the truth of each.
SolutionPush the negation past \forall:
then apply De Morgan’s laws to the “and” inside:
“There is a real number that is negative or greater than 10.” The original is false: not every real number sits in [0, 10], since, for instance, x = 15 does not. That same 15 witnesses the negation, since 15 > 10, so the negation is true.
A universal conditional
Statement: “Every prime greater than 2 is odd,” where P(n) means “n is prime” and O(n) means “n is odd.” In symbols, \forall n \in \mathbb{Z}^+,\ \big((P(n) \land n > 2) \to O(n)\big). Write its negation, and decide the truth of each.
SolutionPush the negation past \forall:
then negate the conditional with \neg(A \to B) \equiv A \land \neg B, where A is P(n) \land n > 2 and B is O(n):
“There is a prime greater than 2 that is not odd.” Every even number greater than 2 has 2 as a factor, so it is not prime; that leaves nothing greater than 2 that could be both prime and even. The original statement is true, so its negation, asserting the opposite, is false: no prime greater than 2 is ever even.
Two quantifiers, one inside the other
Statement: “For every natural number x, there is a natural number y with y < x,” where the natural numbers are 0, 1, 2, \ldots. In symbols, \forall x \in \mathbb{N},\ \exists y \in \mathbb{N},\ y < x. Write its negation, and decide the truth of each.
SolutionPush the negation past the outer \forall first, leaving the inner quantifier untouched:
Now push it past the inner \exists:
and rewrite \neg(y < x) as y \ge x:
“There is a natural number that is less than or equal to every natural number.” The original statement is false: at x = 0 there is no natural number smaller than 0, so 0 already breaks the claim. That same 0 witnesses the negation, since every natural number y satisfies y \ge 0, so the negation is true. 0 is the smallest natural number; over the integers, where there is no smallest number at all, the original statement would instead come out true.
Using the negation to disprove a claim
A classmate claims: “Every odd number is prime.” Use negation to decide whether this is true, and name what you would need to produce to settle it.
SolutionIn symbols the claim is \forall n \in \mathbb{Z}^+,\ \big(O(n) \to P(n)\big), where O(n) is “n is odd” and P(n) is “n is prime.” By the rule for a universal conditional, its negation is
“There is an odd number that is not prime.” To settle the claim it is enough to decide whether this negation is true, and to show a statement of the form \exists n, \ldots true, one object that does the job is all it takes: a single odd, non-prime number. Take n = 9: it is odd, and 9 = 3 \times 3 is not prime. That one number makes the negation true, so the original claim is false. Producing exactly this kind of witness against a \forall statement is the skill of counterexample; negating the claim first is what tells you precisely what such a counterexample has to satisfy.
Boundaries
The domain never changes. Negating \forall x \in D,\ P(x) or \exists x \in D,\ P(x) swaps the quantifier and negates the predicate; it never touches D. A negation that quietly widens or shrinks the domain is not the negation of the original claim.
The quantifiers keep their order. Pushing a negation through nested quantifiers one layer at a time (Example 5) flips the type of every quantifier and negates the innermost predicate, but it never moves a quantifier. The end result can be written in one step for that reason: same variables, same domains, same order, each \forall now \exists and each \exists now \forall. Reordering them as well gives a different statement altogether, since the order of a \forall and an \exists changes what is claimed (Nested quantifiers).
A restriction stays a restriction. In “every prime greater than 2 is odd,” the words “greater than 2” narrow which numbers the claim is about; they are part of the hypothesis, not of the conclusion. The negation keeps them and denies only the conclusion: “some prime greater than 2 is not odd” (Example 4), never “some prime at most 2 is not odd.”
“If ... then” needs its own rule, not just the quantifier swap. Passing \neg across \forall in \forall x,\ \big(P(x) \to Q(x)\big) only produces \exists x,\ \neg\big(P(x) \to Q(x)\big); a further, separate fact, \neg(P \to Q) \equiv P \land \neg Q, is what turns that into \exists x,\ \big(P(x) \land \neg Q(x)\big). Stopping after the quantifier swap leaves a negated conditional sitting unfinished inside the statement.
The rule is an equivalence, not an approximation. \neg\big(\forall x \in D, P(x)\big) and \exists x \in D,\ \neg P(x) do not merely tend to agree; they have the same truth value for every choice of D and P, including the empty domain, where \forall x \in \varnothing,\ P(x) is true and \exists x \in \varnothing,\ \neg P(x) is correspondingly false, for every P.
Where this goes next
Negation turns a \forall claim into the exact statement a counterexample has to make true, which is why disproving “every...” always starts here (Example 6). It is also where a limit definition or a claim of continuity has to begin once you try to show it fails: those are statements with several nested quantifiers, and negating one correctly, layer by layer, is what tells you which quantity to search for and which one you get to fix.
The rule also feeds back into ordinary logical equivalence: once a quantified statement is negated, the sentence sitting inside each quantifier is manipulated with exactly the same tools, De Morgan’s laws and the conditional’s own negation, that apply to statements with no quantifier at all.
Exercises
Negating a single quantifier
- Negate “\forall n \in \mathbb{Z},\ n is a multiple of 3.” Decide the truth of the statement and of its negation.
- Negate “\exists x \in \mathbb{R},\ x^2 = 5.” Decide the truth of both.
- Negate “\forall x \in \mathbb{R},\ x + 1 > x.” Decide the truth of both.
- Negate “\exists n \in \mathbb{Z}^+,\ n^2 = n.” Decide the truth of both.
- Negate “\forall x \in \mathbb{R},\ \lvert x \rvert \ge 0.” Without testing a single number, explain why the negation must be false.
True or false
- \forall n \in \mathbb{Z},\ n^2 \ge 4
- \exists n \in \mathbb{Z},\ n^2 = 2n
- \forall x \in \mathbb{R},\ x^2 + 4x + 5 > 0
- \exists x \in \mathbb{Q},\ x^2 = 3
For each, write the negation and give its truth value too.
And, or, and if ... then
- Negate \forall x \in \mathbb{R},\ \big(x \ge 2 \land x \le 8\big). Decide the truth of both.
- Negate \exists n \in \mathbb{Z},\ \big(n > 0 \lor n < -100\big). Decide the truth of both.
- Negate \forall n \in \mathbb{Z}^+,\ \big(4 \mid n \to 2 \mid n\big), where “4 \mid n” is read “4 divides n” and “2 \nmid n” is read “2 does not divide n.” Decide the truth of both.
- Negate \forall x \in \mathbb{R},\ \big(x < 0 \to x^2 > 0\big). Decide the truth of both.
Nested quantifiers
- Negate \forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ xy = 1. Decide the truth of both.
- Negate \exists x \in \mathbb{Z},\ \forall y \in \mathbb{Z},\ x \le y. Decide the truth of both.
- Negate \forall x \in \mathbb{N},\ \forall y \in \mathbb{N},\ x + y \ge x. Decide the truth of both, using only what it means for y to be a natural number.
Reasoning
- A classmate negates “\forall x,\ \big(P(x) \to Q(x)\big)” as “\forall x,\ \big(\neg P(x) \to \neg Q(x)\big).” Explain why this cannot be right, using the rule for negating a conditional.
- Show, directly from what “for all” and “there exists” mean, that \forall x \in D,\ P(x) and \exists x \in D,\ \neg P(x) can never both be true and can never both be false.
- Explain, in your own words and without simply restating the rule, why \neg\big(\exists x \in D,\ P(x)\big) has to mean the same thing as \forall x \in D,\ \neg P(x).
- Use negation to prove that “Every multiple of 6 is a multiple of 9” is false. Name the number your negation forces you to find.
Answers
- \exists n \in \mathbb{Z},\ n is not a multiple of 3. The original is false (1 is not a multiple of 3), so the negation is true, with the same witness, 1.
- \forall x \in \mathbb{R},\ x^2 \ne 5. The original is true, since \displaystyle x = \sqrt{5} gives \displaystyle \left(\sqrt{5}\right)^2 = 5, so the negation is false.
- \exists x \in \mathbb{R},\ x + 1 \le x. The original is true for every real x, since (x + 1) - x = 1 > 0, so the negation is false.
- \forall n \in \mathbb{Z}^+,\ n^2 \ne n. The original is true, with witness n = 1, since 1^2 = 1, so the negation is false.
- \exists x \in \mathbb{R},\ \lvert x \rvert < 0. An absolute value is a distance, and a distance is never negative, so no real number can make \lvert x \rvert < 0 true. The negation has no witness anywhere, so it is false (and the original is true) without a single value tested.
- False: n = 0 gives 0^2 = 0, which is not \ge 4. Negation: \exists n \in \mathbb{Z},\ n^2 < 4, true with the same witness, 0.
- True: n = 0 gives 0^2 = 0 = 2(0). Negation: \forall n \in \mathbb{Z},\ n^2 \ne 2n, false.
- True: x^2 + 4x + 5 = (x + 2)^2 + 1 \ge 1 > 0 for every real x, since a square is never negative. Negation: \exists x \in \mathbb{R},\ x^2 + 4x + 5 \le 0, false.
- False: \displaystyle \sqrt{3} and \displaystyle -\sqrt{3} are the only real square roots of 3, and neither is a fraction. Negation: \forall x \in \mathbb{Q},\ x^2 \ne 3, true.
- \exists x \in \mathbb{R},\ \big(x < 2 \lor x > 8\big). The original is false, since x = 0 fails it, and 0 witnesses the negation, since 0 < 2, so the negation is true.
- \forall n \in \mathbb{Z},\ \big(n \le 0 \land n \ge -100\big). The original is true, with witness n = 1, since 1 > 0. The negation is false: that same 1 fails “n \le 0,” since 1 \le 0 is false.
- \exists n \in \mathbb{Z}^+,\ \big(4 \mid n \land 2 \nmid n\big). The original is true: any multiple of 4 is 4k = 2(2k), which is a multiple of 2, so no n can be a multiple of 4 without being a multiple of 2. The negation is false.
- \exists x \in \mathbb{R},\ \big(x < 0 \land x^2 \le 0\big). The original is true, since a negative real number is never 0, so its square is always positive. The negation is false: the only real number with x^2 \le 0 is x = 0, and 0 is not negative.
- \exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ xy \ne 1. The negation is true, with witness x = 0: every real y gives 0 \cdot y = 0 \ne 1. So the original is false. Every other x does have a partner, \displaystyle y = \frac{1}{x}, but a “for all” claim needs every x, and one failure is enough.
- \forall x \in \mathbb{Z},\ \exists y \in \mathbb{Z},\ y < x. The original is false: for any candidate x, y = x - 1 is an integer with y < x, since x - (x - 1) = 1 > 0, so no x can be less than or equal to every integer. The negation is true, with that same y = x - 1 serving as the witness for every x.
- \exists x \in \mathbb{N},\ \exists y \in \mathbb{N},\ x + y < x. The original is true: for natural numbers, y \ge 0 always, so x + y \ge x for every x and y. The negation is false, since x + y < x would force y < 0, and no natural number is negative.
- This claims the negation is another universal conditional, but the rule for a conditional says \neg\big(\forall x, (P(x) \to Q(x))\big) is \exists x,\ \big(P(x) \land \neg Q(x)\big): the quantifier becomes existential and the conditional becomes an “and,” neither of which the classmate’s version does. A negation must have the opposite truth value to the original in every case, and the classmate’s version can share it. Over the integers, take P(n): “n is even” and Q(n): “n^2 is even.” The original, “every even integer has an even square,” is true. The classmate’s version, “every odd integer has an odd square,” is also true, since (2k + 1)^2 = 2(2k^2 + 2k) + 1. Two true statements cannot be negations of each other.
- If \forall x \in D,\ P(x) is true, then P fails for no member of D, so no witness exists for \exists x \in D,\ \neg P(x), which is therefore false; they cannot both be true. If \forall x \in D,\ P(x) is false, then P fails for some member of D, and that member is a witness making \exists x \in D,\ \neg P(x) true; they cannot both be false. Every case is one of these two, so exactly one of the pair is true.
- \exists x \in D,\ P(x) is true exactly when at least one member of D makes P true, so it is false exactly when every member of D makes P false, that is, every member makes \neg P true. “Every member makes \neg P true” is exactly what \forall x \in D,\ \neg P(x) says, so the two sides describe the same situation and must share a truth value.
- In symbols, “every multiple of 6 is a multiple of 9” is \forall n \in \mathbb{Z}^+,\ \big(6 \mid n \to 9 \mid n\big), which negates to \exists n \in \mathbb{Z}^+,\ \big(6 \mid n \land 9 \nmid n\big). The number n = 6 makes this true: 6 is a multiple of 6, and 6 \div 9 is not a whole number, so 6 is not a multiple of 9. That single number makes the negation true, so the original claim is false.