Skip to main content

Proof Technique E Equivalences

When a theorem uses the phrase “if and only if” (or the abbreviation “iff”) it is a shorthand way of saying that two if-then statements are true. So if a theorem says “P if and only if Q,” then it is true that “if P, then Q” while it is also true that “if Q, then P.” For example, it may be a theorem that “I wear bright yellow knee-high plastic boots if and only if it is raining.” This means that I never forget to wear my super-duper yellow boots when it is raining and I would not be seen in such silly boots unless it was raining. You never have one without the other. I have my boots on and it is raining or I do not have my boots on and it is dry.

The upshot for proving such theorems is that it is like a 2-for-1 sale, we get to do two proofs. Assume \(P\) and conclude \(Q\text{,}\) then start over and assume \(Q\) and conclude \(P\text{.}\) For this reason, “if and only if” is sometimes abbreviated by \(\iff\text{,}\) while proofs indicate which of the two implications is being proved by prefacing each with \(\Rightarrow\) or \(\Leftarrow\text{.}\) A carefully written proof will remind the reader which statement is being used as the hypothesis, a quicker version will let the reader deduce it from the direction of the arrow. Tradition dictates we do the “easy” half first, but that is hard for a student to know until you have finished doing both halves! Oh well, if you rewrite your proofs (a good habit), you can then choose to put the easy half first.

Theorems of this type are called “equivalences” or “characterizations,” and they are some of the most pleasing results in mathematics. They say that two objects, or two situations, are really the same. You do not have one without the other, like rain and my yellow boots. The more different \(P\) and \(Q\) seem to be, the more pleasing it is to discover they are really equivalent. And if \(P\) describes a very mysterious solution or involves a tough computation, while \(Q\) is transparent or involves easy computations, then we have found a great shortcut for better understanding or faster computation. Remember that every theorem really is a shortcut in some form. You will also discover that if proving \(P\Rightarrow Q\) is very easy, then proving \(Q\Rightarrow P\) is likely to be proportionately harder. Sometimes the two halves are about equally hard. And in rare cases, you can string together a whole sequence of other equivalences to form the one you are after and you do not even need to do two halves. In this case, the argument of one half is just the argument of the other half, but in reverse.

One last thing about equivalences. If you see a statement of a theorem that says two things are “equivalent,” translate it first into an “if and only if” statement.