Proof By Contradiction

Proof by contradiction is another logical technique we can use to prove a statement is true. The process for a proof by contradiction is to:

Assume that the negation of the statement is true (that is, that the original statement is false)
Use definitions, algebraic manipulations, or logical deductions to produce a statement that contradicts this assumed negation, or some other statment known to be true
Reject the negation as false, and therefore conclude that the original statement is true

An example of a time where we can proof by contradiction is to demonstrate the following proposition

The number $\sqrt2$ is irrational.

To prove this, we recall the definition a rational number

A rational number is a number that can be written as $\frac{p}{q}$ where $p, q \in \Z$

To prove the irrationality of $\sqrt2$ , we will first assume the negation of this proposition is true. This means we will assume that $\sqrt2$ is rational, and that there exist two integers $m$ and $n$ such that

$\sqrt2 = \frac{m}{n}$

If $\sqrt2$ is indeed rational, then there must be some pair of $m$ and $n$ that have no common factors. Suppose these numbers did have a common factor $f$ , we could rewrite the fraction as

$\frac{m}{n} = \frac{\frac{m}{f}}{\frac{n}{f}}$

Since $f$ is a factor of both $m$ and $n$ , $\frac{m}{f}$ and $\frac{n}{f}$ are both integers so this is also a valid rational representation of $\sqrt2$ , and these two numbers have no common factors.

From this, we could then write

\begin{aligned} \sqrt2 &= \frac{m}{n} \\ 2 &= \frac{m^2}{n^2} \\ 2n^2 &= m^2 \\ \end{aligned}

Since $n \in \Z$ , then $n^2 \in \Z$ and so this means that $m^2$ meets the definition of an even number. We earlier proved the statement

If, and only if, $n$ is odd, then $n^2$ is odd.

The contrapositive of this statement, which is also true, is

If, and only if, $n^2$ is even, then $n$ is even.

This means that $m$ is also even and so $m = 2x$ for some $x \in \Z$ , and therefore $m^2 = 4x^2$ . This means that we can write

\begin{aligned} 2n^2 &= m^2 \\ 2n^2 &= 4x^2 \\ n^2 &= 2x^2 \\ \end{aligned}

By the same reasoning, we see that $n^2$ is even, and therefore $n$ is even and can be written as $n = 2y$ for some $y \in \Z$ . We have now shown that

\begin{aligned} m &= 2x, \quad x \in \Z \\ n &= 2y, \quad y \in \Z \\ \end{aligned}

This means that $m$ and $n$ must have a common factor of $2$ , which means that there is no pair of integers $m$ and $n$ such that $\sqrt2 = \frac{m}{n}$ with no common factors. This is a direct contradiction of our previous reasoning that such a pair must exist.

Therefore we must reject the assumption that $\sqrt2$ is rational and we have proven that this number is indeed irrational and cannot be written as a fraction of two integers. QED

To summarise our approach:

We assumed that $\sqrt2$ is rational
By the definition of a rational number, we assume that $\sqrt2 = \frac{m}{n}$
We show that there must be some $m$ and $n$ such that they have no common factors
Assume the premise is true, we show that any $m$ $m$ and $n$ $n$ must both be even
- To prove this, we use our previous result that $n^2$ is odd if and only if $n$ is odd.
We conclude that this statement contradicts our previous reasoning that some $m$ and $n$ must exist with no common factors
We reject the premise that $sqrt2$ is rational and conclude that it is irrational

We also saw something interesting in this proof, where we needed to refer back to the result of our previous proof about the squares of even and odd numbers in order to complete our proof. This is a common occurrence and highlights how we can start off from very fundamental assumptions and definitions and over time build up a more complicated, but sophisticated, understanding of the nuances that follow.

...