2.7: Quantifiers
( \newcommand{\kernel}{\mathrm{null}\,}\)
Propositional Function
The expression x>5
Example 2.7.1
Denote the propositional function “x>5” by p(x). We often write p(x):x>5.
Example 2.7.2
Define q(x,y):x+y=1.
- q(x,y)
- q(x,3)
- q(1,1)
- 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 2.7.1
Determine the truth values of these statements, where q(x,y) is defined in Example 2.7.2.
- q(5,−7)
- q(−6,7)
- 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 ∀xp(x),
“for all x, p(x)”.
The symbol ∀ is called the universal quantifier, and can be extended to several variables.
Example 2.7.3
The statement
“For any real number x, we always have x2≥0”
is true. Symbolically, we can write
∀x∈R(x2≥0),or∀x(x∈R⇒x2≥0).
The second form is a bit wordy, but could be useful in some situations.
Example 2.7.4
The statement ∀x∈R(x>5)
However, examples cannot be used to prove a universally quantified statement. Consider the statement ∀x∈R(x2≥0).
Example 2.7.5
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: ∀x(x is a Discrete Mathematics student⇒x has taken Calculus I and Calculus II)
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, ∃xp(x),
“There exists x such that p(x).”
The symbol ∃ 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 2.7.6
To prove that a statement of the form “∃xp(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
- ∃x∈R(x>5)
- ∃x∈R(√x=0)
are true?
- Answer
-
- True. For example: x=6.
- True. For example: x=0.
Example 2.7.7
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 2.7.2
Name a few more examples of twin primes.
Example 2.7.8
The proposition
“There exists a real number x such that x>5”
can be expressed, symbolically, as ∃x∈R(x>5),or∃x(x∈R∧x>5).
hands-on Exercise 2.7.3
Determine the truth value of each of the following propositions:
- For any prime number x, the number x+1 is composite.
- For any prime number x>2, the number x+1 is composite.
- There exists an integer k such that 2k+1 is even.
- For all integers k, the integer 2k is even.
- For any real number x, if x2 is an integer, then x is also an integer.
hands-on Exercise 2.7.4
The proposition
“The square of any real number is positive”
is a universal quantification
“For any real number x, x2>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:
¯∀xP(x)≡∃x¯P(x)
and
¯∃xP(x)≡∀x¯P(x)
hands-on Exercise 2.7.5
Negate the propositions in Hands-On Exercise 2.7.3
Example 2.7.9
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.”
hands-on Exercise 2.7.6
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 “∀xp(x)” and “∃xp(x)” respectively.
- To negate a quantified statement, change ∀ to ∃, and ∃ to ∀, and then negate the statement.
Exercises 2.7.
Exercise 2.7.1
Consider these propositional functions:
p(n): | n is prime |
q(n): | n is even |
r(n): | n>2 |
Express these formulas in words:
- ∃n∈Z(p(n)∧q(n))
- ∀n∈Z[r(n)⇒p(n)∨q(n)]
- ∃n∈Z[p(n)∧(q(n)∨r(n))]
- ∀n∈Z[(p(n)∧q(n))⇒¯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≤2.
Exercise 2.7.2
Write each of the following statements in symbolic form:
- For every even integer n there exists an integer k such that n=2k.
- There exists a right triangle T that is an isosceles triangle.
- Given any quadrilateral Q, if Q is a parallelogram and Q has two adjacent sides that are perpendicular, then Q is a rectangle.
Exercise 2.7.3
Determine whether these statements are true or false:
- There exists an even prime integer.
- There exist integers s and t such that 1<s<t<187 and st=187.
- Given any real numbers x and y, x2−2xy+y2>0.
- Answer
-
(a) true (b) true (c) false
Exercise 2.7.4
Determine whether these statements are true or false:
- There is a rational number x such that x2≤0.
- For all x∈Z, either x is even, or x is odd.
- There exists a unique number x such that x2=1.
Exercise 2.7.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 2.7.6
Negate this universal conditional statement.
∀x∈R(x<0→x+1<0).
- Answer
-
∃x∈R(x<0∧x+1≥0).
Exercise 2.7.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. ∀studentsx(x does not want a final exam on Saturday).
b. ∃astudentx(x does want a final exam on Saturday).
c. Some student does want a final exam on Saturday.
Exercise 2.7.8
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 x1 and x2 such that x1<x2 and x31−x1>x32−x2.
Exercise 2.7.9
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, ∀PQRS(PQRS is a square⇒PQRS is a parallelogram), but the statement “a square must not be a parallelogram” means ∀PQRS(PQRS is a square⇒PQRS is not a parallelogram). The second statement is not the negation of the first. The correct negation, in symbol, is ∃PQRS(PQRS is a square∧PQRS is a parallelogram). In words, it means “there exists a square that is not a parallelogram.”
Exercise 2.7.10
Negate these statements:
- All squared numbers are positive.
- All basketball players are over 6 feet tall.
- No quarterback is under 6 feet tall.