What Is Proof by Contradiction?
Proof by contradiction — also called reductio ad absurdum, Latin for “reduction to absurdity” — is a proof technique where you assume the opposite of what you want to prove and then show that this assumption leads to a logical impossibility.
The logic is simple: if assuming something false leads to a contradiction, the original statement must be true. You can’t have a statement that is simultaneously true and false in classical logic — and that’s exactly the contradiction you’re engineering.
To prove a statement P by contradiction:
- Assume ¬P (the negation of P)
- From ¬P, derive a statement Q
- Show that Q is false (or that Q contradicts a known fact or ¬P itself)
- Conclude that ¬P must be false, therefore P is true
The contradiction you derive doesn’t have to be any particular kind — it just has to be logically impossible. Common forms include: deriving that a number is both even and odd, that a set is both empty and non-empty, that a quantity is both greater than and less than some value, or that a previously proven theorem is violated.
The Standard Framework
Every proof by contradiction follows the same four-step structure. Once you internalize this framework, you can apply it to any problem.
Step 4 is where many students lose points. You must name the specific contradiction — it’s not enough to vaguely say “this is a contradiction.” State what two things conflict: for example, “we derived that n is both even and odd, which is impossible since no integer is both.”
Example 1: If n² Is Even, Then n Is Even
This is the classic introductory example, and it appears in nearly every discrete mathematics textbook. It’s a conditional statement (P → Q), and it happens to be one where proof by contradiction is the most natural approach.
The negation of “if n² is even then n is even” is “n² is even AND n is odd.” We assume both and look for trouble.
Goal: ∀n ∈ ℤ, (n² even) → (n even)
Assume: n² ≡ 0 (mod 2) ∧ n ≡ 1 (mod 2)
n = 2k + 1 for some k ∈ ℤ
n² = 2(2k² + 2k) + 1
n² is odd ← derived from assumption that n is odd
n² even ∧ n² odd → ⊥ (contradiction)
∀n ∈ ℤ: n² even → n even ∎
Example 2: √2 Is Irrational
This is probably the most famous proof by contradiction in all of mathematics. It dates back to ancient Greece and is attributed to Hippasus of Metapontum. The idea is to assume √2 is rational and show this leads to an integer that is both even and odd.
Recall that a number is rational if it can be written as p/q where p and q are integers with no common factors (the fraction is in lowest terms).
Assume: √2 = p/q, gcd(p,q) = 1, p,q ∈ ℤ, q ≠ 0
p² = 2q²
p² even → p even → p = 2k for some k ∈ ℤ
(2k)² = 2q² → 4k² = 2q² → q² = 2k²
q² even → q even
p even ∧ q even → 2 | gcd(p,q) → gcd(p,q) ≥ 2 ≠ 1 → ⊥
Notice the structure: the contradiction comes from the very assumption we put in place at the start (gcd = 1). We derived that the fraction can’t be in lowest terms — directly violating our setup. This is a clean and powerful contradiction.
Example 3: There Are Infinitely Many Prime Numbers
This proof is over 2,300 years old — Euclid proved it around 300 BCE — and it remains one of the most elegant examples of proof by contradiction ever constructed. The key insight is to assume finitely many primes and construct a number that can’t be divisible by any of them.
Assume: {p₁, p₂, ..., pₙ} is the complete list of all primes
N = p₁ · p₂ · p₃ · ... · pₙ + 1
∃ prime p such that p | N
p | (p₁ · p₂ · ... · pₙ)
p | N ∧ p | (N−1) → p | 1 → ⊥ (no prime divides 1)
Students often think N itself must be prime. It doesn’t have to be. For example, if we took primes {2, 3, 5, 7, 11, 13} and formed N = 2·3·5·7·11·13 + 1 = 30031 = 59 × 509, which is not prime. The point is that N’s prime factors are not in our original list — and that’s the contradiction.
When to Use Proof by Contradiction
Proof by contradiction is not always the best choice. Knowing when to reach for it saves time and produces cleaner proofs.
Use contradiction when:
- You’re proving something is irrational, impossible, or doesn’t exist
- The negation of the conclusion gives you a much stronger working assumption than the original statement provides
- You’re proving infinitude — there is no direct way to construct infinitely many things, but assuming finitely many leads to contradiction
- A direct proof would require constructing an object you have no natural way to build
Consider direct proof or contrapositive when:
- The conclusion follows naturally from the hypothesis in a few steps
- The negation of the conclusion doesn’t obviously lead anywhere useful
- The statement is a straightforward conditional P → Q where assuming P and doing algebra gives Q
| Method | What you assume | What you derive | Best for |
|---|---|---|---|
| Direct proof | P (hypothesis) | Q (conclusion) | Straightforward conditionals |
| Contrapositive | ¬Q | ¬P | When negating conclusion gives a strong starting point |
| Contradiction | ¬P (negation of entire goal) | Any contradiction ⊥ | Irrationality, impossibility, infinitude, existence |
| Induction | P(k) for arbitrary k | P(k+1) | Statements about all natural numbers |
Common Mistakes
These are the errors that cost students points most often when writing proofs by contradiction.
Not naming the contradiction explicitly
Ending a proof with “this is a contradiction” without saying what two things conflict is incomplete. You must identify the specific logical impossibility: “We derived that n is both even and odd, which contradicts the fact that no integer can be both.”
Assuming the wrong negation
For a conditional P → Q, the negation is P ∧ ¬Q (P is true and Q is false). A common mistake is assuming only ¬Q, which is actually proof by contrapositive, not contradiction. For simple existence statements like “there exists a prime greater than 100,” the negation is “there is no prime greater than 100” — make sure you negate the entire statement.
Circular reasoning
Using the statement you’re trying to prove as a step in the proof is circular and invalid. Every step in the derivation must follow from the contradiction assumption, known definitions, previously proven theorems, or the axioms of arithmetic — not from the original claim.
Losing track of what was assumed
In longer proofs, students sometimes forget which statements came from the assumption and which came from prior results. Keeping a clear “we assumed X” note at the start helps you verify at the end that the contradiction genuinely conflicts with X.
On exams, write the phrase “Assume for contradiction that [¬P]” at the beginning of the proof — not just “assume ¬P.” The phrase “for contradiction” signals to the grader that you know what proof method you’re using and why the contradiction matters at the end.
Practice Problems
These problems are well-suited to proof by contradiction. Try to identify what to assume and what contradiction to look for before writing anything.
- Prove that if n³ is even, then n is even.
- Prove that log₂(3) is irrational.
- Prove that there is no largest even integer.
- Prove that the sum of a rational and an irrational number is irrational.
- Prove that if p is prime and p | ab, then p | a or p | b. (This is Euclid’s lemma.)
For problems 1–3, the negation is straightforward. Problem 4 requires carefully applying the definition of rational numbers. Problem 5 is harder — it’s worth looking at the proof structure of the primes example for inspiration on how to use divisibility.
Frequently Asked Questions
What is the difference between proof by contradiction and proof by contrapositive?
Proof by contrapositive proves P → Q by proving the logically equivalent ¬Q → ¬P. You assume only ¬Q and derive ¬P — there is no contradiction involved. Proof by contradiction assumes ¬(P → Q), which means P and ¬Q simultaneously, and then derives any contradiction, not necessarily ¬P. The two methods are related but distinct: every proof by contrapositive can be rewritten as a contradiction, but not every contradiction proof is a contrapositive in disguise.
Can proof by contradiction prove any statement?
In classical logic, yes — any true statement can in principle be proved by contradiction. In intuitionistic logic (used in some areas of constructive mathematics and type theory), proof by contradiction has limitations. For most discrete mathematics coursework, classical logic applies and contradiction is universally valid.
How do I know what contradiction to look for?
You usually don’t know in advance — you derive consequences of the assumption until something impossible appears. The most common contradiction types in discrete math are: a number that is both even and odd, a fraction not in lowest terms that you assumed was, a set being both finite and infinite, or a value simultaneously satisfying two inequalities that can’t both hold. Working through the algebra and definitions usually reveals the contradiction naturally.