1.6: Proving an “If and Only If”

Last updated
Save as PDF

Page ID: 49291

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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

Method #1: Prove Each Statement Implies the Other

The statement “\(P \text{ IFF } Q\)” is equivalent to the two statements “\(P \text{ IMPLIES } Q\)” and “\(Q \text{ IMPLIES } P\).” So you can prove an “iff” by proving two implications:

Write, “We prove \(P\) implies \(Q\) and vice-versa.”
Write, “First, we show \(P\) implies \(Q\).” Do this by one of the methods in Section 1.5.
Write, “Now, we show \(Q\) implies \(P\).” Again, do this by one of the methods in Section 1.5.

Method #2: Construct a Chain of Iffs

In order to prove that \(P\) is true iff \(Q\) is true:

Write, “We construct a chain of if-and-only-if implications.”
Prove \(P\) is equivalent to a second statement which is equivalent to a third statement and so forth until you reach \(Q\).

This method sometimes requires more ingenuity than the first, but the result can be a short, elegant proof.

Example

The standard deviation of a sequence of values x₁, x_{2, ... ,}x_n is defined to be:

\[\label{1.6.1} \sqrt{\frac{(x_1 - \mu)^2 + (x_2 - \mu)^2 + \cdots + (x_n - \mu)^2}{n}}\]

where \(\mu\) is the average or mean of the values:

\[\nonumber \mu ::= \frac{x_1 + x_2 + \cdots + x_n}{n}\]

Theorem \(\PageIndex{1}\)

The standard deviation of a sequence of values \(x_1, x_2, \ldots, x_n\) is zero iff all the values are equal to the mean.

For example, the standard deviation of test scores is zero if and only if everyone scored exactly the class average.

Proof. We construct a chain of “iff” implications, starting with the statement that the standard deviation (\ref{1.6.1}) is zero:

\[\label{1.6.2} \sqrt{\frac{(x_1 - \mu)^2 + (x_2 - \mu)^2 + \cdots + (x_n - \mu)^2}{n}} = 0.\]

Now since zero is the only number whose square root is zero, equation (\ref{1.6.2}) holds iff

\[\label{1.6.3} (x_1 - \mu)^2 + (x_2 - \mu)^2 + \cdots + (x_n - \mu)^2 = 0.\]

Squares of real numbers are always nonnegative, so every term on the left hand side of equation (\ref{1.6.3}) is nonnegative. This means that (\ref{1.6.3}) holds iff

\[\label{1.6.4} \text{Every term on the left hand side of } (\ref{1.6.3}) \text{ is zero}.\]

But a term \((x_i - \mu )^2\) is zero iff \(x_i = \mu\), so (\ref{1.6.4}) is true iff

\[\nonumber \text{Every } x_i \text{ equals the mean.} \quad \blacksquare\]