SUNY Geneseo Department of Mathematics
Monday, February 19
Math 239 01
Spring 2018
Prof. Doug Baldwin
Problem set on proofs of conditionals.
Section 3.3.
Finish the proof in Preview Activity 2.
Theorem: For all real numbers x and y, if x ≠ y and x > 0 and y > 0, then x/y + y/x > 2.
Proof: We prove by contradiction that for all real numbers x and y, if x ≠ y and x > 0 and y > 0, then x/y + y/x > 2. Assume for the sake of contradiction that x and y are real numbers, x ≠ y, x > 0, and y > 0, but x/y + y/x ≤ 2. Since x and y are both not equal to 0, we can multiply both sides of the last inequality by xy to obtain
x2 + y2 ≤ 2xy
from which we see
x2 + y2 - 2xy ≤ 0
and then by factoring that
(x-y)2 ≤ 0
In order for this last inequality to hold, either x or y isn’t real, contradicting the assumption that both are real, or x = y, contradicting the assumption that x ≠ y. Since all possibilities lead to a contradiction, it is impossible to have x and y be real numbers with x ≠ y, x > 0, and y > 0, but x/y + y/x ≤ 2. We thus conclude that for all real numbers x and y, if x ≠ y and x > 0 and y > 0, then x/y + y/x > 2. QED.
A variation on Progress Check 3.16.
Prove that for all integers x, if x ≡ 4 (mod 8) then x ≢ 5 (mod 6).
Theorem: For all integers x, if x ≡ 4 (mod 8) then x ≢ 5 (mod 6).
Proof: We show by contradiction that for all integers x, if x ≡ 4 (mod 8) then x ≢ 5 (mod 6). Assume for the sake of contradiction that x is an integer and x ≡ 4 (mod 8) and x ≡ 5 (mod 6). Because x ≡ 4 (mod 8) and x ≡ 5 (mod 6), we have x = 8k + 4 for some integer k, and x = 6n + 5 for some integer n. Setting these expressions equal and isolating n and k on different sides of the equation we see
8k + 4 = 6n + 5
8k = 6n + 1
2(4k) = 2(3n)+1
Now the left side of this equation represents an even integer, but the right side represents an odd integer. This is a contradiction, since it is impossible for an even number to equal an odd one. We have thus established that it is impossible to have an integer simultaneously congruent to 4 mod 8 and to 5 mod 6. This in turn proves that for all integers x, if x ≡ 4 (mod 8) then x ≢ 5 (mod 6). QED.
Theorem: For all integers a and b, if ab is not divisible by 9 then at least one of a and b isn’t divisible by 3.
Proof: We use contradiction to prove that for all integers a and b, if ab is not divisible by 9 then at least one of a and b isn’t divisible by 3. Assume for the sake of contradiction that a and b are integers, and ab is not divisible by 9 but both a and b are divisible by 3. In other words, a = 3x and b = 3m for some integers x and m. But then ab = 9xm which is divisible by 9. This contradicts the assumption that ab is not divisible by 9, and so we conclude that there are no integers a and b such that ab is not divisible by 9 but both a and b are divisible by 3. We have therefore proven by contradiction that for all integers a and b, if ab is not divisible by 9 then at least one of a and b isn’t divisible by 3. QED.
The general method of proof by contradiction.
A good way to discover a proof by contradiction is to assume the negation of your theorem and then see where it leads you, keeping an eye out for impossible results along the way.
Why does it matter? Because it is (probably) the first time you have seen an actual proof that irrational numbers exist at all.
Instead of in-person class meetings Wednesday and Friday this week.
Further practice with proof by contradiction. See “Proof by Contradiction Discussion 1” and “Proof by Contradiction Discussion 2” in Canvas.
Graded as a problem set; to meet expectations you must contribute something that demonstrates thought about the problem to at least one of the discussions.
Next Monday (Feb. 26)
Read section 3.4.