Problem Set 4—Proofs about Conditionals

Purpose

This problem set is mainly intended to reinforce your understanding of proofs involving conditional and biconditional statements. It also develops your ability to reason about quantifiers, and to apply what you are learning in this course out of context.

Background

The main proof techniques related to conditionals and biconditionals in this problem set are from section 3.2 of our textbook. We covered this material in class on February 14. This material rests on ideas about direct proofs from section 3.1, which we discussed in class on February 12.

Section 2.4 talks about quantifiers. We covered this material in class on February 7 and 9.

Activity

Problem 1

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.

1. All natural numbers greater than 9 are also greater than 10
2. Some natural number greater than 9 is also greater than 10
3. For all natural numbers n, there exists some natural number m such that m > n
4. There exists some natural number n such that for all natural numbers m, m > n
5. All natural numbers less than 1 are multiples of 10
6. Some natural number less than 1 is a multiple of 10

Problem 2

Exercise 5 in section 3.2 of our textbook, giving a formal proof if you decide the statement is true. (Exercise 5 asks you to consider the statement that for all integers a and b, if ab is even then a is even or b is even, and to either prove the statement true or give a counter-example to show that it is false.)

Problem 3

Give a formal proof that for all integers n, n is divisible by 6 if and only if n is divisible by 2 and n is divisible by 3.

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.

I will use the following guidelines to grade this problem set:

• What I expect (8 points). Between your written answers and verbal explanations, I expect you to show that you understand (1) how to use the contrapositive to prove a conditional statement, (2) how to prove a biconditional statement, (3) how to determine informally whether a quantified statement is true or false, particularly including cases where the universal set is empty, (4) create proofs outside the context in which you have otherwise done them in this course, and (5) use the conventions of formal proof writing.
• Half of what I expect (4 points). Some plausible, but not the only, examples of solutions that would meet half my expectations include that you fully understand 2 or 3 of the 5 items listed as expected, and don’t understand the others at all, OR you partially understand all 5 items.
• Exceeding expectations (typically 1 point added to what you otherwise earn). Demonstrating that you have significantly engaged with math beyond what is needed to solve the given problems exceeds what I expect.