UK A-Level: Proof by Contradiction

Proof by contradiction is one of mathematics' most elegant and powerful weapons, allowing you to establish the absolute truth of a statement by showing that its falsehood leads to logical chaos. Mastering this technique, also known as reductio ad absurdum, is crucial for A-Level mathematics and beyond, as it unlocks proofs of some of the most fundamental theorems, from the irrationality of numbers to the infinite nature of prime numbers. It trains you to think like a mathematician, constructing airtight logical arguments from a single, clever assumption.

The Logical Structure of an Indirect Proof

At its heart, a proof by contradiction follows a strict logical recipe. You begin with a statement you wish to prove is true, let's call it $P$. Instead of proving $P$ directly, you assume its opposite—that $P$ is false. This assumption, $\neg P$, is your starting point. You then proceed with a chain of logical, mathematically correct deductions from this assumption. The goal is to arrive at a contradiction. This contradiction can take one of two classic forms: it can contradict an established fact (like $1=0$ or "all primes are odd"), or it can contradict the initial assumption $\neg P$ itself.

Why does this work? In logic, if an assumption leads to an impossibility, then the assumption itself must be false. Since we assumed $\neg P$ was true and it led to nonsense, $\neg P$ must be false. Consequently, the original statement $P$ must be true. Think of it like a detective ruling out all other suspects—if assuming someone else committed the crime leads to an impossible timeline, then the original suspect must be guilty. The formal structure is:

1. Assume $\neg P$ (the negation of what you want to prove).
2. Show through valid deduction that $\neg P⟹Q$, where $Q$ is a false statement or a contradiction.
3. Conclude that $\neg P$ must be false, and therefore $P$ is true.

A Classic Example: The Irrationality of $\sqrt{2}$

This is the quintessential introduction to proof by contradiction. We want to prove the statement $P$: "$\sqrt{2}$ is irrational." An irrational number is one that cannot be expressed as a fraction $\frac{a}{b}$, where $a$ and $b$ are integers with no common factors (i.e., a fraction in its simplest form).

We start by assuming the negation, $\neg P$: "$\sqrt{2}$ is rational." If it is rational, we can write it as a fraction in lowest terms: $$\sqrt{2}=\frac{a}{b}$$ where $a$ and $b$ are integers, $b\ne 0$, and the fraction is simplified so that $a$ and $b$ have a highest common factor of 1 (they are coprime).

Now, we perform algebraic manipulations on this assumption:

1. Square both sides: $2=\frac{a^2}{b^2}$.
2. Rearrange: $2b^2=a^2$.

This tells us that $a^2$ is an even number (because it is equal to $2\times$ something). A key property is: if $a^2$ is even, then $a$ itself must be even. Therefore, we can write $a=2k$ for some integer $k$.

1. Substitute back: $2b^2=(2k{)}^2=4k^2$.
2. Simplify: $b^2=2k^2$.

Now we see that $b^2$ is also even, which means $b$ must be even. Here lies the contradiction. We have deduced that both $a$ and $b$ are even. But wait—our initial assumption stated that $\frac{a}{b}$ was in its simplest form, meaning $a$ and $b$ should have no common factors. Yet, if both are even, they share a factor of 2. This is a direct contradiction to the condition of being in lowest terms. Therefore, our initial assumption that $\sqrt{2}$ is rational must be false. Hence, $\sqrt{2}$ is irrational.

Another Pillar: The Infinitude of Primes

Euclid's proof that there are infinitely many prime numbers is a masterpiece of concise logic. We want to prove $P$: "There are infinitely many prime numbers."

Assume the negation, $\neg P$: "There are finitely many prime numbers." If the set is finite, we can list them all: $p_1,p_2,p_3,...,p_n$.

Now, consider a new number constructed from this list: $$N=(p_1\times p_2\times p_3\times ...\times p_n)+1$$ This number $N$ is either prime or composite. Examine both cases:

• If $N$ is prime, we have an immediate problem: $N$ is larger than and different from every prime in our supposedly complete list. This is a contradiction, as we found a new prime.
• If $N$ is composite, it must be divisible by some prime number (by the Fundamental Theorem of Arithmetic). According to our assumption, the only primes that exist are on our list $p_1,p_2,...,p_n$. But if we try to divide $N$ by any prime $p_i$ on the list, we get a remainder of 1, because $N=(\text{product of all primes})+1$. Therefore, none of the primes on our list divides $N$. This means the prime factor of $N$ is not on our list—another contradiction.

In both possible outcomes of analyzing $N$, we reach a contradiction with the assumption of a finite list. Therefore, the assumption is false, and the number of primes must be infinite.

When is Proof by Contradiction the Most Effective Approach?

Choosing the right proof technique is a skill. Proof by contradiction shines in specific scenarios:

• Proving Non-Existence or "Cannot Be" Statements: It's very natural. How do you prove something doesn't exist or can't happen? Assume it does exist or can happen, and show that leads to nonsense. The irrationality proof is a perfect example: proving $\sqrt{2}$ cannot be written as a fraction.
• Proving Uniqueness: To prove "There is only one X with property Y," you can assume there are two distinct ones with property Y and derive a contradiction.
• When the Negation Gives You Something Concrete to Work With: In the infinitude of primes proof, assuming finiteness gave us a concrete, listable set of primes to manipulate. This new, tangible object (the list) is often easier to work with than the abstract concept of "infinity."
• For "Either/Or" Statements: If you need to prove that at least one of two conditions must be true, assume that neither is true (the negation of an "or" statement is an "and" statement) and find a contradiction.

A good rule of thumb: if a direct proof seems elusive or messy, and the negation of the statement provides a useful new premise, contradiction is likely a strong candidate.

Common Pitfalls

1. Misapplying the Negation: The most critical step is correctly stating the negation $\neg P$ of the proposition $P$. If you negate it incorrectly, the entire proof collapses. For example, the negation of "All swans are white" is not "No swans are white," but "There exists at least one swan that is not white." Always double-check your logic.
2. Circular Reasoning: A subtle trap is accidentally assuming the very thing you are trying to prove somewhere in your deductions. For instance, in the $\sqrt{2}$ proof, you cannot assume that a square being even implies the root is even without justification; this is a separate, established lemma that must be cited or proved separately. Every step must follow from the initial assumption $\neg P$ or established, independent facts.
3. Finding a Contradiction with the Wrong Thing: The contradiction must be an indisputable logical or mathematical falsehood, like $0=1$, or a direct clash with the initial assumption or a previously proven theorem. A contradiction with something you merely suspect or haven't proven isn't valid.
4. Overcomplicating the Argument: Sometimes, after assuming the negation, students force an overly complex series of steps. The most elegant proofs by contradiction are often surprisingly simple once you find the right path. The power lies in the logic, not the complexity of the algebra.

Summary

• Proof by contradiction establishes a statement $P$ is true by showing that assuming it is false ($\neg P$) leads to an impossible situation.
• The classic proof that $\sqrt{2}$ is irrational demonstrates the method's power by showing that assuming it is rational forces two numbers to be both coprime and even—a direct contradiction.
• Euclid's proof of the infinitude of primes constructs a new number from a hypothetical finite list of all primes, showing this number must be divisible by a prime not on the list, contradicting the list's completeness.
• This method is most effective for proving non-existence, uniqueness, and statements where the negation provides a useful, concrete starting point for deduction.
• Success depends on correctly stating the logical negation of the proposition and ensuring every subsequent step is valid and leads to an unambiguous contradiction with known facts or the initial assumption.