Proof by Contradiction Explained

The logic behind the method

Proof by contradiction rests on a basic law of classical logic: a statement is either true or false, with no third option. To prove a claim P, you temporarily assume its negation, not P, and combine that assumption with known facts to derive something impossible, such as a statement that is both true and false at once. Since a contradiction can never actually hold, your assumption not P must have been untenable, which leaves P as the only possibility.

The structure is worth stating cleanly. You want to prove P. You suppose not P. You reason validly until you reach an absurdity. You conclude that not P is impossible, hence P holds. The entire burden of the proof is to reach that absurdity, so the creative work lies in seeing which known fact your false assumption ends up violating.

• Assume the negation of what you want to prove.
• Reason with valid steps from that assumption.
• Derive an impossibility, a contradiction.
• Conclude the negation was false, so the claim is true.

A related cousin: the contrapositive

Contradiction is often confused with proving the contrapositive, and the two are closely related but distinct. To prove if P then Q by contrapositive, you instead prove if not Q then not P, which is logically equivalent to the original. This is really a direct proof of an equivalent statement, and it introduces no contradiction.

Proof by contradiction is broader. It can prove statements that are not phrased as implications at all, such as there is no largest prime or the square root of 2 is irrational. When a claim asserts that something does not exist or cannot happen, contradiction is frequently the natural approach, because assuming the thing does exist gives you a concrete object to reason about and eventually break.

The classic example: the square root of 2 is irrational

Claim: the square root of 2 cannot be written as a fraction of two integers. Suppose, for contradiction, that it can. Then the square root of 2 equals a over b, where a and b are integers with no common factor, meaning the fraction is already in lowest terms. This reduced form is the assumption we will eventually contradict.

Square both sides. Two equals a squared over b squared, so a squared equals 2 times b squared. That means a squared is even, and since the square of an odd number is odd, a itself must be even. Write a as 2 times c for some integer c. Substituting gives 2 times b squared equals 4 times c squared, so b squared equals 2 times c squared, which makes b squared even and therefore b even as well.

But now both a and b are even, so they share the common factor 2. That contradicts our assumption that the fraction was in lowest terms with no common factor. The contradiction shows our supposition was impossible, so the square root of 2 cannot be written as such a fraction and is therefore irrational.

Why the contradiction lands

The engine of that proof is the choice to start from a fraction in lowest terms. That single stipulation is what the derivation eventually violates, so setting it up front is the strategic move. Without it, discovering that a and b are both even would be unremarkable; with it, that discovery is fatal.

This illustrates a general pattern in contradiction proofs. You often build a small amount of extra structure into your false assumption, choose a minimal counterexample, or a reduced form, or a smallest element, precisely so that the eventual contradiction has something to bump against. Learning to see what structure to demand is much of the skill.

When to reach for contradiction

Contradiction is a strong default for non-existence and impossibility claims, statements of the form there is no such thing or this can never happen. Assuming the forbidden object exists hands you material to work with, and irrationality proofs, proofs that certain equations have no integer solutions, and the classic proof that there are infinitely many primes all follow this shape.

It is less appropriate when a direct proof is readily available, because an unnecessary contradiction can obscure a clean argument and is easier to get subtly wrong. A common beginner habit is to wrap a perfectly good direct proof inside an assume not P shell that is never actually used. If you reach the conclusion without ever invoking the contradiction, you had a direct proof all along and should present it as one.

• Strong choice for non-existence and impossibility claims.
• Useful when assuming the negation hands you a concrete object.
• Avoid when a clean direct proof is already in reach.
• If you never use the false assumption, rewrite it as a direct proof.