Skip to main content
Logo image

Applied Discrete Structures

Section 3.8 Quantifiers

As we saw in Section 3.6, if p(n) is a proposition over a universe U, its truth set Tp is equal to a subset of U. In many cases, such as when p(n) is an equation, we are most concerned with whether Tp is empty or not. In other cases, we might be interested in whether Tp=U; that is, whether p(n) is a tautology. Since the conditions Tpβ‰ βˆ… and Tp=U are so often an issue, we have a special system of notation for them.

Subsection 3.8.1 The Existential Quantifier

Definition 3.8.1. The Existential Quantifier.

If p(n) is a proposition over U with Tpβ‰ βˆ…, we commonly say β€œThere exists an n in U such that p(n) (is true).” We abbreviate this with the symbols (βˆƒn)U(p(n)). The symbol βˆƒ is called the existential quantifier. If the context is clear, the mention of U is dropped: (βˆƒn)(p(n)).

Example 3.8.2. Some examples of existential quantifiers.

  1. (βˆƒk)Z(k2βˆ’kβˆ’12=0) is another way of saying that there is an integer that solves the equation k2βˆ’kβˆ’12=0. The fact that two such integers exist doesn’t affect the truth of this proposition in any way.
  2. (βˆƒk)Z(3k=102) simply states that 102 is a multiple of 3, which is true. On the other hand, (βˆƒk)Z(3k=100) states that 100 is a multiple of 3, which is false.
  3. (βˆƒx)R(x2+1=0) is false since the solution set of the equation x2+1=0 in the real numbers is empty. It is common to write (βˆ„x)R(x2+1=0) in this case.
There are a wide variety of ways that you can write a proposition with an existential quantifier. Table 3.8.5 contains a list of different variations that could be used for both the existential and universal quantifiers.

Subsection 3.8.2 The Universal Quantifier

Definition 3.8.3. The Universal Quantifier.

If p(n) is a proposition over U with Tp=U, we commonly say β€œFor all n in U, p(n) (is true).” We abbreviate this with the symbols (βˆ€n)U(p(n)). The symbol βˆ€ is called the universal quantifier. If the context is clear, the mention of U is dropped: (βˆ€n)(p(n)).

Example 3.8.4. Some Universal Quantifiers.

  1. We can say that the square of every real number is non-negative symbolically with a universal quantifier: (βˆ€x)R(x2β‰₯0).
  2. (βˆ€n)Z(n+0=0+n=n) says that the sum of zero and any integer n is n. This fact is called the identity property of zero for addition.
Table 3.8.5. Notational Variations with Quantified Expressions
Universal Quantifier Existential Quantifier
(βˆ€n)U(p(n)) (βˆƒn)U(p(n))
(βˆ€n∈U)(p(n)) (βˆƒn∈U)(p(n))
βˆ€n∈U,p(n) βˆƒn∈U such that p(n)
p(n),βˆ€n∈U p(n) is true for some n∈U
p(n) is true for all n∈U

Subsection 3.8.3 The Negation of Quantified Propositions

When you negate a quantified proposition, the existential and universal quantifiers complement one another.

Example 3.8.6. Negation of an Existential Quantifier.

Over the universe of animals, define F(x): x is a fish and W(x): x lives in the water. We know that the proposition W(x)β†’F(x) is not always true. In other words, (βˆ€x)(W(x)β†’F(x)) is false. Another way of stating this fact is that there exists an animal that lives in the water and is not a fish; that is,
Β¬(βˆ€x)(W(x)β†’F(x))⇔(βˆƒx)(Β¬(W(x)β†’F(x)))⇔(βˆƒx)(W(x)∧¬F(x)).
Note that the negation of a universally quantified proposition is an existentially quantified proposition. In addition, when you negate an existentially quantified proposition, you get a universally quantified proposition. Symbolically,
Table 3.8.7. Negation of Quantified Expressions
Β¬((βˆ€n)U(p(n)))⇔(βˆƒn)U(Β¬p(n))
Β¬((βˆƒn)U(p(n)))⇔(βˆ€n)U(Β¬p(n))

Example 3.8.8. More Negations of Quantified Expressions.

  1. The ancient Greeks first discovered that 2 is an irrational number; that is, 2 is not a rational number. Β¬((βˆƒr)Q(r2=2)) and (βˆ€r)Q(r2β‰ 2) both state this fact symbolically.
  2. Β¬((βˆ€n)P(n2βˆ’n+41 is prime)) is equivalent to (βˆƒn)P(n2βˆ’n+41 is composite). They are either both true or both false.

