$\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 that 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.

Discover more enlightening videos by visiting our YouTube channel!

## Induction Made Simple: The Ultimate Guide

“Induction Made Simple: The Ultimate Guide” is your gateway to mastering the art of mathematical induction, demystifying a powerful tool in mathematics. This ultimate guide…

## Simplified Method for Calculating First Term and Common Ratio in Infinite Geometric Series

Hello, math enthusiasts! Today, we’re delving into the captivating realm of infinite geometric series and discovering how to easily determine the “First Term” and the…

## Induction Magic: Your Ticket to Inequality Triumph

Welcome to the world of mathematical induction, where we unravel the secrets of inequalities. Inequalities can be quite intimidating, but fear not! We have a…

## Domain and Range: Top Tips for Quick Learning

Understanding Domain and Range: A Comprehensive Guide Domain and range are fundamental mathematical concepts that help us understand the behaviour and characteristics of relations and…

## Index Notation

A convenient way to write a product of $\textit{identical factors}$ is to use $\textbf{exponential}$ or $\textbf{index notation}$.Rather than writing \$5 \times 5 \times 5 \times…

#### Responses

1. Great explanation!
Just one little thing though, I would recommend mentioning that for the statement in the first example that, p^2 or q^2 being even means that p and q is even, only works when the number (p or q) is an integer.

1. Great comment! We will make sure to consider your valuable points in future video lessons.