2.8: Multiple Quantifiers
( \newcommand{\kernel}{\mathrm{null}\,}\)
Multiple Quantifiers
Multiple quantifiers can be used. With more than one quantifier, the order makes a difference.
Example 2.8.1
When multiple quantifiers are present, the order in which they appear is important. Determine whether these two statements are true or false.
∀x∈Z∃y∈R∗(xy<1)
∃y∈R∗∀x∈Z(xy<1)
Here, R∗ denotes the set of all nonzero real numbers.
- Answer
-
- To prove that the statement is true, we need to show that no matter what integer x we start with, we can always find a nonzero real number y such that xy<1. For x≤0, we can pick y=1, which makes xy=x≤0<1. For x>0, let y=1x+1, then xy=xx+1<1. This concludes the proof that the first statement is true.
- Let y=1. Can we find an integer x such that xy≥1? Definitely! For example, we can set x=2. This counterexample shows that the second statement is false. NOTE: the statement is false, but this is not a valid explanation. Do you see why? What do you need to show an existence statement is false?
hands-on Exercise 2.8.1
True or false: ∃y∈R∀x∈Z(xy<1)?
Example 2.8.2
Many theorems in mathematics can be expressed as quantified statements. Consider
“If x is rational and y is irrational, then x+y is irrational.”
This is same as saying
“Whenever x is rational and y is irrational, then x+y is irrational.”
The keyword “whenever” suggests that we should use a universal quantifier. ∀x,y(x is rational∧y is irrational⇒x+y is irrational).
The fact that an implication can be expressed as a universally quantified statement sounds familiar.
Negation with Multiple Quantifiers
We shall learn several basic proof techniques in Chapter 3. Some of them require negating a logical statement. Since many mathematical results are stated as quantified statements, it is necessary for us to learn how to negate a quantification. The rule is rather simple. Interchange ∀ and ∃, and negate the statement that is being quantified. In other words,
¯∀xp(x)≡∃x¯p(x),and¯∃xp(x)≡∀x¯p(x).
If we have ∀x∈Z, we only change it to ∃x∈Z when we take negation. It should not be negated as ∃x∉Z. The reason is: we are only negating the quantification, not the membership of x. In symbols, we write
¯∀x∈Zp(x)≡∃x∈Z¯p(x).
The negation of “∃x∈Zp(x)” is obtained in a similar manner.
Example 2.8.11
We find ¯∀x∈Z∃y∈R∗(xy<1)≡∃x∈Z∀y∈R∗(xy≥1),
Example 2.8.12
The statement
“All real numbers x satisfy x2≥0”
can be written as, symbolically, ∀x∈R(x2≥0). Its negation is ∃x∈R(x2<0). In words, it says “There exists a real number x that satisfies x2<0.”
Summary and Review
- Symbolically, here's how to negate statements with quantifiers: ¯∀xp(x)≡∃x¯p(x),and¯∃xp(x)≡∀x¯p(x).
- In general, “∀x∃yp(x,y)” is NOT the same as “∃y∀xp(x,y)”, so order makes a difference.
Exercises 2.8.
Exercise 2.8.1
Determine whether these statements are true or false:
- There is an integer m such that both m/2 is an integer and, for every integer k, m/(2k) is not an integer.
- For every integer n, there exists an integer m such that m>n2.
- There exists a real number x such that for every real number y, xy=0.
- Answer
-
(a) false (b) true (c) true
Exercise 2.8.2
Negate the following statements:
- For all real numbers x, there exists an integer y such that p(x,y) implies q(x,y).
- There exists a rational number x such that for all integers y, either p(x,y) or r(x,y) is true.
- For all integers x, there exists an integer y such that if p(x,y) is true, then there exists an integer z so that q(x,y,z) is true.
Exercise 2.8.3
Find the negation (in simplest form) of each symbolic statement.
- ∀x<0∧x∈R∀y,z∈R(y<z⇒xy>xz)
- ∀x∈Z[p(x)∨q(x)]
- ∀x,y∈R[p(x,y)⇒q(x,y)]
- Answer
-
(a) ∃x<0∧x∈R∃y,z∈R(y<z∧xy≤xz)
(b) ∃x∈Z[¯p(x)∧¯q(x)]
(c) ∃x,y∈R[p(x,y)∧¯q(x,y)]
Exercise 2.8.4
For this statement, (i) represent it in symbolic form, (ii) find the symbolic negation (in simplest form), and (iii) express the negation in words.
For all real numbers x and y there exists an integer z such that 2z=x+y.
Exercise 2.8.5
For each statement, (i) represent it in symbolic form, (ii) find the symbolic negation (in simplest form), and (iii) express the negation in words.
- For all real numbers x and y, x+y=y+x.
- For every positive real number x there exists a real number y such that y2=x.
- There exists a real number y such that, for every integer x, 2x2+1>x2y.
- Answer
-
(a)
∀x,y∈R(x+y=y+x) ∃x,y∈R(x+y≠y+x) There exist real numbers x and y such that x+y≠y+x. (b)
∀x∈R+∃y∈R(y2=x) ∃x∈R+∀y∈R(y2≠x) There exists a positive real number x such that for all real numbers y, y2≠x. (c)
∃y∈R∀x∈Z(2x2+1>x2y) ∀y∈R∃x∈Z(2x2+1≤x2y) For every real number y, there exists an integer x such that 2x2+1≤x2y.
-
Some students may not be familiar with matrices. A matrix is rectangular array of numbers. Matrices are important tools in mathematics. The product of two matrices of appropriate sizes is defined in a rather unusual way. It is the peculiar way that two matrices are multiplied that makes matrices so useful in mathematics. The square of a matrix is of course the product of the matrix with itself. It is well-defined only when the matrix is a square matrix. As it turns out, the order of multiplication of two matrices is important. In other words, given any two matrices A and B, it is not always true that AB=BA.↩