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 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.

Algebra Algebraic Fractions Arc Binomial Expansion Capacity Chain Rule Common Difference Common Ratio Differentiation Double-Angle Formula Equation Exponent Exponential Function Factorise Functions Geometric Sequence Geometric Series Index Laws Inequality Integration Kinematics Length Conversion Logarithm Logarithmic Functions Mass Conversion Measurement Perfect Square Perimeter Prime Factorisation Probability Product Rule Proof Pythagoras Theorem Quadratic Quadratic Factorise Ratio Rational Functions Sequence Sketching Graphs Surds Time Transformation Trigonometric Functions Trigonometric Properties Volume

Help

• Issue: *
  Wrong AnswerTypoUnclear QuestionBroken LinksWrong ImageInvalid ContentSuggestionsFeedbackSomething Else
• Your Name: *
  
• Your Email: *
  

• Details: *
  

Send for Help