Proofs about Conditional Statements

Return to List of Lectures

Previous Lecture

Questions?

Using the Contrapositive

Reading ideas:

• It can sometimes be more efficient to prove P implies Q by proving the contrapositive: not Q implies not P
• To write such a proof
  • Start by saying you’ll use the contrapositive as the proof method
  • Prove the contrapositive of the theorem directly
  • Summarize by noting that having proven the contrapositive you’ve also proven the original theorem

Proposition: For all integers a and b, if ab is a multiple of 4 then a is even or b is even

Proof: We assume that a and b are integers, and want to show that if ab is a multiple of 4, then a is even or b is even. We show this via its contrapositive, i.e., if both a and b are odd then ab is not a multiple of 4. So assume that a and b are odd, and thus a = 2c + 1 and b = 2d + 1 for integers c and d. Then ab = (2c+1)(2d+1) = 2(2cd + c + d) + 1 which is odd, but every multiple of 4 is of the form 4k = 2(2k) for some integer k, which is even. An odd number can’t equal an even number, so ab is not a multiple of four. Hence we have shown the contrapositive of the proposition, and so conclude that if ab is multiple of 4, then a is even or b is even. QED

Biconditionals

Reading ideas:

• P if and only if Q requires P and Q to both be true or both be false, so prove the biconditional by proving that P and Q always have to have same truth value.
• Or treat P if and only if Q as P implies Q and Q implies P and prove both parts separately.
• Proof structure: We prove each part in turn. ...Prove P implies Q.... ...Prove Q implies P.... Having proved both P implies Q and Q implies P we have shown P if and only if Q.

Proposition: For all integers n, n is even if and only if n/2 is an integer.

Proof: We assume that n is an integer and will prove that n is even if and only if n/2 is an integer. We prove the biconditional by proving each direction in turn. To show that if n is even then n/2 is an integer, we assume that n is even, i.e., n = 2x for some integer x. Then by algebra n/2 = 2x/2 = x which we know is an integer. For the other direction, showing that if n/2 is an integer then n is even, we let n/2 = m for some integer m. By algebra, n = 2m which is even by the definition of even integer. Having proven both directions, we conclude that n is even if and only if n/2 is an integer. QED

You could also do the second direction by the contrapositive, i.e., show that if n is odd then n/2 is not an integer. In such a proof, algebra would lead you to arguing that for some integer m, m + 1/2 is not an integer, which is intuitive although we haven’t really developed ways of talking about what real numbers are and aren’t integers.

Proposition: For all real numbers x, 2x - 3 > 0 if and only if x > 3/2

Proof: 2x - 3 > 0 if and only if 2x > 3, which holds if and only if x > 3/2. QED

This is an example of a biconditional proof in which every step itself relies on a biconditional, and so you don’t need to prove each direction separately. Another way to think about it is that you could construct the two directions of the standard proof by making the above argument with implications instead of “if and only if” going from left to right for one direction, and from right to left for the other. Proofs that rely on laws of algebra can often be done this way.

Proposition: For all real numbers x, x =4 if and only if x³ = 64 if and only if x^3/2 = ±8

Proof: x = 4 implies that x³ = 4³ = 64. x³ = 64 implies that x^3/2 = √64 = ±8. x^3/2 = ±8 implies that x = (±8)^2/3 = (±2)² = 4. We have now proved that each statement in the proposition implies the next, from which we see that each statement in fact implies all the others, including the previous one. QED

This example shows that you can prove a chain of biconditionals by proving that each implies the next, and that the last implies the first. This structure usually involves fewer steps than proving both directions for each step in the chain.

Next

Proof by contradiction

Read section 3.3

Next Lecture