Proof by contradiction (also known as indirect proof or the method of reductio ad absurdum) is a technique which can be used to prove any kind of statement. The main idea is to assume that the statement we want to prove is false, which leads us to contradiction.
More precisely, if we want to prove that statement P is true, we assume that P is false. Then P being false implies something that cannot be true. Therefore, we can conclude that P is true.
Examples (statement P)
To illustrate the above, we will show a simple example.
Example 1: Prove that the harmonic series $\sum \frac{1}{n}$ diverges.
Solution:
Suppose that the harmonic series converges. In other words, let
$$S = 1 + \frac{1}{2} + \frac{1}{3} + \cdots$$
If we divide this expression by $2$, we get
$$\frac{S}{2} = \frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \cdots$$
Obviously,
$$1 + \frac{1}{3} + \frac{1}{5} + \cdots > \frac{S}{2}.$$
Also, by adding $\frac{S}{2}$
$$S > \frac{S}{2} + \frac{S}{2} = S \rightarrow S > S.$$
Therefore, we have reached a contradiction so our assumption must be wrong. In other words, the harmonic series $\sum \frac{1}{n}$ diverges.
Example 2: Prove that $\sqrt{2}$ is an irrational number.
Solution:
Suppose $\sqrt{2}$ is rational. This means that $\sqrt{2} = \frac{m}{n}$, where $m$ and $n$ are some integers. Without loss of generality we can assume that $m$ and $n$ have no factors in common.
Squaring gives us:
$$2 = \frac{m^2}{n^2}.$$
Therefore, $m^{2} = 2n^{2}$. Obviously, $m^{2}$ is even, which means that $m$ is even to (try to prove this!). In other words, $m = 2k$ for some $k \in \mathbf{Z}$. Then
$$2n^2 = m^{2} = (2k)^{2} = 4k^2.$$
When we divide that by $2$, we get
$$n^{2} = 2k^{2},$$
so $n^{2}$ is even. This means that $n = 2l, l \in \mathbf{Z}$.
Therefore, we have seen that if $\sqrt{2}= \frac{m}{n}$, then both $m$ and $n$ must be even. In other words, $m$ and $n$ are multiples of $2$. This is a contradiction to the fact that $m$ and $n$ are chosen to have no factors in common. In conclusion, $\sqrt{2}$ is an irrational number.
Examples (statements $P \rightarrow Q$)
Often, statements we want to prove have the form: $P \rightarrow Q$. In those situations we assume that $P \land \neg Q$ is true, which in some point leads us to a contradiction.
For the following example, you will need a knowledge of the lesson Relations.
Example 3: Let $A$ and $B$ be a non – empty sets and $R \subseteq A \times B$.
Prove the following statement:
$R$ is injective if and only if $R^{-1} \circ R \subseteq I_{A}$.
Solution:
We need to prove two directions: neccessity and sufficiency.
First we will prove neccessity. In other words, we want to prove that if $R$ is injective, then $R^{-1} \circ R \subseteq I_{A}$.
Let’s assume that $R$ is injective and that $R^{-1} \circ R \not \subseteq I_{A}$. This means that
$$(\exists x \in A) (\exists x’ \in A) (x \neq x’ \land (x, x’) \in R^{-1} \circ R).$$
Therefore, $R^{-1} \circ R \neq \emptyset$. By definition of composition of relations we have:
$$(\exists x \in A) (\exists x’ \in A) (\exists y \in B) (x \neq x’ \land (x, y) \in R\land (y, x’) \in R^{-1}).$$
Furthermore, by using the definition of an inverse relation, we have
$$(\exists x \in A) (\exists x’ \in A) (\exists y \in B) (x \neq x’ \land (x, y) \in R\land (x’, y) \in R),$$
from which we conclude that $R$ is not injective. In other words, we have reached a contradiction so our assumption must be wrong. In conclusion, $R^{-1} \circ R \subseteq I_{A}$.
Next, we will proof sufficiency. More precisely, we want to prove that if $R^{-1} \circ R \subseteq I_{A}$ is valid, then $R$ is injective.
Let’s assume that $R^{-1} \circ R \subseteq I_{A}$ and that $R$ is not injective. In other words, we simply negate the definition of injective relation and get
$$(\exists x \in A) (\exists x’ \in A) (\exists y \in B) (x \neq x’ \land (x, y) \in R \land (x’, y) \in R).$$
Furthermore, by definition of inverse relation we have
$$(\exists x \in A) (\exists x’ \in A) (\exists y \in B) (x \neq x’ \land (x, y) \in R \land (y, x’) \in R^{-1}).$$
Therefore,
$$(\exists x \in A) (\exists x’ \in A) (x \neq x’ \land (x, x’) \in R^{-1} \circ R),$$
so $R^{-1}\circ R \not \subseteq I_{A},$ which is a contradiction.
In conclusion, $R$ must be injective.
