The notion of equivalence of statements has already been seen to be useful in proving theorems, for example in proof by contrapositive. In this section we will make use of some other equivalences of statements to prove certain types of theorems.
SubsectionCases
Convention2.24.
One commonly used method for proving a statement of the form \(P \to Q\) is by breaking up the proof into a number of cases (and possibly subcases, subsubcases and so on).
Formally, we use proof by cases when the premise \(P\) can be written in the form \(A ∨ B\text{.}\) We then use Exercise 1.3.2 (6) to see that \((A ∨ B) \to Q\) is equivalent to \((A \to Q) \wedge (B \to Q)\text{.}\) Hence, in order to prove that a statement of the form \((A ∨ B) \to Q\) is true, it is sufficient to prove that each of the statements \(A \to Q\) and \(B \to Q\) is true.
Remark2.25.
The use of this strategy often occurs when proving a statement involving a quantifier of the form “for all \(x\) in \(U\text{,}\)” and where no single proof can be found for all such \(x\text{,}\) but where \(U\) can be divided up into two or more parts, and where a proof can be found for each part.
Theorem2.26.
Let \(n\) be an integer. Then \(n^2 + n\) is even.
Remark2.27.
In the proof of Theorem 2.4.1 we had two cases, which together covered all possibilities, and which were exclusive of each other. It is certainly possible to have more than two cases, and it is also possible to have non-exclusive cases; all that is needed is that all the cases combined cover all possibilities. The proof of Theorem 2.4.4 below has two non-exclusive cases.
We now turn to theorems that have statements of the form \(P \to (A ∨ B)\text{.}\) Such theorems are less common than the previously discussed type, but do occur, and it is worth being familiar with the standard proof strategies for such theorems.
Convention2.28.
There are two commonly used strategies, each one being advantageous in certain situations. One approach would be to use the contrapositive together with De Morgan’s Law (Fact 1.3.2 (13)), which together imply that \(P \to (A∨B)\) is equivalent to \((¬A\wedge ¬B) \to ¬P\text{.}\) The other would be to use Exercise 1.3.2 (5), which says that\(P \to (A ∨ B)\) is equivalent to \((P \wedge ¬A) \to B\text{.}\) The roles of \(A\) and \(B\) could also be interchanged in this last statement.
Theorem2.29.
Let \(x\) and \(y\) be real numbers. If \(xy\) is irrational, then \(x\) or \(y\) is irrational.
Suppose that \(xy\) is irrational and that \(x\) is rational. Hence \(x = a/b\) for some integers \(a\) and \(b\) such that \(b \ne 0\text{.}\) We will show that \(y\) is irrational, by using proof by contradiction. Suppose that \(y\) is rational. It follows that \(y = m/n\) for some integers \(m\) and \(n\) such that \(n \ne 0\text{.}\) Hence \(xy = am/bn\text{,}\) and \(bn \ne 0\text{,}\) contradicting the fact that \(xy\) is irrational. Hence \(y\) is irrational.
SubsectionIf and Only If
Whereas the most common logical form of the statement of a theorem is \(P \to Q\text{,}\) as we have discussed so far, another common form is \(P ↔ Q\text{.}\) We refer to such theorems as “if and only if” theorems (often abbreviated “iff” theorems). To prove such a theorem, we make use of the fact that \(P ↔ Q\) is equivalent to \((P \to Q) \wedge (Q \to P)\text{,}\) as was shown in Fact 1.3.2 (11). Hence, to prove a single statement of the form \(P ↔ Q\text{,}\) it is sufficient to prove the two statements \(P \to Q\) and \(Q \to P\text{,}\) each of which can be proved using any of the methods we have seen so far.
Theorem2.30.
Let \(a\) and \(b\) be non-zero integers. Then \(a|b\) and \(b|a\) if and only if \(a = b\) or \(a = -b\text{.}\)
⇒. Suppose that \(a|b\) and \(b|a\text{.}\) Because \(a|b\text{,}\) there is some integer m such that \(am = b\text{,}\) and because \(b|a\text{,}\) there is some integer \(k\) such that \(bk = a\text{.}\) Substituting this last equation into the previous one, we obtain \((bk)m = b\text{,}\) and hence \(b(km) = b\text{.}\) Because \(b \ne 0\text{,}\) it follows that \(km = 1\text{.}\) Because \(k\) and m are integers, then either \(k = 1\) and \(m = 1\text{,}\) or \(k = -1\) and \(m = -1\text{.}\) (We will not provide a proof of this last fact; it is stated as Theorem A.4 in the Appendix.) In the former case \(a = b\text{,}\) and in the latter case \(a = -b\text{.}\)
⇐. Suppose that \(a = b\) or \(a = -b\text{.}\) First, suppose that \(a = b\text{.}\) Then \(a · 1 = b\text{,}\) so \(a|b\text{,}\) and \(b · 1 = a\text{,}\) so \(b|a\text{.}\) Similarly, suppose that \(a = -b\text{.}\) Then \(a · (-1) = b\text{,}\) so \(a|b\text{,}\) and \(b · (-1) = a\text{,}\) so \(b|a\text{.}\)
Theorem2.31.
Let \(m\) and \(n\) be integers. Then \(mn\) is odd if and only if both \(m\) and \(n\) are odd.
⇐. Suppose that \(m\) and \(n\) are both odd. Hence there is an integer \(j\) such that \(m = 2 j + 1\text{,}\) and there is an integer \(k\) such that \(n = 2k + 1\text{.}\) Therefore
Because \(k\) and \(j\) are integers, so is \(2 jk + j + k\text{.}\) Therefore \(mn\) is odd.
⇒. Suppose that \(m\) and \(n\) are not both odd. We will deduce that mn is not odd, and the desired result will follow by contrapositive. If \(m\) and \(n\) are not both odd, then at least one of them is even. Suppose first that \(m\) is even. Then there is an integer \(p\) such that \(m = 2p\text{.}\) Hence \(mn = (2p)n = 2(pn)\text{.}\) Because \(p\) and \(n\) are integers, so is \(pn\text{.}\) Therefore \(mn\) is even. Next assume that \(n\) is even. The proof in this case is similar to the previous case, and we omit the details.
SubsectionThe Following are Equivalent
A slightly more built-up version of an if and only if theorem is a theorem that states that three or more statements are all mutually equivalent. Such theorems often include the phrase “the following are equivalent,” sometimes abbreviated “TFAE.”
