Proof by Contraposition

The structure of proof by contraposition

We can consider this an indirect method. We know the following logical equivalence:

$$\left(P\Rightarrow Q\right)\Leftrightarrow \left(\neg Q \Rightarrow \neg P\right) .$$

Starting the proof with $P$ and trying to conclude $Q$ is sometimes harder than starting with $\neg Q$ and concluding $\neg P$. If we want to prove the following statement $s$:

$$s=\forall x \left(P(x)\Rightarrow Q(x)\right).$$

We instead prove the following logically equivalent statement $t$:

$$t=\forall x \left(\neg Q(x)\Rightarrow \neg P(x)\right).$$

As we know that both $s$ and $t$ are logically equivalent, showing that $t$ is true. This means $s$ is also true and vice versa. Let’s look at a few examples to explore this method further.

Examples

Let’s assume $x$ and $y$ are two real numbers. We will prove the following theorem:

Theorem 1

For any real numbers $x$ and $y$, if $x+y \ge 2$ then $x\ge 1 \lor y\ge 1$.

Proof

We have to show that $\left((x+y)\ge 2\right) \Rightarrow \left( x\ge 1 \lor y\ge 1 \right)$, which is $P\Rightarrow Q$, where, $P:= \left((x+y)\ge 2\right)$, and $Q:=\left( x\ge 1 \lor y\ge 1 \right)$. We instead prove that $\neg Q \Rightarrow \neg P$. We start with $\neg Q$, which is the hypothesis. We use DeMorgan’s law to achieve the following equivalence:

\neg Q \equiv \left( x<1 \land y<1 \right).

As, x<1, and y<1, we can add both the inequalities to conclude \left(x+y\right)<2. That is exactly $\neg P$. Therefore, $\neg Q \Rightarrow \neg P$ is true. We have the following tautology:

$$\left(\neg Q \Rightarrow \neg P\right)\Leftrightarrow (P\Rightarrow Q).$$

Therefore, $P\Rightarrow Q$ is true.

Theorem 2

For any real numbers x>0 and y>0, if $m=xy$, then $\left(|\sqrt{m}|\ge x \lor |\sqrt{m}|\ge y\right)$.

Proof

We are given that both $x$ and $y$ are positive. We have to show that $P\Rightarrow Q$ is true, where, $P:= \left(m=xy\right)$, and $Q:=\left(|\sqrt{m}|\ge x \lor |\sqrt{m}|\ge y\right)$. Because, $(P\Rightarrow Q)\Leftrightarrow \left(\neg Q \Rightarrow \neg P\right)$ is a tautology, we will instead show that $\left(\neg Q \Rightarrow \neg P\right)$ is true. We use DeMorgan’s law to achieve the following equivalence:

\neg Q \equiv \left(|\sqrt{m}| < x \land |\sqrt{m}| < y\right).

As we have, \left(|\sqrt{m}| < x\right), we can multiply it by $|\sqrt{m}|$. Therefore, we get \left(m < x|\sqrt{m}|\right). Similarly, we have \left(|\sqrt{m}| < y\right) and we get \left(x|\sqrt{m}| < xy\right), because x>0. We can use the transitive property of inequalities to get $m