
# 2.6: Logical Quantiﬁers

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

The expression $x>5$ is neither true nor false. In fact, we cannot even determine its truth value unless we know the value of $$x$$. This is an example of a propositional function, because it behaves like a function of $$x$$, it becomes a proposition when a specific value is assigned to $$x$$. Propositional functions are also called predicates.

Example $$\PageIndex{1}$$

Denote the propositional function “$$x > 5$$” by $$p(x)$$. We often write $p(x): \quad x>5.$ It is not a proposition because its truth value is undecidable, but $$p(6)$$, $$p(3)$$ and $$p(-1)$$ are propositions.

Example $$\PageIndex{2}\label{eg:quant-02}$$

Define $q(x,y): \quad x+y=1.$ Which of the following are propositions; which are not?

1. $$q(x,y)$$
2. $$q(x,3)$$
3. $$q(1,1)$$
4. $$q(5,-4)$$

For those that are, determine their truth values.

Both (a) and (b) are not propositions, because they contain at least one variable. Both (c) and (d) are propositions; $$q(1,1)$$ is false, and $$q(5,-4)$$ is true.

hands-on Exercise $$\PageIndex{1}\label{he:quant-01}$$

Determine the truth values of these statements, where $$q(x,y)$$ is defined in Example 2.6.2.

1. $$q(5,-7)$$
2. $$q(-6,7)$$
3. $$q(x+1,-x)$$

Although a propositional function is not a proposition, we can form a proposition by means of quantification. The idea is to specify whether the propositional function is true for all or for some values that the underlying variables can take on.

Definition

The universal quantification of $$p(x)$$ is the proposition in any of the following forms:

• $$p(x)$$ is true for all values of $$x$$.
• For all $$x$$, $$p(x)$$.
• For each $$x$$, $$p(x)$$.
• For every $$x$$, $$p(x)$$.
• Given any $$x$$, $$p(x)$$.

All of them are symbolically denoted by $\forall x \, p(x),$ which is pronounced as

“for all $$x$$, $$p(x)$$”.

The symbol $$\forall$$ is called the universal quantifier, and can be extended to several variables.

Example $$\PageIndex{3}\label{eg:quant-03}$$

The statement

“For any real number $$x$$, we always have $$x^2\geq0$$”

is true. Symbolically, we can write

$\forall x \in \mathbb{R} \, (x^2 \geq 0), \qquad\mbox{or}\qquad \forall x \, (x \in \mathbb{R} \Rightarrow x^2 \geq 0).\label{eg:forallx}$

The second form is a bit wordy, but could be useful in some situations.

Example $$\PageIndex{4}\label{eg:quant-04}$$

The statement $\forall x\in\mathbb{R}\, (x > 5)$ is false because $$x$$ is not always greater than 5. To disprove a claim, it suffices to provide only one counterexample. We can use $$x=4$$ as a counterexample.

However, examples cannot be used to prove a universally quantified statement. Consider the statement $\forall x\in\mathbb{R}\, (x^2\geq0).$ By direct calculations, one may demonstrate that $$x^2\geq0$$ is true for many $$x$$-values. But it does not prove that it is true for every $$x$$, because there may be a counterexample that we have not found yet. We have to use mathematical and logical argument to prove a statement of the form “$$\forall x \, p(x)$$.”

Example $$\PageIndex{5}\label{eg:quant-05}$$

The statement

“Every Discrete Mathematics student has taken Calculus I and Calculus II”

is clearly a universally quantified proposition. To express it in a logical formula, we can use an implication: $\forall x \, (x \mbox{ is a Discrete Mathematics student} \Rightarrow x \mbox{ has taken Calculus~I and Calculus~II})$ An alternative is to say $\forall x \in S \, (x \mbox{ has taken Calculus~I and Calculus~II})$ where $$S$$ represents the set of all Discrete Mathematics students. Although the second form looks simpler, we must define what $$S$$ stands for.

Definition

The existential quantification of $$p(x)$$ takes one of these forms:

• There exists an $$x$$ such that $$p(x)$$.
• For some $$x$$, $$p(x)$$.
• There is some $$x$$ such that $$p(x)$$.

We write, in symbol, $\exists x \, p(x),$ which is pronounced as

“There exists $$x$$ such that $$p(x)$$.”

The symbol $$\exists$$ is called the existential quantifier. It can be extended to several variables.

Example $$\PageIndex{6}\label{eg:quant-06}$$

To prove that a statement of the form “$$\exists x \, p(x)$$” is true, it suffices to find an example of $$x$$ such that $$p(x)$$ is true. Using this guideline, can you determine whether these two propositions

1. $$\exists x\in\mathbb{R}\,(x>5)$$
2. $$\exists x\in\mathbb{R}\,(\sqrt{x}=0)$$

are true?

1. True. For example: $$x=6$$.
2. True. For example: $$x=0$$.

Example $$\PageIndex{7}\label{eg:quant-07}$$

The proposition

“There exists a prime number $$x$$ such that $$x+2$$ is also prime”

is true. We call such a pair of primes twin primes.

hands-on Exercise $$\PageIndex{2}\label{he:quant-02}$$

Name a few more examples of twin primes.

Example $$\PageIndex{8}\label{eg:quant-08}$$

The proposition

“There exists a real number $$x$$ such that $$x>5$$”

can be expressed, symbolically, as $\exists x\in\mathbb{R}\, (x>5), \qquad\mbox{or}\qquad \exists x\, (x\in\mathbb{R}\, \wedge x>5).$ Notice that in an existential quantification, we use $$\wedge$$ instead of $$\Rightarrow$$ to specify that $$x$$ is a real number.

