Section 4.3 Biconditional proofs
We saw in the last chapter that the biconditional statement \(p \leftrightarrow q\) is equivalent to the statement \((p \to q) \wedge (q \to p)\text{.}\) In other words, if we can prove both “if \(p\) then \(q\)” and “if \(q\) then \(p\)” then we have proven “\(p\) if and only if \(q\text{.}\)”
We have accidentally done one example:
Theorem 4.3.1.
An integer is even if and only if its square is.
We can name the integer \(n\text{.}\) Since we have proven both the statements “If \(n\) is even then \(n^2\) is even” and “If \(n^2\) is even then \(n\) is even,” we have proven the biconditional statement as well.
Let's see a couple of fully worked examples, rather than taking the lazy way out and combining examples from previous sections.
Example 4.3.2.
Prove that \(7n^2 - 4n + 1\) is even if and only if \(n\) is odd.
To do so, prove both the statements “If \(n\) is odd then \(7n^2 - 4n + 1\) is even” and “If \(7n^2 - 4n + 1\) is even then \(n\) is odd.” The latter of the two should be proven via contraposition. As usual, try it yourself before reading the proof below.
Proof.
Suppose that \(n\) is an integer.
Let \(n\) be odd. Then \(n=2m+1\) for some integer \(m\text{.}\) Therefore,
which is even. Thus if \(n\) is odd, then \(7n^2 - 4n + 1\) is even.
Conversely, let \(7n^2 - 4n + 1\) be even. We will show that \(n\) must be odd by showing that if \(n\) is even then \(7n^2 - 4n + 1\) is odd. Let \(n\) be even, meaning that there is an integer \(m\) where \(n=2m\text{.}\)
We have shown that \(7n^2-4n+1\) is odd when \(n\) is even. Therefore for \(7n^2-4n+1\) to be even, \(n\) must be odd.
In conclusion, if \(n\) is an integer, then \(7n^2 - 4n + 1\) is odd if and only if \(n\) is even.
We used \(m\) to represent two different integers in this proof. However, that is okay, because the second time it was used was after “discharging” it from its prior use. If you use the same symbol for two objects at the same time, then your proof will be impossible to understand.
Example 4.3.3.
Prove that a product of integers is odd if and only if both are odd.
First, name the integers. Maybe you'll choose \(m\) and \(n\text{,}\) or \(x\) and \(y\text{.}\) (Remember you can't re-use names you're currently using!) Then prove two statements: “If both integers are odd then their product is” and “If the product of two integers is odd then both integers must be odd.”
Notice the subtle appearance of DeMorgan's law in the proof below.
Proof.
Put \(x, y \in \mathbb{Z}\text{.}\)
First, suppose that \(x\) and \(y\) are both odd. In that case, there exist integers \(k\) and \(m\) such that \(x=2k+1\) and \(y=2m+1\text{.}\) So,
which is odd by definition. Therefore if \(x\) and \(y\) are both odd then their product is odd.
Conversely we would like to show that if a product of integers is odd then both integers are odd. Equivalently, we will prove that if it is untrue that both integers are odd, then the product is even.
Assume not both \(x\) and \(y\) are odd. Then one is even. Without loss of generality, we can assume \(x\) is even (if not just change the labels). Then \(x=2k\) for some integer \(k\text{.}\) Therefore,
As claimed, if not both of the integers are odd, then their product is even. So, the only way for the product to be odd is if both integers are odd.
Therefore, the product of two integers is odd if and only if both integers are odd.
Did you see it? The negation of “both integers are odd” is “one integer is even”. Also notice the use of the phrase “without loss of generality”—sometimes abbreviated “WOLOG”. It means that we may make an assumption without losing the generality of our proof, because the assumption is just one of labeling.