Proof by Contradiction

The structure of proof by contradiction

We use this method to prove that a given statement $s$ is true. As $s$ is a proposition, it is either true or false. We start the proof by assuming that $s$ is false and use this assumption and other hypotheses to conclude a contradiction. Therefore, $s$ can not be false, which means $s$ is true. We can also interpret this proof method as follows:

$$\neg s \Rightarrow F.$$

As the contrapositive of an implication is logically equivalent, we conclude the following:

$$T\Rightarrow s.$$

The above implication can only be true if $s$ is true.

Another way to look at proof by contradiction is as follows. Assume we want to prove that $P\Rightarrow Q$ is true. We know that $P\Rightarrow Q \equiv \left( \neg P \lor Q\right)$. Further, due to DeMorgan’s law, we can write the following equivalence:

$$\begin{aligned}{} P\Rightarrow Q &\equiv \left( \neg P \lor Q\right)\\ &\equiv \neg \left( P \land \neg Q\right).\\ &\equiv\neg \left( P \land \neg Q\right)\lor F.\\ &\equiv \left( P \land \neg Q\right)\Rightarrow F. \end{aligned}$$

Therefore, if we can show that $\left( P \land \neg Q\right)$ leads to a contradiction, we have shown that $P\Rightarrow Q$ is true.

To comprehend it further, let’s prove a few example statements using this method.

Examples

We define a rational number in the form $\frac{p}{q}$, where $p$ and $q$ are integers and $q\ne 0$. Further, a rational number is in standard form if $p$ and $q$ do not have a common factor greater than one.

Lemma 1

For an integer $n$, if $n^2$ is even, then $n$ is also even.

Proof

We prove this statement using the method of contraposition. We want to prove the following statement:

$$n^2\space\text{is even} \Rightarrow n\space \text{is even}.$$

Instead, we’ll prove the contrapositive of this statement, which is logically equivalent to the above statement. The contrapositive of the above statement is as follows:

$$n\space\text{is odd} \Rightarrow n^2\space\text{is odd}.$$

Assuming that $n$ is odd, we can write $n$ as follows:

$$n = 2k+1~~\text{for some integer}\space k.$$

Taking the square on both sides, we get the following equation:

$$n^2 = \left(2k+1\right)^2.$$

We open up the square on the right side and rearrange the terms.

$$n^2 = 4k^2+4k+1.$$

$$n^2 = 2\left(2k^2+2k\right)+1.$$

As $k$ is an integer, $\left(2k^2+2k\right)$ is also an integer. Let $j=\left(2k^2+2k\right)$. Now, we can write the following equation:

$$n^2 = 2j+1.$$

Therefore, $n^2$ is odd.

Theorem 1

$\sqrt{2}$ is an irrational number.

Proof

We want to prove the following statement:

$$s=\sqrt{2}\space \text{is irrational}.$$

A number is either rational or irrational. We assume that the given statement is false. This means $\neg s$ is true.

$$\neg s = \sqrt{2}\space \text{is a rational number}.$$

In that case, we can write it in the standard form as $\sqrt{2} = \frac{p}{q}$, where $q\ne0$ and there is no common factor of $p$ and $q$. If we square both sides, we get the following equation:

$$\left(\sqrt{2}\right)^2 = \frac{p^2}{q^2}.$$

We can rearrange the terms as follows:

$$2q^2 = p^2.$$

As $p$ and $q$ are integers, we see that $p^2$ is even.

If $p^2$ is even, then $p$ is even by lemma 1. Therefore, we can write $p=2k$ for some integer $k$. We get the following equation:

$$2q^2 = \left(2k\right)^2.$$

Simplifying the above equation gives us the following equation:

$$q^2 = 2k^2.$$

This means $q^2$ is an even number. By lemma 1, if $q^2$ is an even number, then $q$ is an even number.

This means $p$ and $q$ both are even numbers. But that is a contradiction because we assumed that $p$ and $q$ do not have a common factor greater than one. As $\neg s$ leads us to a contradiction, it can not be true. Therefore, $s$ is true.

Theorem 2

There are infinitely many prime numbers.

Proof

Assume that there are finitely many prime numbers. Then we can write them in ascending order as $p_1, p_2, p_3, \ldots, p_n$, where $p_n$ is the largest prime number. We can construct a number $p$ as follows:

$$p= p_1\times p_2 \times p_3 \times \ldots \times p_n+1.$$

Note that $p_i$ cannot be a factor of $p$ because it is a factor of $\left(p-1\right)$, and the smallest prime is two. Now, there are two possibilities. The first possibility is that $p$ is a prime that is greater than $p_n$, which is a contradiction because we assumed that $p_n$ is the biggest prime. The second possibility is that $p$ is a composite number, but there is no prime number that divides it, which is a contradiction to the fact that every composite number has a prime factor.

Therefore, there are infinitely many prime numbers.