2.8: Multiple Quantifiers

Multiple Quantifiers

Multiple quantifiers can be used.  With more than one quantifier, the order makes a difference.

 

 

Example \(\PageIndex{1}\label{eg:quant-09}\)

When multiple quantifiers are present, the order in which they appear is important. Determine whether these two statements are true or false.

\(\forall x \in \mathbb{Z} \; \exists y \in \mathbb{R}^* \, (xy < 1)\)

\(\exists y \in \mathbb{R}^* \; \forall x \in \mathbb{Z} \, (xy < 1)\)

Here, \(\mathbb{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 \(x\leq 0\), we can pick \(y=1\), which makes \(xy=x\leq0<1\). For \(x>0\), let \(y=\frac{1}{x+1}\), then \(xy=\frac{x}{x+1}<1\). This concludes the proof that the first statement is true.
2. Let \(y=1\). Can we find an integer \(x\) such that \(xy \geq 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 \(\PageIndex{1}\label{he:quant-05}\)

True or false: \(\exists y\in\mathbb{R}\, \forall x\in\mathbb{Z}\, (xy<1)\)?

Example \(\PageIndex{2}\label{eg:quant-10}\)

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. \[\forall x,y\,(x\mbox{ is rational} \wedge y\mbox{ is irrational} \Rightarrow x+y\mbox{ is irrational}).\] It can also be written as \[\forall x\in\mathbb{Q}\,\forall y\notin\mathbb{Q}\, (x+y\mbox{ 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 \(\forall\) and \(\exists\), and negate the statement that is being quantified. In other words,

\[\overline{\forall x\,p(x)} \equiv \exists x\,\overline{p(x)}, \qquad\mbox{and}\qquad \overline{\exists x\,p(x)} \equiv \forall x\,\overline{p(x)}.\]

If we have \(\forall x\in\mathbb{Z}\), we only change it to \(\exists x \in \mathbb{Z}\) when we take negation. It should not be negated as \(\exists x \not\in \mathbb{Z}\). The reason is: we are only negating the quantification, not the membership of \(x\). In symbols, we write

\[\overline{\forall x\in\mathbb{Z}\,p(x)} \equiv \exists x\in\mathbb{Z}\,\overline{p(x)}.\]

The negation of “\(\exists x\in\mathbb{Z}\,p(x)\)” is obtained in a similar manner.

Example \(\PageIndex{11}\label{eg:quant-11}\)

We find \[\overline{\forall x \in \mathbb{Z} \; \exists y \in \mathbb{R}^* \, (xy < 1)} \equiv \exists x\in\mathbb{Z}\; \forall y\in\mathbb{R}^*\,(xy\geq1),\] and \[\overline{\exists y \in \mathbb{R}^* \; \forall x \in \mathbb{Z} \, (xy < 1)} \equiv \forall y\in\mathbb{R}^*\;\exists x\in\mathbb{Z}\,(xy\geq1).\] Remember that we do not change the membership of \(x\) and \(y\).

Example \(\PageIndex{12}\label{eg:quant-12}\)

The statement

“All real numbers \(x\) satisfy \(x^2\geq0\)”

can be written as, symbolically, \(\forall x\in\mathbb{R} \, (x^2 \geq 0)\). Its negation is \(\exists x\in\mathbb{R} \, (x^2 < 0)\). In words, it says “There exists a real number \(x\) that satisfies \(x^2<0\).”

Summary and Review

• Symbolically, here's how to negate statements with quantifiers:   \(\overline{\forall x\,p(x)} \equiv \exists x\,\overline{p(x)}, \qquad\mbox{and}\qquad \overline{\exists x\,p(x)} \equiv \forall x\,\overline{p(x)}.\)
• In general, “\(\forall x\, \exists y\,p(x,y)\)” is NOT the same as  “\(\exists y\,\forall x\,p(x,y)\)”, so order makes a difference.

Exercises \(\PageIndex{}\)    

Exercise \(\PageIndex{1}\label{ex:quant-03}\)

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>n^2\).
3. There exists a real number \(x\) such that for every real number \(y\), \(xy=0\).

Answer

(a) false (b) true (c) true

Exercise \(\PageIndex{2}\label{ex:quant-06}\)

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 \(\PageIndex{3}\label{ex:quant-05}\)

Find the negation (in simplest form) of each symbolic statement.

1. \(\forall x<0 \wedge x\in\mathbb{R}\,\forall y,z\in\mathbb{R}\,(y<z \Rightarrow xy>xz)\)
2. \(\forall x\in\mathbb{Z}\,[p(x)\vee q(x)]\)
3. \(\forall x,y\in\mathbb{R}\,[p(x,y)\Rightarrow q(x,y)]\)

Answer

(a) \(\exists x<0\wedge x\in\mathbb{R}\,\exists y,z\in\mathbb{R}\,(y<z \wedge xy\leq xz)\)

(b) \(\exists x\in\mathbb{Z}\,[\overline{p(x)}\wedge\overline{q(x)}]\)

(c) \(\exists x,y\in\mathbb{R}\,[p(x,y)\wedge\overline{q(x,y)}]\)

 

 

Exercise \(\PageIndex{4}\label{ex:quant-08}\)

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 \(\PageIndex{5}\label{ex:quant-07}\)

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 \(y^2=x\).
3. There exists a real number \(y\) such that, for every integer \(x\), \(2x^2+1>x^2y\).

Answer

(a)

\(\forall x,y\in\mathbb{R}\,(x+y=y+x)\)

\(\exists x,y\in\mathbb{R}\,(x+y\neq y+x)\)

There exist real numbers \(x\) and \(y\) such that \(x+y\neq y+x\).

(b)

\(\forall x\in\mathbb{R}^+\,\exists y\in\mathbb{R}\,(y^2=x)\)

\(\exists x\in\mathbb{R}^+\,\forall y\in\mathbb{R}\,(y^2\neq x)\)

There exists a positive real number \(x\) such that for all real numbers \(y\), \(y^2\neq x\).

(c)

\(\exists y\in\mathbb{R}\,\forall x\in\mathbb{Z}\,(2x^2+1>x^2y)\)

\(\forall y\in\mathbb{R}\,\exists x\in\mathbb{Z}\,(2x^2+1\leq x^2y)\)

For every real number \(y\), there exists an integer \(x\) such that \(2x^2+1\leq x^2y\).

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\).↩