Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 5.1 Contrapositive

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 scratch work. 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.
It’s time to return to Example 5.0.1 and try out a contrapositive proof.

Example 5.1.1. Example 5.0.1 redux.

Let \(n\) be an integer. Prove that if \(3n+7\) is even, then \(n\) is odd.
Scratchwork.
First up, lets write out some scratch work / explorations.
  • We got stuck when we tried a direct proof, so write down the contrapositive:
    \begin{equation*} (n \text{ is even}) \implies (3n+7 \text{ is odd}) \end{equation*}
    This looks easier.
  • Assume \(n\) is even.
    \begin{align*} n \amp =2k\\ 3n+7 \amp = 6k+7 = 2(3k+3)+1 \end{align*}
  • Since \(3k+3 \in \mathbb{Z}\) we are done.
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!
Solution.
We prove the contrapositive. Assume that \(n\) is even and hence \(n=2k\) for some integer \(k\text{.}\) This means that we can write
\begin{equation*} 3n+7=6k+7=2(3k+3)+1. \end{equation*}
Since \(3k+3\in\mathbb{Z}\text{,}\) it follows that \(3n+7\) is odd as required.

Remark 5.1.2. Warn your 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
  • “We prove the contrapositive…”,
  • “Consider the contrapositive…”,
  • or even (if, say you are writing a test and running out of time)“Do contrapositive…”
A few words from you can save the reader a lot of confusion “Why are they assuming the conclusion is false?”, “What is going on here?”, etc.
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.

Example 5.1.3. Example 5.0.1 redux redux.

Let \(n\) be an integer. If \(3n+7\) is even, then \(n\) is odd.
Solution.
Assume that \(3n+7\) is even. Hence \(3n+7 = 2\ell\text{,}\) where \(\ell\) is some integer. Now we can write
\begin{align*} n &= (3n+7) - (2n+7)\\ &= 2\ell-2n - 7\\ &= 2(\ell-n-4)+1 \end{align*}
Since \(\ell-n+4 \in \mathbb{Z}\) it follows that \(n\) is odd.
Another similar example…

Example 5.1.4.

Let \(n\in\mathbb{Z}\text{.}\) If \(n^2+4n+5\) is odd, then \(n\) is even.
Scratchwork.
The first thing we should do as part of our scratch work 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 scratch work 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*}
This is now straight-forward for us.
Solution.
Let \(n \in \mathbb{Z}\) and assume \(n\) is odd. Then \(n = 2k+1\) for some integer \(k\text{.}\) Hence
\begin{align*} n^2+4n+5 \amp = (2k+1)^2+4(2k+1)+5 \\ \amp = 4k^2+4k+1 + 8k + 4 + 5 \\ \amp = 4k^2+12k+10 = 2(2k^2+6k+5) \end{align*}
Since \(2k^2+6k+5\) is an integer, we know that \(n^2+4n+5\) is even as required.
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.
We will prove the contrapositive, so let \(n \in \mathbb{Z}\) and assume \(n\) is odd. Then \(n = 2k+1\) for some integer \(k\text{.}\) Hence
\begin{align*} n^2+4n+5 \amp = 4k^2+12k+10 = 2(2k^2+6k+5) \end{align*}
and since \(2k^2+6k+5\) is an integer, we know that \(n^2+4n+5\) is even.
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
\begin{equation*} P \iff Q \equiv (P\implies Q) \land (Q \implies P) \end{equation*}
But how do we prove the conjunction of two implications?
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
  • If \(n^2\) is odd then \(n\) is odd.
  • If \(n\) is odd then \(n^2\) is odd.
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 (ie 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.
Parity proofs can get a little dull, so lets prove something a little different. Again, we’ll call it a lemma because it might be useful later on.
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
If \(a \mid b\) and \(b\mid a\) then \(a=\pm b\text{.}\)
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.
  • 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
    \begin{gather*} k \ell = 1 \end{gather*}
  • 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.
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.
<Prev^TopNext>