Lecture 6 — Multiple Quantifiers, Negations of Quantified Statements
Pre-work: Video 007 (Negation of Quantified Statements), Video 008 (Statements with Multiple Quantifiers). See quantified-statements for the reference rules and tables this lecture builds on.
Learning goals
- Know how to negate quantified statements.
- Understand and analyse statements with multiple quantifiers.
- Know how to negate statements with multiple quantifiers.
Common questions
If we establish that the negation of a statement is true, does that mean the original statement is false? Yes.
Negations of quantified statements — why does “exists” change to “for all” and vice versa? “Not every \(x\) has property \(P\)” is exactly “some \(x\) fails \(P\)”, and “no \(x\) has property \(P\)” is exactly “every \(x\) fails \(P\)”. The rules themselves are in quantified-statements.
Is there a short-hand way to write “such that”? Where do we place it? s.t., immediately after the variable and its domain: \(\exists x \in D\) s.t. \(P(x)\).
How can we tell whether a statement with multiple quantifiers is true or false? Sometimes it helps to consider both the original statement and its negation. Remember:
- \(\forall x \in D \dots\) can be shown false with one example.
- \(\exists x \in D \dots\) can be shown true with one example.
Worked: a negation is not the “opposite-sounding” statement
The truth of each statement for each set \(S\):
| \(S\) | \(\forall x \in S, x\) is odd | \(\forall x \in S, x\) is not odd | \(\exists x \in S\) s.t. \(x\) is not odd |
|---|---|---|---|
| \(\{1,3,5,7\}\) | T | F | F |
| \(\{1,2,3,4\}\) | F | F | T |
| \(\{2,4,6,8\}\) | F | T | T |
The first and third columns are negations of one another — they disagree in every row. The middle column is not the negation: for \(S = \{1,2,3,4\}\) it and the original are both false, so they can’t be negations.
Q2 from the Video 7 pre-class questions
Which of the following is a negation of \(\forall x \in \mathbb{Z}\), if \(x^2 > 3\) then \(x > 3\)?
- \(\exists x \in \mathbb{Z}\) such that \(x^2 \leq 3\) or \(x > 3\).
- \(\forall x \in \mathbb{Z}\), if \(x > 3\) then \(x^2 > 3\).
- \(\exists x \in \mathbb{Z}\) such that if \(x^2 > 3\) then \(x > 3\). d. \(\exists x \in \mathbb{Z}\) such that \(x^2 > 3\) and \(x \leq 3\).
- \(\exists x \in \mathbb{Z}\) such that \(x^2 \geq 3\) and \(x \geq 3\).
Answer: d. The trap is that \(P(x)\) here is itself of the form \(p \to q\) — with \(p\) being “\(x^2 > 3\)” and \(q\) being “\(x > 3\)” — so flipping the quantifier is only half the job. The predicate has to be negated as a conditional:
\[\sim(p \to q) \equiv \sim(\sim p \lor q) \equiv p \land \sim q\]
The first step is the definition of \(\to\). The second is de Morgan followed by the double negative law, since de Morgan alone gives \(\sim\!\sim\! p \land \sim q\). De Morgan and the double negative law are both on the exam formula page; the definition of \(\to\) is not — none of that page’s eleven equivalence laws so much as mentions \(\to\), they are written in \(\sim\), \(\land\), \(\lor\) and the constants \(\mathbf{t}\) and \(\mathbf{c}\) alone (see logical-equivalence-laws), so \(p \to q \equiv \sim p \lor q\) has to come from memory; it is set out in conditional-statements. A “justify each step” question wants all three named.
So the negation is \(\exists x \in \mathbb{Z}\) such that \(x^2 > 3\) and \(x \leq 3\). Of the wrong options: b is the converse, with the quantifier not flipped at all; c flips the quantifier but leaves the conditional intact; a is that same mistake in disguise, since \(x^2 \leq 3\) or \(x > 3\) is just \(\sim p \lor q\), i.e. the conditional itself — two of the four distractors are that one error, which is what the question is built to catch; and e weakens \(x^2 > 3\) and never negates \(x > 3\).
Worked: negate, and say which is true
| Statement | Negation | True one | |
|---|---|---|---|
| (a) | \(\exists y \in \mathbb{R}\) s.t. \(y^2 < 0\) (F) | \(\forall y \in \mathbb{R}, y^2 \geq 0\) | negation |
| (b) | All dogs are white. (F) | Some dog is not white. | negation |
| (c) | \(\forall x \in \mathbb{Z}^+, x\) is prime or \(x\) is composite (F) | \(\exists x \in \mathbb{Z}^+\) s.t. \(x\) is not prime and \(x\) is not composite | negation |
| (d) | \(\forall x \in \mathbb{R}\), if \(x > 2\) then \(x^2 > 4\) (T) | \(\exists x \in \mathbb{R}\) s.t. \(x > 2\) and \(x^2 \leq 4\) | original |
Two of these need a reason:
- (c) One value settles it: \(x = 1\), which is neither prime nor composite. Both definitions exclude it (see the prime/composite discussion in proof-techniques), so an “or” that looks exhaustive is not.
- (d) The negation asks for a real number with \(x > 2\) and \(x^2 \leq 4\). The graph of \(x^2\) is an upward parabola: past \(x = 2\) it has already climbed above \(4\) and never comes back, so there is no such \(x\). The negation is false and the original is true.
Every negation in the table has the same shape: the statements built on \(\exists \dots\) negate to \(\forall \dots\) and vice versa, and the ones whose predicate is an or negate to an and (row c), while the one whose predicate is a conditional negates to an and as well (row d). The quantifier flip and the predicate negation are separate steps and both are needed.
Statements with multiple quantifiers
Questions 1 and 2 from the Video 8 pre-class questions
- True or false: \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) such that \(xy \geq y\).
- True or false: \(\exists x \in \mathbb{Z}\) such that \(\forall y \in \mathbb{Z}, xy \geq y\).
Read each one as a question about who chooses what, and in which order:
- “If someone gives me an integer \(x\), can I always find an integer \(y\) such that \(xy \geq y\)?” Notice \(x^2 \geq x\) for any integer \(x\), so given \(x\) we can choose \(y = x\). (Or more simply, choose \(y = 0\).) True.
- “Is there an integer \(x\) such that \(xy \geq y\) for every integer \(y\)?” Notice \(y \geq y\) for any integer \(y\), so taking \(x = 1\) works for every \(y\). True.
The difference is whether \(y\) may be chosen after seeing \(x\) (statement 1), or a single \(x\) has to work for every \(y\) at once (statement 2).
Writing two of the same quantifier
Two of the same quantifier in a row can be written three ways:
| Form | Comment |
|---|---|
| \(\exists x \in D\) and \(\exists y \in E \dots\) | clearer |
| \(\exists x \in D\) and \(y \in E \dots\) | — |
| \(\exists x, y \in D \dots\) | shorthand for the same domain |
The third only makes sense when both variables range over the same domain. All three are acceptable — write the first if you want to be safe.
Negation of statements with multiple quantifiers
Flip every quantifier, keep the order, negate the predicate:
\[\sim\big(\forall x \in X, \exists y \in Y \text{ such that } P(x,y)\big) \equiv \exists x \in X \text{ such that } \forall y \in Y, \sim P(x,y)\]
As a picture, the two statements are written one above the other and matched piece by piece:
Figure 1: Negating a two-quantifier statement, piece by piece. The statement and its negation are stacked and aligned part-for-part, and each coloured pair shows one substitution: every ‘for all’ becomes a ‘there exists’ and picks up the words ‘such that’, every ‘there exists’ becomes a ‘for all’ and picks up the comma, and the predicate at the end is negated. Nothing changes order — \(x\) is still chosen before \(y\) in both rows, which is why the negation of a for-all-then-exists statement is an exists-then-for-all statement and not the other way round.
Two things the picture makes hard to get wrong. The “such that” travels with the \(\exists\), so it moves from the middle of the top row to the front of the bottom row and the comma moves the other way — that is punctuation, not content, but the course expects it. And the order of the variables does not move: the negation of a \(\forall\exists\) statement is an \(\exists\forall\) statement, never \(\forall\exists\) again, and never with \(x\) and \(y\) swapped.
Worked: negate, and determine truth
| Statement | Negation | Which is true | |
|---|---|---|---|
| (a) | \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\) s.t. \(x + y = 0\) | \(\exists x \in \mathbb{R}\) s.t. \(\forall y \in \mathbb{R}, x + y \neq 0\) | original |
| (b) | \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\) s.t. \(xy = 1\) | \(\exists x \in \mathbb{R}\) s.t. \(\forall y \in \mathbb{R}, xy \neq 1\) | negation |
| (c) | \(\exists x \in \mathbb{R}\) s.t. \(\forall y \in \mathbb{R}, xy = 0\) | \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\) s.t. \(xy \neq 0\) | original |
- Given any \(x \in \mathbb{R}\), take \(y = -x\); then \(x + y = x + (-x) = 0\).
- Let \(x = 0\). Then \(0 \cdot y = 0 \neq 1\) for any value of \(y\), so the original fails.
- Take \(x = 0\). Then \(0 \cdot y = 0\) for any \(y\).
Worked: true or false?
| Statement | Verdict | |
|---|---|---|
| (a) | \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) s.t. \(y = 2x\) | True. Given any \(x \in \mathbb{Z}\), take \(y = 2x\). |
| (b) | \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) s.t. \(x = 2y\) | False. Take \(x = 3\) (or any odd integer): \(3 = 2y\) needs \(y = \frac{3}{2} \notin \mathbb{Z}\). |
| (c) | \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) s.t. \(y \geq x\) | True. Given any \(x \in \mathbb{Z}\), take \(y = x + 1\). |
| (d) | \(\exists x \in \mathbb{Z}\) s.t. \(\forall y \in \mathbb{Z}, xy = x\) | True. Take \(x = 0\); then \(0 \cdot y = 0\) for every \(y\). |
- and (b) look symmetric but aren’t — that asymmetry is the whole point of the ordering.
Worked: which statement is the negation?
Which one of the following is a negation of \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) such that \(x + y\) is odd?
- For every integer \(x\) there is an integer \(y\) such that \(x + y\) is not odd.
- There exists an integer \(x\) such that for every integer \(y\), \(x + y\) is odd. c. There exists an integer \(x\) such that \(x + y\) is even for every integer \(y\).
- For every integer \(x\) and every integer \(y\) there is an odd integer \(x + y\).
The negation is: \(\exists x \in \mathbb{Z}\) such that \(\forall y \in \mathbb{Z}\), \(x + y\) is not odd — i.e. is even. Options a and d keep the leading \(\forall\); option b fails to negate the predicate.
Here the original is true (so the negation is false): given any \(x \in \mathbb{Z}\), if \(x\) is odd take \(y = 0\) so \(x + y = x\) is odd; if \(x\) is even take \(y = 1\) so \(x + y = x + 1\) is odd.
See also
- quantified-statements · logical-equivalence-laws
- 2026-08-06-quantified-statements — Lecture 5
- 2026-08-10-direct-proof-and-counterexample — Lecture 7
- practice-problems — §7 Negation of Quantified Statements, with full worked solutions
- practice-problems — §8 Statements with Multiple Quantifiers, with full worked solutions