# Proof by Contradiction

$\textbf{Introduction to Proof by Contradiction}$

The basic idea of $\textit{Proof by Contradiction}$ is to assume that the statement that we want to prove is $\textit{false}$, and then show this assumption leads to nonsense. We then conclude that it was wrong to assume the statement was $\textit{false}$, so the statement must be $\textit{true}$.

As an example of $\textit{Proof by Contradiction}$, consider the following proposition and its proof.

A $\textit{rational number}$ is a number which can be written in the form $\dfrac{p}{q}$, where $p$ and $q$ are integers, $q \ne 0$. It has been proven that a rational number has a decimal expansion which either terminates or recurs.

If we begin to write the decimal expansion of $\sqrt{2}$ , there is no indication that it will terminate or recur, and we might therefore suspect that $\sqrt{2}$ is irrational.
$$1.414\ 213\ 562\ 373\ 095\ 048\ 801\ 688\ 724\ 209\ 698\ 078\ 569\ 671\ 875\ 376\ 948\ 073 \cdots$$
However, we cannot $\textit{prove}$ that $\sqrt{2}$ is rational by writing out its decimal expansion, as we would have to write an infinite number of decimal places. We might therefore $\textit{believe}$ that $\sqrt{2}$ is irrational, but it may also seem impossible to $\textit{prove}$ it.

In fact, we can quite easily prove that $\sqrt{2}$ is rational by using a method called $\textit{Proof by Contradiction}$. In this method we suppose that the opposite is true of what we want to show is true, and follow a series of logical steps until we arrive at a contradiction. The contradiction confirms that our original supposition must be false.

It is ready to use contradiction to prove that $\sqrt{2}$ is irrational. The first line of the proof must be “Suppose that the statement is not true that $\sqrt{2}$ is irrational.

$\textit{Proof by Contradiction Example 1}$

$\textit{Proposition}$     The number $\sqrt{2}$ is irrational.

Suppose for the sake of contradiction that it is not true that $\sqrt{2}$ is irrational. Then $\sqrt{2}$ is rational, so $\sqrt{2} = \dfrac{p}{q}$ for some (positive) integers $p$ and $q$, $q \ne 0$.

We assume this fraction has been in lowest terms which means that this fraction is fully reduced, so $p$ and $q$ have no common factors.
\begin{align} \displaystyle 2 &= \dfrac{p^2}{q^2} &\ \textit{squaring both sides}\\ p^2 &= 2q^2 \cdots (1) \\ \end{align}
$p^2$ is even, and so $p$ must be even.
Thus $p = 2k$, for some $k \in \mathbb{Z}^{+}$
\begin{align} \displaystyle 4k^2 &= 2q^2 &\ &\ \textit{substituting into } (1)\\ q^2 &= 2k^2 \\ \end{align}
Thus $q^2$ is even, and so $q$ must be even.
Here we have a contradiction, so $p$ and $q$ have no common factors.
Therefore our original supposition is false, and $\sqrt{2}$ is irrational.

$\textit{Proof by Contradiction Example 2}$

$\textit{Proposition}$     The sum of two even numbers is always even.

Let’s $\textit{negate}$ this proposition.
The sum of two even numbers is $\textit{not}$ always even.

That means that there are two even numbers somewhere that will give us an odd number when they are added.
$2x+2y=z, \ \ x,y,z \in \mathbb{Z}^{+}$, where $z$ is an odd number.

Even and odd numbers are always positive integers, so we know $2x$ and $2y$ are positive integers, which means $x$ and $y$ are also positive integers. If these even numbers are divided by $2$, we get a positive integer. It is also known that $z$ is an odd number, which means it is not evenly divisible by $2$.
\begin{align} \displaystyle 2x+2y &= z \\ x+y &= \dfrac{z}{2} \\ \end{align}
$x+y$ is a positive integer, but $\dfrac{z}{2}$ is not a positive integer, because $z$ is assumed as an odd number.
The left hand side can’t possibly equal the fraction on the right. That’s a $\textit{contradiction}$!

Because the sum of two even numbers $2x$ and $2y$ should always be positive integers that are divisible by $2$, this contradicted the proposition. Therefore the original proposition is true: the sum of two even numbers is always even.