Subsection 3.8.4 Multiple Quantifiers

If a proposition has more than one variable, then you can quantify it more than once. For example, p(x,y):x2βˆ’y2=(x+y)(xβˆ’y) is a tautology over the set of all pairs of real numbers because it is true for each pair (x,y) in RΓ—R. Another way to look at this proposition is as a proposition with two variables. The assertion that p(x,y) is a tautology could be quantified as (βˆ€x)R((βˆ€y)R(p(x,y))) or (βˆ€y)R((βˆ€x)R(p(x,y)))
In general, multiple universal quantifiers can be arranged in any order without logically changing the meaning of the resulting proposition. The same is true for multiple existential quantifiers. For example, p(x,y):x+y=4 and xβˆ’y=2 is a proposition over RΓ—R. (βˆƒx)R((βˆƒy)R(x+y=4 and xβˆ’y=2)) and (βˆƒy)R ((βˆƒx)R(x+y=4 and xβˆ’y=2)) are equivalent. A proposition with multiple existential quantifiers such as this one says that there are simultaneous values for the quantified variables that make the proposition true. A similar example is q(x,y):2xβˆ’y=2 and 4xβˆ’2y=5, which is always false; and the following are all equivalent:
Β¬((βˆƒx)R((βˆƒy)R(q(x,y))))⇔¬(βˆƒy)R((βˆƒx)R(q(x,y)))⇔(βˆ€y)R(Β¬((βˆƒx)R(q(x,y))))⇔((βˆ€y)R((βˆ€x)R(Β¬q(x,y))))⇔((βˆ€x)R((βˆ€y)R(Β¬q(x,y))))
When existential and universal quantifiers are mixed, the order cannot be exchanged without possibly changing the meaning of the proposition. For example, let R+ be the positive real numbers, x:(βˆ€a)R+((βˆƒb)R+(ab=1)) and y:(βˆƒb)R+((βˆ€a)R+(ab=1)) have different logical values; x is true, while y is false.
Tips on Reading Multiply-Quantified Propositions. It is understandable that you would find propositions such as x difficult to read. The trick to deciphering these expressions is to β€œpeel” one quantifier off the proposition just as you would peel off the layers of an onion (but quantifiers shouldn’t make you cry!). Since the outermost quantifier in x is universal, x says that z(a):(βˆƒb)R+(ab=1) is true for each value that a can take on. Now take the time to select a value for a, like 6. For the value that we selected, we get z(6):(βˆƒb)R+(6b=1), which is obviously true since 6b=1 has a solution in the positive real numbers. We will get that same truth value no matter which positive real number we choose for a; therefore, z(a) is a tautology over R+ and we are justified in saying that x is true. The key to understanding propositions like x on your own is to experiment with actual values for the outermost variables as we did above.
Now consider y. To see that y is false, we peel off the outer quantifier. Since it is an existential quantifier, all that y says is that some positive real number makes w(b) : (βˆ€a)R+(ab=1) true. Choose a few values of b to see if you can find one that makes w(b) true. For example, if we pick b=2, we get (βˆ€a)R+(2a=1), which is false, since 2a is almost always different from 1. You should be able to convince yourself that no value of b will make w(b) true. Therefore, y is false.
Another way of convincing yourself that y is false is to convince yourself that Β¬y is true:
Β¬((βˆƒb)R+((βˆ€a)R+(ab=1)))⇔(βˆ€b)R+Β¬((βˆ€a)R+(ab=1))⇔(βˆ€b)R+((βˆƒa)R+(abβ‰ 1))
In words, for each value of b, there is a value for a that makes ab≠1. One such value is a=1b+1. Therefore, ¬y is true.
One final example that serves as a preview to how quantifiers appear in calculus.

Example 3.8.9. The Limit of a Sequence.

What does it mean that 0.999… = 1? The ellipsis (…) implies that there are an infinite number of 9’s on the left of the equals sign. Any way to try to justify this equality boils down to the idea of limits. After many years of struggling with what this means, mathematicians have come up with a universally accepted interpretation involving quantifiers. It is that
(βˆ€Ο΅)R+((βˆƒN)P)(nβ‰₯Nβ‡’|1βˆ’0.99..9⏟n9β€²s|<Ο΅))
In calculus, the symbol Ο΅ is usually reserved for small positive real numbers. Let’s pick a value for Ο΅ and peel the universal quantifier off the statement above. Let’s try Ο΅ equal to 1210=11024. In addition we note that 0.99..9⏟n9β€²s=1βˆ’110n. With our choice of Ο΅ we get
(βˆƒN)P(nβ‰₯Nβ‡’|1βˆ’0.99..9⏟n9β€²s|<11024)
or
(βˆƒN)P(nβ‰₯Nβ‡’110n<11024)
This last statement is true - one value of N that would work is 11. You just have to convince yourself that any positive value of Ο΅, no matter how small, will produce a true statement. If you see that, you’ve convinced yourself that 0.999β‹―=1!

