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

*1*.*6* *Proving* *an* ""*If* *and* *Only* *If*“ *13*

1.5.2 Method #2‐ Prove the Contrapositive

An implication $\mathrm{(}\mathit{P}$ IMPLIES $\mathit{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* $\mathit{r}$ *is* *irrational*, *then* $\sqrt{\mathit{r}}$ *is* *also* *irrational*.

A number is *rational* when it equals a quotient of integers —that is, if it equals $\mathit{m}\mathrm{/}\mathit{n}$ for some integers $\mathit{m}$ and $\mathit{n}$. If it's not rational, then it's called *irrational*. So we must show that if $\mathit{r}$ is *not* a ratio of integers, then $\sqrt{\mathit{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 $\sqrt{\mathit{r}}$ is rational, then $\mathit{r}$ is rational.

Assume that $\sqrt{\mathit{r}}$ is rational. Then there exist integers $\mathit{m}$ and $\mathit{n}$ such that:

$\sqrt{\mathit{r}}\mathrm{=}\frac{\mathit{m}}{\mathit{n}}$

Squaring both sides gives:

$\mathit{r}\mathrm{\u205f}\mathrm{=}\frac{{\mathit{m}}^{\mathrm{2}}}{{\mathit{n}}^{\mathrm{2}}}$

Since ${\mathit{m}}^{\mathrm{2}}$ and ${\mathit{n}}^{\mathrm{2}}$ are integers, $\mathit{r}$ is also rational. $\mathrm{\blacksquare}$

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.“