Lecture 6 — Multiple Quantifiers, Negations of Quantified Statements

lecture
discrete-math
logic
quantifiers

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

  1. Know how to negate quantified statements.
  2. Understand and analyse statements with multiple quantifiers.
  3. Know how to negate statements with multiple quantifiers.

Student questions and comments

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? Because “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 are in quantified-statements.

Is there a short-hand way to write “such that”? Where do we place it? s.t., immediately after the quantified variable: \(\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.

Activity 1 — a negation is not the “opposite-sounding” statement

Fill in 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\)?

  1. \(\exists x \in \mathbb{Z}\) such that \(x^2 \leq 3\) or \(x > 3\).
  2. \(\forall x \in \mathbb{Z}\), if \(x > 3\) then \(x^2 > 3\).
  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\).
  4. \(\exists x \in \mathbb{Z}\) such that \(x^2 \geq 3\) and \(x \geq 3\).

Answer: d. Here \(P(x)\) is of the form \(p \to q\), so negate it accordingly:

\[\sim(p \to q) \equiv \sim(\sim p \lor q) \equiv p \land \sim q\]

using the definition of \(\to\) and then De Morgan’s law (see logical-equivalence-laws). Option b is the converse, not a negation; c keeps the conditional intact.

Activity 2 — 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

For (c), \(x = 1\) is neither prime nor composite — see the prime/composite discussion in proof-techniques.

Statements with multiple quantifiers

Questions 1 and 2 from the Video 8 pre-class questions

  1. True or false: \(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z}\) such that \(xy \geq y\).
  2. 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:

  1. “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.
  2. “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 depend on \(x\) (statement 1) or must work for all \(y\) at once (statement 2).

Writing two of the same quantifier

\(\exists x \in D\) and \(\exists y \in E \dots\) is the clearest; \(\exists x \in D\) and \(y \in E \dots\) is common shorthand; \(\exists x, y \in D \dots\) is shorthand when both range over the same domain.

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)\]

Activity 3 — 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
    1. Given any \(x \in \mathbb{R}\), take \(y = -x\); then \(x + y = x + (-x) = 0\).
    1. Let \(x = 0\). Then \(0 \cdot y = 0 \neq 1\) for any value of \(y\), so the original fails.
    1. Take \(x = 0\). Then \(0 \cdot y = 0\) for any \(y\).

Activity 4 — 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\).
  1. and (b) look symmetric but aren’t — that asymmetry is the whole point of the ordering.

Activity 5

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?

  1. For every integer \(x\) there is an integer \(y\) such that \(x + y\) is not odd.
  2. 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\).
  3. 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