Exercises 3.8.5 Exercises

1.

Let C(x) be β€œx is cold-blooded,” let F(x) be β€œx is a fish,” and let S(x) be β€œx lives in the sea.”
  1. Translate into a formula: Every fish is cold-blooded.
  2. Translate into English: (βˆƒx)(S(x)∧¬F(x)).
  3. Translate into English: (βˆ€x)(F(x)β†’S(x)).
Answer.
  1. (βˆ€x)(F(x)β†’C(x))
  2. There are objects in the sea which are not fish.
  3. Every fish lives in the sea.

2.

Let M(x) be β€œx is a mammal,” let A(x) be β€œx is an animal,” and let W(x) be β€œx is warm-blooded.”
  1. Translate into a formula: Every mammal is warm-blooded.
  2. Translate into English: (βˆƒx)(A(x)∧(Β¬M(x))).

3.

Over the universe of books, define the propositions B(x): x has a blue cover, M(x): x is a mathematics book, U(x): x is published in the United States, and R(x,y) : The bibliography of x includes y.
Translate into words:
  1. (βˆƒx)(Β¬B(x)).
  2. (βˆ€x)(M(x)∧U(x)β†’B(x)).
  3. (βˆƒx)(M(x)∧¬B(x)).
  4. (βˆƒy)((βˆ€x)(M(x)β†’R(x,y))).
  5. Express using quantifiers: Every book with a blue cover is a mathematics book.
  6. Express using quantifiers: There are mathematics books that are published outside the United States.
  7. Express using quantifiers: Not all books have bibliographies.
Answer.
  1. There is a book with a cover that is not blue.
  2. Every mathematics book that is published in the United States has a blue cover.
  3. There exists a mathematics book with a cover that is not blue.
  4. There exists a book that appears in the bibliography of every mathematics book.
  5. (βˆ€x)(B(x)β†’M(x))
  6. (βˆƒx)(M(x)∧¬U(x))
  7. (βˆƒx)((βˆ€y)(Β¬R(x,y))

4.

Let the universe of discourse, U, be the set of all people, and let M(x,y) be β€œx is the mother of y.”
Which of the following is a true statement? Translate it into English.
  1. (βˆƒx)U((βˆ€y)U(M(x,y)))
  2. (βˆ€y)U((βˆƒx)U(M(x,y)))
  3. Translate the following statement into logical notation using quantifiers and the proposition M(x,y) : β€œEveryone has a maternal grandmother.”

5.

Translate into your own words and indicate whether it is true or false that (βˆƒu)Z(4u2βˆ’9=0).
Answer.
The equation 4u2βˆ’9=0 has a solution in the integers. (False)

7.

What do the following propositions say, where U is the power set of {1,2,…,9}? Which of these propositions are true?
  1. (βˆ€A)U|A|β‰ |Ac|.
  2. (βˆƒA)U(βˆƒB)U(|A|=5,|B|=5, and A∩B=βˆ…).
  3. (βˆ€A)U(βˆ€B)U(Aβˆ’B=Bcβˆ’Ac).
Answer.
  1. Every subset of U has a cardinality different from its complement. (True)
  2. There is a pair of disjoint subsets of U both having cardinality 5. (False)
  3. Aβˆ’B=Bcβˆ’Ac is a tautology. (True)

8.

Use quantifiers to state that for every positive integer, there is a larger positive integer.

9.

Use quantifiers to state that the sum of any two rational numbers is rational.
Answer.
(βˆ€a)Q(βˆ€b)Q(a+b is a rational number.)

10.

Over the universe of real numbers, use quantifiers to say that the equation a+x=b has a solution for all values of a and b.
Hint.
You will need three quantifiers.

12.

Prove that (βˆƒx)(βˆ€y)(p(x,y))β‡’(βˆ€y)(βˆƒx)(p(x,y)), but that converse is not true.
You have attempted of activities on this page.