Skip to main content

Section 4.1 Explanation and an Example

Another method of proof that is frequently used in mathematics is a proof by contradiction. This method is based on the fact that a statement \(X\) can only be true or false (and not both). The idea is to prove that the statement \(X\) is true by showing that it cannot be false. This is done by assuming that \(X\) is false and proving that this leads to a contradiction. (The contradiction often has the form \((R \wedge \neg R)\text{,}\) where \(R\) is some statement.) When this happens, we can conclude that the assumption that the statement \(X\) is false is incorrect and hence \(X\) cannot be false. Since it cannot be false, then \(X\) must be true.

A logical basis for the contradiction method of proof is the tautology

\begin{equation*} \left[ \neg X \to C \right] \to X\text{,} \end{equation*}

where \(X\) is a statement and \(C\) is a contradiction. The following truth table establishes this tautology.

\(X\) \(C\) \(\neg X\) \(\neg X \to C\) \(( \neg X \to C) \to X\)
T F F T T
F F T F T

This tautology shows that if \(\neg X\) leads to a contradiction, then \(X\) must be true. The previous truth table also shows that the statement \(\neg X \to C\) is logically equivalent to \(X\text{.}\) This means that if we have proved that \(\neg X\) leads to a contradiction, then we have proved statement \(X\text{.}\) So if we want to prove a statement \(X\) using a proof by contradiction, we assume that \(\neg X\) is true and show that this leads to a contradiction.

When we try to prove the conditional statement, ā€œIf \(\to\) then \(\to\)ā€ using a proof by contradiction, we must assume that \(P \to Q\) is false and show that this leads to a contradiction. Since we are assuming the conditional statement is false, we are, in effect, assuming its negation is true. According to TheoremĀ 1.1,

\begin{equation*} \neg (P \to Q) \equiv P \wedge \neg Q \end{equation*}

We will illustrate the process of a proof by contradiction with the following proposition.

Proof.

We will use a proof by contradiction. So we assume that the proposition is false, or that there exists a real number \(x\) such that \(0 \lt x \lt 1\) and

\begin{equation} \frac{1}{x (1 - x)} \geq 4\tag{1} \end{equation}

We note that since \(0 \lt x \lt 1\text{,}\) we can conclude that\(x \gt 0\) and that \(x(1 - x) \gt 0\text{.}\) Hence, \(x(1 - x) \gt 0\) and if we multiply both sides of inequality (1) by \(x(1 - x)\text{,}\) we obtain

\begin{equation*} 1 \lt 4x (1-x) \end{equation*}

We can now use algebra to rewrite the last inequality as follows:

\begin{align*} 1 \amp \lt 4x - 4x^2\\ 4x^2 -4x + 1 \amp \lt 0\\ (2x - 1)^2 \amp \lt 0 \end{align*}

However, \((2x - 1)\) is a real number and the last inequality says that a real number squared is less than zero. This is a contradiction since the square of any real number must be greater than or equal to zero. Hence, the proposition cannot be false and we have proved that for each real number \(x\text{,}\) if \(0 \lt x \lt 1\text{,}\) then \(\frac{1}{x (1 - x)} \geq 4\text{.}\)