Problem Set 5—Quantifiers

Purpose

This problem set develops your ability to reason about quantifiers. In particular, by the time you finish this problem set you should be able to translate between English and symbolic forms of quantified statements, informally determine whether a quantified statement is true or false (including vacuously true statements), negate quantified statements, and prove universally quantified statements true.

Background

This problem set is based on material in section 2.4 of our textbook and class discussions on September 23, 26, and possibly 28.

Activity

Solve the following problems. Formal proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text.

Problem 1

An extension of exercise 3b in section 2.4 of our textbook (considering the symbolic statement (∀x∈ℚ) (x²-2 ≠ 0), give an equivalent English statement, show the negation symbolically without using a negation symbol, and express the negation in English). In addition to what the book asks you to do, determine informally whether the statement is true or false. In the English statements, you may use words synonymous with the quantifiers, just not the quantifier symbols.

Problem 2

An extension of exercise 3d in section 2.4 of our textbook (considering the symbolic statement (∃x∈ℚ) (√2 < x < √3), give an equivalent English statement, show the negation symbolically without using a negation symbol, and express the negation in English). In addition to what the book asks you to do, determine informally whether the statement is true or false. In the English statements, you may use words synonymous with the quantifiers, just not the quantifier symbols.

Problem 3

Exercises 9a and 9b in section 2.4 of our textbook (write symbolic expressions that say what it means for an integer to have and not have a “divides” property; see the textbook for details).

Problem 4

Classify each of the following as true or false, and justify each answer. To remove any doubt, define the natural numbers as the integers strictly greater than 0.

Part A

All natural numbers less than 1 are multiples of 10

Part B

Some natural number less than 1 is a multiple of 10

Problem 5

Formally prove that for every integer n ≥ 1, 2ⁿ is even.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.