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 quantified statements true.

Background

This problem set is based on material in section 2.4 of our textbook and class discussions on February 8 and 10.

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, prove that the statement is true. In the English statements, you may use words synonymous with the quantifiers, just not the quantifier symbols.

Problem 3

Classify each of the following as true or false, and justify each answer. Recall that for purposes of this course, the natural numbers are 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 4 (Proofs Out Of Context)

(This problem is adapted from a set of out of context problems for Math 239 courtesy of Prof. Olympia Nicodemi.)

Assume the following is true:

Fact 1. For all real numbers x and y, if x > 0 then there is a natural number n such that nx > y.

Use Fact 1 to prove the following two claims:

Proposition 1. For all real numbers x, if x > 0 then there is a natural number n such that 0 < 1/n < x.

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.