]> No Title

""mcs“ —2015/5/18 —1:43 — page 13 —#21

1.6 Proving an ""If and Only If13

1.5.2 Method #2‐ Prove the Contrapositive

An implication (P IMPLIES Q is logically equivalent to its contrapositive

NOT (Q) IMPLIES NOT (P) .

Proving one is as good as proving the other, and proving the contrapositive is some‐ times easier than proving the original statement. If so, then you can proceed as follows:

1. Write, ""We prove the contrapositive:“ and then state the contrapositive.

2. Proceed as in Method #1.

Example

Theorem 1.5.2. If r is irrational, then r is also irrational.

A number is rational when it equals a quotient of integers —that is, if it equals m/n for some integers m and n. If it's not rational, then it's called irrational. So we must show that if r is not a ratio of integers, then r is also not a ratio of integers. That's pretty convoluted! We can eliminate both not's and simplify the proof by using the contrapositive instead.

Proo. We prove the contrapositive: if r is rational, then r is rational.

Assume that r is rational. Then there exist integers m and n such that:

r=mn

Squaring both sides gives:

r=m2n2

Since m2 and n2 are integers, r is also rational.

1.6 Proving an ""If and Only If“

Many mathematical theorems assert that two statements are logically equivalent; that is, one holds if and only if the other does. Here is an example that has been known for several thousand years:

Two triangles have the same side lengths if and only if two side lengths

and the angle between those sides are the same.

The phrase ""if and only if“ comes up so often that it is often abbreviated ""iff.“