hands-on Exercise $$\PageIndex{3}\label{he:quant-03}$$

Determine the truth value of each of the following propositions:

1. For any prime number $$x$$, the number $$x+1$$ is composite. 0.4in
2. For any prime number $$x>2$$, the number $$x+1$$ is composite. 0.4in
3. There exists an integer $$k$$ such that $$2k+1$$ is even. 0.4in
4. For all integers $$k$$, the integer $$2k$$ is even. 0.4in
5. For any real number $$x$$, if $$x^2$$ is an integer, then $$x$$ is also an integer.

hands-on Exercise $$\PageIndex{4}\label{he:quant-04}$$

The proposition

“The square of any real number is positive”

is a universal quantification

“For any real number $$x$$, $$x^2>0$$.”

Is it true or false?

Example $$\PageIndex{9}\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.

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\mathbb{N}less 1$$? Definitely! For example, we can set $$x=2$$. This counterexample shows that the second 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{10}\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. See Example [eg:isostrig].

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 \mathbb{N}ot\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$$.

hands-on Exercise $$\PageIndex{6}\label{he:quant-06}$$

Negate the propositions in Hands-On Exercise 2.6.3.

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$$.”

hands-on Exercise $$\PageIndex{7}\label{he:quant-07}$$

Negate the statement

“Every Discrete Mathematics student has taken Calculus I and Calculus II.”

## Summary and Review

• There are two ways to quantify a propositional function: universal quantification and existential quantification.
• They are written in the form of “$$\forall x\,p(x)$$” and “$$\exists x\,p(x)$$” respectively.
• To negate a quantified statement, change $$\forall$$ to $$\exists$$, and $$\exists$$ to $$\forall$$, and then negate the statement.

Exercise $$\PageIndex{1}\label{ex:quant-01}$$

Consider these propositional functions:

 $$p(n)$$: $$n$$ is prime $$q(n)$$: $$n$$ is even $$r(n)$$: $$n>2$$

Express these formulas in words:

1. $$\exists n\in\mathbb{Z}\,(p(n)\wedge q(n))$$
2. $$\forall n\in\mathbb{Z}\,[r(n)\Rightarrow p(n)\vee q(n)]$$
3. $$\exists n\in\mathbb{Z}\,[p(n)\wedge(q(n)\vee r(n)]$$
4. $$\forall n\in\mathbb{Z}\,[(p(n)\wedge r(n)) \Rightarrow\overline{q(n)}]$$

Exercise $$\PageIndex{2}\label{ex:quant-02}$$

Give a formula for each of the following statements:

1. For every even integer $$n$$ there exists an integer $$k$$ such that $$n=2k$$.
2. There exists a right triangle $$T$$ that is an isosceles triangle.
3. Given any quadrilateral $$Q$$, if $$Q$$ is a parallelogram and $$Q$$ has two adjacent sides that are perpendicular, then $$Q$$ is a rectangle.

Exercise $$\PageIndex{3}\label{ex:quant-03}$$

Determine whether these statements are true or false:

1. There exists an even prime integer.
2. There exist integers $$s$$ and $$t$$ such that $$1<s<t<187$$ and $$st=187$$.
3. There is an integer $$m$$ such that both $$m/2$$ is an integer and, for every integer $$k$$, $$m/(2k)$$ is not an integer.
4. Given any real numbers $$x$$ and $$y$$, $$x^2-2xy+y^2>0$$.
5. For every integer $$n$$, there exists an integer $$m$$ such that $$m>n^2$$.

Exercise $$\PageIndex{4}\label{ex:quant-04}$$

Determine whether these statements are true or false:

1. There is a rational number $$x$$ such that $$x^2\leq0$$.
2. There exists a number $$x$$ such that for every real number $$y$$, $$xy=0$$.
3. For all $$x\in\mathbb{Z}$$, either $$x$$ is even, or $$x$$ is odd.
4. There exists a unique number $$x$$ such that $$x^2=1$$.

Exercise $$\PageIndex{5}\label{ex:quant-05}$$

Find the negation (in simplest form) of each formula.

1. $$\forall x<0\,\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)]$$

Exercise $$\PageIndex{6}\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{7}\label{ex:quant-07}$$

For each statement, (i) represent it as a formula, (ii) find the negation (in simplest form) of this formula, 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$$.

Exercise $$\PageIndex{8}\label{ex:quant-08}$$

For each statement, (i) represent it as a formula, (ii) find the negation (in simplest form) of this formula, and (iii) express the negation in words.

1. There exist rational numbers $$x_1$$ and $$x_2$$ such that $$x_1<x_2$$ and $$x_1^3-x_1 > x_2^3-x_2$$.
2. For all real numbers $$x$$ and $$y$$ there exists an integer $$z$$ such that $$2z=x+y$$.
3. For all real numbers $$x_1$$ and $$x_2$$, if $$x_1^3+x_1-2 = x_2^3+x_2-2$$, then $$x_1=x_2$$.

Exercise $$\PageIndex{9}\label{ex:quant-09}$$

The easiest way to negate the proposition

“A square must be a parallelogram”

is to say

“It is not true that a square must be a parallelogram.”

Yet, it is not the same as saying

“A square must not be a parallelogram.”

Can you explain why? What are other ways to express its negation in words?

Exercise $$\PageIndex{10}\label{ex:quant-10}$$

Negate these statements:

1. All squared numbers are positive.
2. All basketball players are over 6 feet tall.
3. No quarterback is under 6 feet tall.

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$$.