SUNY Geneseo Department of Mathematics
Monday, February 25
Math 239 01
Spring 2019
Prof. Doug Baldwin
I will be away at a conference this Friday. Prof. Johannes will guest lecture that day.
Part of section 3.2.
Prove...
Theorem: for all integers n, n is odd if and only if n+1 is even.
The key idea is that the biconditional is 2 conditionals. So prove that if n is odd then n+1 is even and that if n+1 is even then n is odd
Proof: We assume that n is an integer, and show that n is odd if and only if n+1 is even. We will prove both directions of the conditional separately.
If n is odd, then n = 2a+1 for some integer a. So n+1 = 2a + 1 + 1 = 2a + 2 = 2(a+1). Since integers are closed under addition, a+1 is an integer, and so by the definition of even integer, 2(a+1) is even, and thus n+1 is even.
If n+1 is even, then n+1 = 2a for some integer a, so n = 2a-1 = 2a - 2 + 1 = 2(a-1) + 1. Since the integers are closed under subtraction, a-1 is an integer, and so by the definition of odd integer, n is odd.
Since we have proven both conditionals, we have also proven the biconditional, i.e., we have proven that for all integers n, n is odd if and only if n+1 is even. QED.
(This is my name for a way of proving multiple biconditionals all at once. I don’t know of an “official” name for the technique.)
Suppose you have a series of biconditionals of the form P iff Q iff R iff S .... Rather than prove both directions of each biconditional, you can get away with roughly half as many proofs if you prove that P implies Q, Q implies R, and so forth, and then finally S implies P.
For example...
Theorem: for every real number x, x = 4 if and only if x3 = 64 if and only if x3/2 = ±8.
Proof: We assume that x is a real number, and prove that x = 4 if and only if x3 = 64 if and only if x3/2 = ±8. The proof consists of showing that each part of the statement implies the next.
For the first step, we assume that x = 4. Then by cubing both sides of this equation we see that x3 = 64.
For the next step, suppose that x3 = 64. Then by taking square roots we see √x3 = √64, i.e., x3/2 = ±8.
For the final step, suppose x3/2 = ±8. Taking cube roots of both sides of this equation gives √x = ±2, and then squaring yields x = 4.
We have now shown that x = 4 implies that x3 = 64, which implies that x3/2 = ±8, which finally implies that x = 4. We have thus shown that for all real numbers x, x = 4 if and only if x3 = 64 if and only if x3/2 = ±8. QED.
Sometimes the logic in proving a biconditional is such that you can in fact do each step of the proof as another biconditional, thereby proving both directions at the same time.
For example...
Theorem: for all real numbers x, 3x - 2 > 0 if and only if x > 2/3.
Proof: We will show through a series of biconditionals that for all real numbers x, 3x - 2 > 0 if and only if x > 2/3. To start, note that 3x - 2 > 0 if and only if 3x > 2. This relation in turn holds if and only if x > 2/3. Thus we have shown that for all real numbers x, 3x - 2 > 0 if and only if x > 2/3. QED.
See handout for details.
Proof by contradiction.
Read section 3.3