Let \(x, y\in\mathbb{R}\text{.}\) Determine whether the following statements are true or false.
\begin{equation*}
\forall x, \exists y, x+y=5.
\end{equation*}
\begin{equation*}
\exists x, \forall y, x+y=5.
\end{equation*}
Section 3.3 Statements with Multiple Quantifiers
Many statements in mathematics involve multple quantifiers. For example, “For all real numbers \(x\text{,}\) there exists a real number \(y\) with \(x+y=0\text{.}\)” 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\text{.}\)
-
\(\forall x\in D, \exists y\in E, P(x, y)\text{.}\)This means we can find a \(y\) in \(E\) that makes \(P(x, y)\) true for each \(x\) in \(D\text{.}\) In such statements \(y\) will often depend on \(x\text{.}\)
-
\(\exists x\in D, \forall y\in E, P(x, y)\text{.}\)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\text{.}\) In such statements \(x\) does not depend on \(y\text{.}\) The same \(x\) must work for all the \(y\)’s.
-
\(\forall x\in D, \forall y\in E, P(x, y)\text{.}\)
-
\(\exists x\in D, \exists y\in E, P(x, y)\text{.}\)
Example 3.3.1. Statements with Multiple Quantifiers.
Activity 3.3.1.
Let \(x, y\in \mathbb{Z}^{nonneg}\text{.}\) Determine if each statement is true or false. Give a reason for your answer.
(a)
\(\forall x\ \exists y, x < y\text{.}\)
(b)
\(\exists y\ \forall x, x < y\text{.}\)
(c)
\(\exists x\ \forall y, x < y\text{.}\)
(d)
\(\forall y\ \exists x, x < y\text{.}\)
(e)
\(\exists x\ \exists y, x < y\text{.}\)
(f)
\(\forall x\ \forall y, x < y\text{.}\)
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 \(\epsilon>0\text{,}\) there exists a \(\delta>0\) such that if \(|x-a|<\delta\) then \(|f(x)-L|<\epsilon\text{.}\) Or in symbols, \(\forall\epsilon>0, \exists\delta>0, |x-a|<\delta\rightarrow |f(x)-L|<\epsilon\text{.}\)
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 \(\forall x\in D, \exists y\in E, P(x, y)\) is \(\exists x\in D, \forall y\in E, \sim P(x, y)\text{;}\)
In notation,
\begin{equation*}
\sim(\forall x\in D, \exists y\in E, P(x, y))\equiv \exists x\in D, \forall y\in E, \sim P(x, y).
\end{equation*}
The negation of \(\exists x\in D, \forall y\in E, P(x, y)\) is \(\forall x\in D, \exists y\in E, \sim P(x, y)\text{;}\)
In notation,
\begin{equation*}
\sim(\exists x\in D, \forall y\in E, P(x, y))\equiv \forall x\in D, \exists y\in E, \sim P(x, y).
\end{equation*}
The negation of \(\forall x\in D, \forall y\in E, P(x, y)\) is \(\exists x\in D, \exists y\in E, \sim P(x, y)\text{;}\)
In notation,
\begin{equation*}
\sim(\forall x\in D, \forall y\in E, P(x, y))\equiv \exists x\in D, \exists y\in E, \sim P(x, y).
\end{equation*}
The negation of \(\exists x\in D, \exists y\in E, P(x, y)\) is \(\forall x\in D, \forall y\in E, \sim P(x, y)\text{;}\)
In notation,
\begin{equation*}
\sim(\exists x\in D, \exists y\in E, P(x, y))\equiv \forall x\in D, \forall y\in E, \sim P(x, y).
\end{equation*}
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 \(\epsilon>0\text{,}\) there exists a \(\delta>0\) such that if \(|x-a|<\delta\) then \(|f(x)-L|<\epsilon\text{.}\)” Hint: Our statement has the form \(\forall \epsilon, \exists \delta, P(\delta)\rightarrow Q(\epsilon).\) So the negation has the form \(\exists \epsilon, \forall \delta, P(\delta)\wedge \sim Q(\epsilon).\)
Answer.
\(\exists\epsilon>0, \forall\delta>0, |x-a|<\delta\wedge |f(x)-L|\geq\epsilon\text{.}\)
Activity 3.3.2.
Write the negation of the following statements. Then determine whether the original statment is true or false.
(a)
(b)
Activity 3.3.3.
Write the negation of the following statements. Then determine whether the original statment is true of false.
(a)
(b)
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.
\(\exists x, \forall y, L(x, y).\)
Someone is loved by everyone.
Answer 2.
\(\exists x, \forall y, L(y, x).\)
Everyone loves someone.
Answer 3.
\(\forall x, \exists y, L(x, y).\)
Everyone is loved by someone.
Answer 4.
\(\forall x, \exists y, L(y, x).\)
Reading Questions Check Your Understanding
1.
Write the negation of \(\forall x\in \mathbb{R}, \exists y\in \mathbb{R}, xy>0\text{.}\)
2.
True.
- If \(x=0\text{,}\) no \(y\) will have \(xy>0\text{.}\)
False.
- If \(x=0\text{,}\) no \(y\) will have \(xy>0\text{.}\)
True or False: \(\forall x\in \mathbb{R}, \exists y\in \mathbb{R}, xy>0\text{.}\)
3.
Write the negation of \(\exists x\in \mathbb{R}, \forall y\in \mathbb{R}, xy>0\text{.}\)
4.
True.
- No matter which \(x\) you choose, \(y=-x\) will have \(xy\leq 0\text{.}\)
False.
- No matter which \(x\) you choose, \(y=-x\) will have \(xy\leq 0\text{.}\)
True or False: \(\exists x\in \mathbb{R}, \forall y\in \mathbb{R}, xy>0\text{.}\)
5.
Write the negation of \(\forall n\in \{\textrm{even integers}\}, \exists k\in \mathbb{Z}, n=2k\text{.}\)
6.
True.
- Every even integer is 2 times an integer.
False.
- Every even integer is 2 times an integer.
True or False: \(\forall n\in \{\textrm{even integers}\}, \exists k\in \mathbb{Z}, n=2k\text{.}\)
Exercises Exercises
1.
Let \(D=E=\{-2, -1, 0, 1, 2\}\text{.}\) Explain why each of the following statements are true.
2.
Let \(D=E=\{-2, -1, 0, 1, 2\}\text{.}\) Write the negations for each of the following statements and determine which is true, the given statement or the negation.
3.
For each of the following, (1) rewrite the statement in English without the symbols \(\forall\) or \(\exists\) or variables. Then (2) indicate whether the statement is true or false.
4.
For each of the following, (1) rewrite the statement in English without the symbols \(\forall\) or \(\exists\) or variables, trying to express your answer as simply as possible. Then (2) write the negation for each statement.
-
\(\forall\) colors \(C\text{,}\) \(\exists\) a candy \(A\) such that \(A\) is colored \(C\text{.}\)
5.
For each of the following, (1) write a new statement by interchanging the symbols \(\forall\) and \(\exists\text{.}\) Then (2) state which is true: the given statement, the interchanged statement, neither, or both.
-
\(\exists x\in \mathbb{R}\) such that \(\forall y\in \mathbb{R}^-\) (the set of negative real numbers), \(x>y\text{.}\)
6.
For each of the following statements, (1) rewrite the statement formally using quantifiers and variables, and (2) write the negation for the statement.
-
Everybody trusts somebody.
-
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.
-
\(\exists x\in \mathbb{R}\text{,}\) such that \(\forall y\in \mathbb{R}\text{,}\) \(x=y+1\text{.}\)
You have attempted of activities on this page.
