2.7: Quantifiers

Propositional Function

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.

Answer

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 \(\PageIndex{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.

Universal Quantifier

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.

 

Existential Quantifier

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.

Notice the pronouciation includes the phrase "such that".  Don't forget to say that phrase as part of the verbalization of a symbolic existential statement.

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?

Answer

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. 
2. For any prime number \(x>2\), the number \(x+1\) is composite. 
3. There exists an integer \(k\) such that \(2k+1\) is even.
4. For all integers \(k\), the integer \(2k\) is even. 
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?

 

Negation with Quantifiers

 

To negate that a proposition always happens, is to say there exists an instance where it does not happen.

To negate that a proposition exists, is to say the proposition always does not happen.

Symbolically:

\(\overline {\forall x P(x)} \equiv \exists x  \overline{P(x)}\)

and 

\(\overline {\exists x P(x)} \equiv \forall x  \overline{P(x)}\)

hands-on Exercise \(\PageIndex{5}\label{he:quant-06}\)

Negate the propositions in Hands-On Exercise \(\PageIndex{3}\)

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

Exercises \(\PageIndex{}\)    

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 q(n)) \Rightarrow\overline{r(n)}]\)

Answer

(a) There exists an integer \(n\) such that \(n\) is prime and \(n\) is even.

(b) For all integers \(n\), if \(n>2\), then \(n\) is prime or \(n\) is even.

(c) There exists an integer \(n\) such that \(n\) is prime, and either \(n\) is even or \(n>2\).

(d) For all integers \(n\), if \(n\) is prime and \(n\) is even, then \(n\leq2\).

 

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

Write each of the following statements in symbolic form:

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. Given any real numbers \(x\) and \(y\), \(x^2-2xy+y^2>0\).

Answer

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

 

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. For all \(x\in\mathbb{Z}\), either \(x\) is even, or \(x\) is odd.
3. There exists a unique number \(x\) such that \(x^2=1\). 

 

Exercise \(\PageIndex{5}\)

Negate this universal conditional statement (think about how a conditional statement is negated).

For all cats, if a cat eats 3 meals a day, then that cat weighs at least 10 lbs.

Answer

There exists a cat that eats 3 meals a day and weighs less than 10 lbs.

Exercise \(\PageIndex{6}\)

Negate this universal conditional statement.

 \(\forall x \in \mathbb{R} (x<0 \rightarrow x+1<0)\).

 

Answer

\(\exists x \in \mathbb{R} (x<0 \wedge x+1\geq 0)\).
 

Exercise \(\PageIndex{7}\)

original: No student wants a final exam on Saturday.

a. Write the original statement symbolically.

b. Negate the original statement symbolically.

C. Negate the original statement informally (in English).

Answer

a. \(\forall \;students \;x\; (x  \mbox{ does not want a final exam on Saturday})\).
b. \(\exists \;a \;student \;x\; (x  \mbox{ does want a final exam on Saturday})\).
c. Some student does want a final exam on Saturday.

Exercise \(\PageIndex{8}\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.

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

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?

Answer

The statement “a square must be a parallelogram” means, symbolically, \[\forall PQRS\,(PQRS \mbox{ is a square} \Rightarrow PQRS \mbox{ is a parallelogram}),\] but the statement “a square must not be a parallelogram” means \[\forall PQRS\,(PQRS \mbox{ is a square} \Rightarrow PQRS \mbox{ is not a parallelogram}).\] The second statement is not the negation of the first. The correct negation, in symbol, is \[\exists PQRS\,(PQRS \mbox{ is a square} \wedge PQRS \mbox{ is a parallelogram}).\] In words, it means “there exists a square that is not a parallelogram.”

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.

---