Problem Set 5—Proofs by Contradiction and Cases

Purpose

This problem set reinforces your understanding of proof by contradiction, and of proofs in cases.

Background

Our textbook covers proof by contradiction in section 3.3. We discussed it in class on February 19, and in two online discussions between February 21 and 23. Proof by cases is from section 3.4 of the textbook, and the February 26 and 28 classes.

Activity

Prove the following. All your proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text, particularly the guideline of stating early in a proof what technique is being used.

Proposition 1

The proposition implied by exercise 8b in section 3.3 of our textbook. You will need to start by formulating the proposition, assuming that the special case in part a is true (The proposition from part a is “for all real numbers x, x + √2 is irrational, or -x + √2 is irrational”; see the textbook for more information).

Proposition 2

Exercise 13d in section 3.3 of Sundstrom’s text (prove that for all real numbers a and b, if a > 0 and b > 0, then 2/a + 2/b ≠ 4 / (a+b)).

Proposition 3

Exercise 5a in section 3.4 of Sundstrom’s text (prove that for all integers a, b, and d with d ≠ 0, if d divides a or d divides b, then d divides ab).

Proposition 4

Exercise 7 in section 3.4 of Sundstrom’s text (determine whether it is true or false that for all integers n, if n is odd then 8 | (n²-1); prove the proposition or provide a counterexample, according to whether you think it is true or false). The notation a | b means “a divides b,” i.e., b = ka for some integer k.

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 contradiction in proofs, (2) how to use cases in proofs, and (3) how to use conventions of formal proof writing in both proof styles.
• Three quarters of what I expect (6 points). A plausible, but not the only, example of a solution that would meet three quarters of my expectations for this problem set is one in which you understand both proof styles, but fail in multiple places to use proper formal conventions.
• Half of what I expect (4 points). Some plausible, but not the only, examples of solutions that would meet half my expectations include ones that show you do not understand one proof style but do understand the other, regardless of how formally the proofs are expressed, OR solutions that show you partially understand both styles (regardless of level of formality).
• 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.