As we have just seen, when we are presented with an implication to prove we should take a moment to think about the contrapositive of that implication — it might be easier! However, it do that we need to be able to contrapose a statement quickly. But that, in turn, requires us to negate statements fluently. Practice is crucial.
Once you have this fluency it only takes a moment to write down the contrapositive when you start your scratchwork. Then you can assess what looks easier: the original or the contrapositive. If the contrapositive looks easier to prove, then we should proceed down that path. On the other hand, when it looks harder stick with the original.
Now that we’ve worked out how to make the proof work, we can write it up nicely. Since we are not using a direct proof we should alert the reader that we are going to prove the contrapositive. Otherwise it can look a little strange — I’m not going to assume the hypothesis is true, instead I’m going to assume the conclusion is false. Think about the reader!
As noted in the example above, when you prove the contrapositive of the result you should warn the reader of what you are going to do. You don’t need to write much
Of course, there can be more than one way to prove things. Here is another proof of the same result, this one using a direct proof. Is uses a cute little trick that is worth remembering.
The first thing we should do as part of our scratchwork is to write down the contrapositive:
\begin{equation*}
(n \text{ is not even}) \implies (n^2+4n+5 \text{ is not odd})
\end{equation*}
We’ve been a little sloppy here — we didn’t write down the “Let \(n \in \mathbb{Z}\)”, but it is scratchwork not the actually proof. It is okay to be a little bit sloppy. The integerness of \(n\) means that we can simplify this further to
\begin{equation*}
(n \text{ is odd}) \implies (n^2+4n+5 \text{ is even})
\end{equation*}
The above proof can be improved. First up, we forgot to warn the reader “we are going to prove the contrapositive”. Second, the reader doesn’t need to see those boring algebraic manipulations; we can reasonably assume that the reader can do some basic algebra. So with those things in mind, here is a better proof.
Let us now prove a simple (but useful) biconditional result. We’ll call it a result rather than an example, because we’ll need to refer back it later. We could even call it a lemma — in fact, let’s do that.
We’ve not proved a biconditional before, so where do we start. Our starting point is to rewrite the biconditional as implications because we know what we have to do to prove those. Recall from Theorem 4.2.3 that
Go back to first principles — we want to show that the statement cannot be false. This means that we must show that both implications are true. Hence we have to show that both
are true and then it follows that the conjunction is true, and so our original biconditional statement is true. Hence our proof consists of two parts (i.e. sub-proofs).
Of course, we have to tell the reader what we are doing. Statements like “We prove each implication in turn” or “We first prove one direction and then the other” are good ways to warn the reader what structure to expect. Then you can make this structure very easy to read by using dot-points or other formatting tricks.
We must show both that if \(n\) is odd then \(n^2\) is odd, and if \(n^2\) is odd then \(n\) is odd.
Assume \(n\) is odd and so \(x = 2k+1\) for some \(k \in \mathbb{Z}\text{.}\) Then \(x^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1\text{.}\) Since \(2k^2+2k\) is an integer, it follows that \(x^2\) is odd.
To prove that if \(x^2\) is odd then \(x\) is odd we will show the contrapositive. Assume \(x\) is even and so \(x=2k\text{.}\) Then \(x^2 = 4k^2 = 2(2k^2)\text{.}\) Since \(2k^2\) is an integer, it follows that \(x^2\) is even.
So this is pretty much just what we did for the other proofs, we just had to do it twice. First we proved \(\implies\) and then we proved \(\Leftarrow\text{.}\) And we told the reader what we were doing; we didn’t leave them to guess.
Because this result is about divisibility now is a good time to review Definition 3.2.4. Unfortunately that definition tells us what it means for an integer to be divisible by another, but not what is means when one integer is not divisible. However, we can turn that around using the contrapositive. The result then becomes
This looks a lot easier. When we assume the hypothesis to be true we can use the definition of divisibility quite directly. This is a good sign that the contrapositive was the right thing to do.
Of course we can also write this out in proper sentences and not point form. Actually, because we wrote things nicely above, we really just need to remove the dots:
Assume \(a\mid b\) and \(b\mid a\text{.}\) Hence there are integers \(k,\ell\) so that \(b=ka\) and \(a=\ell b\text{.}\) Thus we can write \(b=ka=k\ell b\text{.}\) Since \(b\neq 0\) we can divide both sides by \(b\) to get \(k\ell = 1\text{.}\) Now since \(k,\ell \in \mathbb{Z}\) it follows that the only solutions to this are \(k,l \in \set{1,-1}\text{.}\) This gives \(b=\pm a\) as required.
