Quantifiers

Return to Course Outline

Previous Lecture

Misc

Grow STEM

Grow STEM ice cream social is a good chance to learn more about Grow STEM and meet members: Wednesday, February 20, 6:30 PM, Newton 209.

Exam 1

The first hour exam is scheduled for next Friday, Feb. 22.

It will cover material from the beginning of the semester through problem set 3 (e.g., mathematical statements, direct proofs, propositional logic, sets, predicates).

Expect 3 to 5 short-answer questions, similar (in my mind at least) to problem set questions.

You’ll have the whole class period to do the test.

Open references (book, notes, online references), but closed person.

Questions?

Problem set question 2: should the requested proof based on a truth table still be formal? Yes, you can embed a truth table in a formal proof (i.e., a proof with appropriate introductory and concluding text, suitable labels for the theorem and proof, proper typographical conventions, etc.)

Statements with Quantifiers

Section 2.4

Interpretation

Paraphrase (∀ x ∈ {4n | n ∈ ℕ}) ( (∃ y ∈ ℤ)(x = 2y) ) in English

Literally: for all x in the set of natural number multiples of 4, there exists an integer y such that x = 2y.

Or: every positive multiple of 4 is even.

Translate symbolic expressions like these in a way that makes the meaning clear, not necessarily word-for-word.

Truth and Falsehood

True or false (and say why)?

• Every person in this room is over 1 year old. True, we can check everyone’s age if we need to.
• Some prime number is odd. True, we can present an example (e.g., 3).
• (∀ n∈ ℤ)((∃ x∈ ℝ)(x>n)). True, the statement means “for every integer there’s a real number greater than it,” and we can argue that this is true, e.g., n + 1 is real and greater than n.
• Every pink elephant in this room is dancing on the tables. True, this illustrates “vacuous truth,” the rule that every statement about all members of an empty set is true. Justify this from the use of conditionals to describe universal statements (“if there is a pink elephant in this room, then it is dancing on the tables” is true because its hypothesis is false) or by a counting argument (the number of pink elephants in the room is 0, which equals the number dancing on the tables, so all 0 in the room are dancing on the tables).
• Some pink elephant in this room is dancing on the tables. False, no example can be shown.
• Some pink elephant in this room is not dancing on the tables. Also false, for the same reason.

Negations

So “some pink elephant in this room is not dancing on the tables” is clearly not the negation of “some pink elephant in this room is dancing on the tables.” What is the negation of “Some pink elephant in this room is dancing on the tables”?

“Every pink elephant is not dancing on the tables.”

How about the negation of “Every real number is less than 0”?

“Some real number is greater than or equal to 0.”

To negate a quantified statement, you change the quantifier and then move the negation inside.

For example: negate (∀ n∈ ℤ)((∃ x∈ ℝ)(x>n)).

¬ (∀ n∈ ℤ)((∃ x∈ ℝ)(x>n))

≡ (∃ n∈ ℤ)(¬(∃ x∈ ℝ)(x>n))

≡ (∃ n∈ ℤ)((∀ x∈ ℝ)(¬x>n))

≡ (∃ n∈ ℤ)((∀ x∈ ℝ)(x≤n))

Proofs

What would be a good strategy for proving a universally quantified statement, i.e., one of the form “for all ...”?

Rephrase the statement as a conditional.

How about an existentially quantified statement, one of the form “there exists ...”?

Show an example.

Sometimes you can’t find an example. For instance...

Theorem: there exists a real number x such that x = cos x.

You can’t solve this equation and find x, but you can see that the graphs of y = cos x and y = x cross, or, more rigorously, argue from the Intermediate Value Theorem that cos x - x must equal 0 at some point between x = 0 and x = π/2, because cos x - x is positive at 0, negative at π/2, and continuous on the whole interval.

This is an example of “nonconstructive” proof, i.e., a proof that something exists without actually finding it. This seems frustrating, but is sometimes the only option.

Key Points

The meanings of quantifiers.

Truth and falsehood of quantified statements, particularly vacuous truth.

Rules for negating quantified statements.

Proof strategies for quantified statements.

Next

Start seriously developing a collection of proof techniques.

Start by reviewing direct proof, in a slightly new context (divisibility).

Read section 3.1

Next Lecture