Introduction to Quantifiers

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Misc

Next Tuesday (March 2) is the semester’s first rejuvenation day. It doesn’t affect this course directly, but in the spirit of getting a bit of a break from academic worries, I’m discouraging individual meetings that day (well, slightly discouraging them — if you want one you can certainly have it, but if you’d rather not, I think that’s a good idea in the spirit of the day). I also won’t hand out a new problem set today, so you’ll have a bit of a break from working on problem sets for the beginning of the week.

Quantifiers

From “Beginning Activity 1 (An Introduction to Quantifiers)” and “Forms of Quantified Statements in English” in section 2.4 of the textbook and this discussion of quantifiers .

What Quantifiers Mean

These mostly have good answers in the discussion, but it’s worth reviewing those answers and talking about why they’re correct.

Determine whether the following statements are true or false, and rewrite each using the quantifier symbols “∀” and “∃.”

1. For all natural numbers n, n > 0. (∀n ∈ ℕ)(n>0). True, because natural numbers are defined as integers greater than or equal to 1 (some people actually define them as greater than or equal to 0, but our textbook uses 1, so that’s what we’ll use).
2. Every natural number is greater than -1. (∀n ∈ ℕ)(n>-1). True, as in #1.
3. There exists an integer n such that n > 0. (∃n ∈ ℤ)(n>0). True because there’s at least 1 such integer, for example 1. 
4. Some integer is negative. (∃n ∈ ℤ)(n<0).  True, because like in #3 we can find examples.
5. If y is a real number, then ln y > 0. (∀ x ∈ ℝ)(ln y > 0). False, because while many real numbers have positive logarithms, some have negative logarithms, or complex ones.
6. Sometimes ln y > 0, where y is a real number. (∃ y ∈ ℝ)(ln y > 0). True, because any real number greater than 1 has a positive logarithm.
7. One or more of the integers is less than 10. (∃ n ∈ ℤ)(n < 10). True, we can find examples.

Determine whether the following are true or false, and say why, and see if you can rephrase each in English, without quantifier symbols:

1. (∀ x ∈ ℝ)(x ∈ ℚ). “For every real number x, x is a rational number,” or “every real number is also rational”. False, there are irrational real numbers.
2. (∃ x ∈ ℝ)(x ∈ ℚ). “Some real numbers are also rational.” True because you can have a real number that’s rational, for example 1/2.
3. (∃ n ∈ ℤ)(n > 8 ∧ n < 5). “There exists an integer greater than 8 and less than 5”. False, you can’t have a number that’s simultaneously greater than 8 but less than 5.
4. (∀ m ∈ ℤ)(m > 8 ∨ m < 10) “Every integer is greater than 8 or less than 10.” True, any integer that’s not greater than 8 is less than 10 (remember that “or” in math is inclusive, so the fact that 9 is greater than 8 and less than 10 isn’t a problem).

Quantifiers and Empty Sets

Some of the most unintuitive quantified statements involve quantification over an empty set (i.e., statements of the form “there exists an x in S such that …” or “for all x in S, …” where S is an empty set.

For example, is it true or false that some purple Martian in our classroom is writing on the whiteboard while we talk?

False, because there are no examples that make it true.

Is it true or false that every purple Martian in our classroom is writing on the whiteboard while we talk?

True. There are several ways to justify this:

• Think of it as a conditional, “if there are purple Martians in the room, then they’re writing on the board.” Since the hypothesis is false, the overall conditional is true.
• There are no counterexamples to show that it’s false.
• 0 out of the 0 Martians in the room are writing on the board, so that’s all of them.

Years ago, one of my students in another class that was learning about quantifiers came to me with this story: one evening my student, who had never in his life taken a physics course, noticed that his roommate was studying for a physics exam. He walked over to the roommate and casually remarked “just so you know, I got an A in every physics course I ever took.” Was my student telling the truth? Yes.

Can you state a general rule for the truth value of statements that are universally quantified over an empty set? What about for statements that are existentially quantified over an empty set?

(∀ x ∈ ∅)( P(x) ) is always true, for lack of counterexamples.

(∃ x ∈ ∅)( P(x) ) is always false, for lack of examples.

Next

Negations of quantifiers (e.g., statements of the form ¬(∀ x ∈ S) P(x) or ¬(∃x ∈ S) P(x)) are tricky to understand at first, but are often important in understanding quantified statements. This is even more the case when the statement involves multiple quantifiers (which are hard enough to understand even without being negated). So we should study negations and statements with multiple quantifiers.

We explored a couple of examples, and it seemed that negations of existential statements involve universal quantifiers, and negations of universal statements involve existential quantifiers. To learn more about this…

Please read “Beginning Activity 2 (Attempting to Negate Quantified Statements),” “Negations of Quantified Statements,” “Counterexamples and Negations of Conditional Statements,” “Quantifiers in Definitions,” “Statements with More than One Quantifier,” and “Writing Guideline” in section 2.4 of our textbook.

Please also contribute to this discussion of advanced topics in quantifiers.

Next Lecture