Skip to main content

Discrete Mathematics An Active Approach to Mathematical Reasoning

Jennifer Firkins Nordstrom

Section 3.3 Statements with Multiple Quantifiers

Many statements in mathematics involve multple quantifiers. For example, “For all real numbers x, there exists a real number y with x+y=0.” These statements, though frequent in math courses, represent some of the most complicated types of statements to understand. In this section we will try to understand the general structure of such statements.
🔗
Let’s look at the various ways we could have statements with two quantifiers. Since we have two quantifiers, we will have two variables. Thus, our predicate will now involve both variables. We can use the notation P(x,y) to mean a statement about x and y.
🔗
  • ∀x∈D,∃y∈E,P(x,y).
    🔗
    This means we can find a y in E that makes P(x,y) true for each x in D. In such statements y will often depend on x.
    🔗
    🔗
  • ∃x∈D,∀y∈E,P(x,y).
    🔗
    The order of the quantifiers matters. This means we can find a single x in D that makes P(x,y) true for every y in E. In such statements x does not depend on y. The same x must work for all the y’s.
    🔗
    🔗
  • ∀x∈D,∀y∈E,P(x,y).
    🔗
    This means P(x,y) is true for all x∈D and for all y∈E.
    🔗
    🔗
  • ∃x∈D,∃y∈E,P(x,y).
    🔗
    This means P(x,y) is true for for at least one x∈D and at least one y∈E.
    🔗
    🔗

Example 3.3.1. Statements with Multiple Quantifiers.

Let x,y∈R. Determine whether the following statements are true or false.
🔗
∀x,∃y,x+y=5.
For any x can you always find a corresponding y with x+y=5?
🔗
Answer 1.
Yes, for each x let y=5−x. So the statement is true.
🔗
🔗
∃x,∀y,x+y=5.
Is there a single x that works for all y?
🔗
Answer 2.
No, no single x will always have x+y=5. So the statement is false.
🔗
🔗
🔗

Activity 3.3.1.

Let x,y∈Znonneg. Determine if each statement is true or false. Give a reason for your answer.
🔗
🔗
Although we won’t study the mathematical context of the following example in this class, it is a classic example in mathematics of a statement with multiple quantifiers and a conditional. It is so important that it is the subject of one set of math bike racks in front of Taylor Hall!
🔗

Example 3.3.2. Definition of a Limit.

The definition of the limit of a function: For every ϵ>0, there exists a δ>0 such that if |x−a|<δ then |f(x)−L|<ϵ. Or in symbols, ∀ϵ>0,∃δ>0,|x−a|<δ→|f(x)−L|<ϵ.
🔗
🔗
Now, we want to be able to negate statements with multiple quantifiers. There is nothing really new here, we just negate our quantified statements as we did for single quantifiers.
🔗

Negating Statements with Multiple Quantifiers.

The negation of ∀x∈D,∃y∈E,P(x,y) is ∃x∈D,∀y∈E,∼P(x,y);
🔗
In notation,
∼(∀x∈D,∃y∈E,P(x,y))≡∃x∈D,∀y∈E,∼P(x,y).
🔗
The negation of ∃x∈D,∀y∈E,P(x,y) is ∀x∈D,∃y∈E,∼P(x,y);
🔗
In notation,
∼(∃x∈D,∀y∈E,P(x,y))≡∀x∈D,∃y∈E,∼P(x,y).
🔗
The negation of ∀x∈D,∀y∈E,P(x,y) is ∃x∈D,∃y∈E,∼P(x,y);
🔗
In notation,
∼(∀x∈D,∀y∈E,P(x,y))≡∃x∈D,∃y∈E,∼P(x,y).
🔗
The negation of ∃x∈D,∃y∈E,P(x,y) is ∀x∈D,∀y∈E,∼P(x,y);
🔗
In notation,
∼(∃x∈D,∃y∈E,P(x,y))≡∀x∈D,∀y∈E,∼P(x,y).
🔗
🔗

Example 3.3.3. Negating the Definition of a Limit.

If you take Elementary Analysis, you will need to be able to negate the definition of the limit from Example 3.3.2. Negate “For every ϵ>0, there exists a δ>0 such that if |x−a|<δ then |f(x)−L|<ϵ.” Hint: Our statement has the form ∀ϵ,∃δ,P(δ)→Q(ϵ). So the negation has the form ∃ϵ,∀δ,P(δ)∧∼Q(ϵ).
🔗
Answer.
∃ϵ>0,∀δ>0,|x−a|<δ∧|f(x)−L|≥ϵ.
🔗
🔗

Activity 3.3.2.

Write the negation of the following statements. Then determine whether the original statment is true or false.
🔗

(a)

There exists an integer n such that for all integers m, nm=0.
🔗
🔗

(b)

For every integer n there exists an integer m such that nm=0.
🔗
🔗
🔗

Activity 3.3.3.

