Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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.

xZyR(xy<1)

yRxZ(xy<1)

Here, R denotes the set of all nonzero real numbers.

Answer
  1. 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 x0, we can pick y=1, which makes xy=x0<1. For x>0, let y=1x+1, then xy=xx+1<1. This concludes the proof that the first statement is true.
  2. Let y=1. Can we find an integer x such that xy1? 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: yRxZ(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 rationaly is irrationalx+y is irrational).

It can also be written as xQyQ(x+y is irrational).
Although this form looks complicated and seems difficult to understand (primarily because it is quite symbolic, hence appears to be abstract and incomprehensible to many students), it provides an easy form for negation. See the discussion below.

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 xZ, we only change it to xZ when we take negation. It should not be negated as xZ. The reason is: we are only negating the quantification, not the membership of x. In symbols, we write

¯xZp(x)xZ¯p(x).

The negation of “xZp(x)” is obtained in a similar manner.

Example 2.8.11

We find ¯xZyR(xy<1)xZyR(xy1),

and ¯yRxZ(xy<1)yRxZ(xy1).
Remember that we do not change the membership of x and y.

Example 2.8.12

The statement

“All real numbers x satisfy x20

can be written as, symbolically, xR(x20). Its negation is xR(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, “xyp(x,y)” is NOT the same as  “yxp(x,y)”, so order makes a difference.

Exercises 2.8.    

Exercise 2.8.1

Determine whether these statements are true or false:

  1. There is an integer m such that both m/2 is an integer and, for every integer k, m/(2k) is not an integer.
  2. For every integer n, there exists an integer m such that m>n2.
  3. 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:

  1. For all real numbers x, there exists an integer y such that p(x,y) implies q(x,y).
  2. There exists a rational number x such that for all integers y, either p(x,y) or r(x,y) is true.
  3. 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.

  1. x<0xRy,zR(y<zxy>xz)
  2. xZ[p(x)q(x)]
  3. x,yR[p(x,y)q(x,y)]
Answer

(a) x<0xRy,zR(y<zxyxz)

(b) xZ[¯p(x)¯q(x)]

(c) x,yR[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.

  1. For all real numbers x and y, x+y=y+x.
  2. For every positive real number x there exists a real number y such that y2=x.
  3. There exists a real number y such that, for every integer x, 2x2+1>x2y.
Answer

(a)

x,yR(x+y=y+x)
x,yR(x+yy+x)
There exist real numbers x and y such that x+yy+x.

(b)

xR+yR(y2=x)
xR+yR(y2x)
There exists a positive real number x such that for all real numbers y, y2x.

(c)

yRxZ(2x2+1>x2y)
yRxZ(2x2+1x2y)
For every real number y, there exists an integer x such that 2x2+1x2y.
  1. 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.


This page titled 2.8: Multiple Quantifiers is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?