4.4 Proving the contrapositive

The statements ‘$P\Rightarrow Q$’ and ‘not $Q\Rightarrow$ not $P$’ are equivalent. To see why, let’s think about the Euler diagrams representing these two statements.

Recall the Euler diagram for the statement ‘$P\Rightarrow Q$’ from Section 3.2.4.

The arrangement of $P$ and $Q$ in the diagram ensures that a dot placed inside $P$ (representing $P$ being true) must also be inside $Q$ (meaning that $Q$ must also be true). But this relationship can be equally well described by saying that if a dot is outside $Q$ then it must be outside $P$. If we draw the Euler diagram for this, then the shape for $P$ must be inside the shape for $Q$, giving the same Euler diagram as above.

So proving the statement ‘not $Q\Rightarrow$ not $P$’ is equivalent to proving ‘$P\Rightarrow Q$’. We call ’not $Q$ $\Rightarrow$ not $P$’ the contrapositive of ’$P\Rightarrow Q$’.

This idea may seem counter-intuitive at first but it helps to think about a real-life example. In some legal jurisdictions, there is a road safety law that states: ‘if your vehicle’s wipers are on, then its lights must be on’. The contrapositive of this statement is ‘if your vehicle’s lights are not on, then its wipers are not on’. Think about this and convince yourself that these are indeed equivalent ways of stating the same thing.

As demonstrated by the following exercises, it can sometimes be easier to prove the contrapositive rather than the original statement.

• ​

  Solution.The contrapositive is: if $a$ is not odd then $a^{2}$ is not odd. In other words, if $a$ is even then $a^{2}$ is even.

  We can now prove this directly. Suppose $a$ is even, and so we can write $a=2k$ for some integer $k$. Then

  $$a^{2}=(2k)^{2}=4k^{2}=2(2k^{2}).$$

  As $k$ is an integer, so is $(2k^{2})$ and so $a^{2}$ has the form of an even integer.

• ​

  Solution.The contrapositive is: if $a$ is odd then $a^{2}$ is odd.

  We now prove this directly. Suppose $a$ is odd, and so we can write $a=2k+1$ for some integer $k$. Then

  $$a^{2}=(2k+1)^{2}=4k^{2}+4k+1=2(2k^{2}+2k)+1.$$

  As $k$ is an integer, so is $(2k^{2}+2k)$ and so $a^{2}$ has the form of an odd integer.

• ​

  Solution.The contrapositive is: if $z>0$, then $xz>yz$.

  We now prove this directly. Suppose $x>y$ and $z>0$. Multiplying both sides of an inequality by a positive number does not reverse the direction of the inequality, and so $xz>yz$.