Write the negation of the following statements. Then determine whether the original statment is true of false.
🔗

(a)

There exists an integer n such that for all integers m, n+m=0.
🔗
🔗

(b)

For every integer n there exists an integer m such that n+m=0.
🔗
🔗
🔗

Example 3.3.4. Translating Statements with Multiple Quantifiers.

Let L(x,y) be “x loves y”. Translate each of the following statements using quantifiers and variables.
🔗
Someone loves everyone.
🔗
Answer 1.
∃x,∀y,L(x,y).
🔗
Someone is loved by everyone.
🔗
Answer 2.
∃x,∀y,L(y,x).
🔗
Everyone loves someone.
🔗
Answer 3.
∀x,∃y,L(x,y).
🔗
Everyone is loved by someone.
🔗
Answer 4.
∀x,∃y,L(y,x).
🔗
🔗

Reading Questions Check Your Understanding

1.

Write the negation of ∀x∈R,∃y∈R,xy>0.
🔗
🔗

2.

    True or False: ∀x∈R,∃y∈R,xy>0.
    🔗

  • True.

  • If x=0, no y will have xy>0.

  • False.

  • If x=0, no y will have xy>0.
🔗

3.

Write the negation of ∃x∈R,∀y∈R,xy>0.
🔗
🔗

4.

    True or False: ∃x∈R,∀y∈R,xy>0.
    🔗

  • True.

  • No matter which x you choose, y=−x will have xy≤0.

  • False.

  • No matter which x you choose, y=−x will have xy≤0.
🔗

5.

Write the negation of ∀n∈{even integers},∃k∈Z,n=2k.
🔗
🔗

6.

    True or False: ∀n∈{even integers},∃k∈Z,n=2k.
    🔗

  • True.

  • Every even integer is 2 times an integer.

  • False.

  • Every even integer is 2 times an integer.
🔗
🔗

Exercises Exercises

1.

Let D=E={−2,−1,0,1,2}. Explain why each of the following statements are true.
🔗
  1. ∀x∈D, ∃y∈E, such that x+y=0.
    🔗
    🔗
  2. ∃x∈D such that ∀y∈E,x+y=y.
    🔗
    🔗
🔗

2.

Let D=E={−2,−1,0,1,2}. Write the negations for each of the following statements and determine which is true, the given statement or the negation.
🔗
  1. ∀x∈D, ∃y∈E, such that x+y=1.
    🔗
    🔗
  2. ∃x∈D such that ∀y∈E,x+y=−y.
    🔗
    🔗
  3. ∀x∈D, ∃y∈E, such that xy≥y.
    🔗
    🔗
  4. ∃x∈D such that ∀y∈E,x≤y.
    🔗
    🔗
🔗

3.

For each of the following, (1) rewrite the statement in English without the symbols ∀ or ∃ or variables. Then (2) indicate whether the statement is true or false.
🔗
  1. ∀ real numbers x, ∃ a real number y such that x+y=0.
    🔗
    🔗
  2. ∃ a real number y such that ∀ real numbers x, x+y=0.
    🔗
    🔗
🔗

4.

For each of the following, (1) rewrite the statement in English without the symbols ∀ or ∃ or variables, trying to express your answer as simply as possible. Then (2) write the negation for each statement.
🔗
  1. ∀ colors C, ∃ a candy A such that A is colored C.
    🔗
    🔗
  2. ∀ odd integers n, ∃ an integer k such that n=2k+1.
    🔗
    🔗
  3. ∃ a real number u such that ∀ real numbers v, uv=v.
    🔗
    🔗
🔗

5.

For each of the following, (1) write a new statement by interchanging the symbols ∀ and ∃. Then (2) state which is true: the given statement, the interchanged statement, neither, or both.
🔗
  1. ∀x∈R, ∃y∈R such that x<y.
    🔗
    🔗
  2. ∃x∈R such that ∀y∈R− (the set of negative real numbers), x>y.
    🔗
    🔗
🔗

6.

For each of the following statements, (1) rewrite the statement formally using quantifiers and variables, and (2) write the negation for the statement.
🔗
  1. Everybody trusts somebody.
    🔗
    🔗
  2. Any even integer equals twice some integer.
    🔗
    🔗
🔗

7.

Determine whether the following statements are true or false. Give a sentence or two explaining your answer.
🔗
  1. ∀x∈Z+, ∃y∈Z+ such that x=y+1.
    🔗
    🔗
  2. ∀x∈Z, ∃y∈Z such that x=y+1.
    🔗
    🔗
  3. ∃x∈R, such that ∀y∈R, x=y+1.
    🔗
    🔗
  4. ∀x∈R+, ∃y∈R+ such that xy=1.
    🔗
    🔗
  5. ∀x∈R, ∃y∈R such that xy=1.
    🔗
    🔗
🔗
🔗
You have attempted 1 of 7 activities on this page.
🔗
PrevTopNext