Not sure which lesson to do first? Find your level and get a plan →

Math · Sets & Logic · Grade 9-12

Proof by Contradiction

Proof by contradiction (reductio ad absurdum) proves P by assuming ¬P, deriving a contradiction like 0=1 or 'an integer that is both even and odd', and concluding P holds.


Quick Answer

Proof by contradiction (reductio ad absurdum) proves P by assuming ¬P, deriving a contradiction like 0=1 or 'an integer that is both even and odd', and concluding P holds. Use it when a claim says something does not exist or cannot happen (no largest prime, no fraction equal to 2), because assuming the opposite hands you a specific object to work with. The logic rests on one fact: valid steps from a true assumption can never reach something impossible, so the assumption must be false.

Why This Matters

Some of the most important facts in mathematics, such as that there are infinitely many primes and that 2 is irrational, have no natural forward proof, because "there is no fraction" gives you nothing to compute with. Contradiction turns them into problems with something concrete to work on. Used carelessly, it produces arguments that end at a merely surprising statement and prove nothing.

Intuitive Explanation

Claim: there is no largest whole number. Suppose there were one, and call it N. Then N+1 is a whole number bigger than N, so N wasn't the largest after all. The assumption defeats itself, so it is false: there is no largest whole number. That is the whole method: assume the opposite, follow valid steps, reach something impossible, and blame the assumption.

The power comes from what the assumption gives you. "There are infinitely many primes" is hard to attack head-on, but "suppose there are only finitely many, p1,p2,…,pk" hands you a list. Multiply them all and add 1: M=p1p2⋯pk+1. Dividing M by any prime on the list leaves remainder 1, so none of them divides M. Yet every whole number above 1 has a prime factor, so M has one that is missing from the list, and the list was not complete. M itself need not be prime: 2⋅3⋅5⋅7⋅11⋅13+1=30031=59⋅509.

The ending must be truly impossible: 1=0, an integer that is both even and odd, a fraction in lowest terms whose top and bottom are both even. A statement that is only surprising, such as "then n is bigger than a million", is not a contradiction. The method also differs from the contrapositive. To prove "if P then Q" by contrapositive, you assume only "not Q" and prove "not P" directly; by contradiction, you assume P and "not Q" together and look for any impossibility.

Think of it like this. It works like checking an alibi. Suppose the suspect was at the scene; then they were in two cities at 9 p.m., which is impossible, so they weren't there. The reasoning holds only if every step is solid: a wrong clock, like a faulty algebra step, can produce a false impossibility.

Core idea. Proof by contradiction assumes the negation of your claim, follows valid logic until it produces something impossibly false, and concludes the original claim must be true.


When to Use

Reach for contradiction when a claim says something does not exist, cannot happen or is irrational, or when "suppose not" gives you a concrete object (a largest prime, a fraction ab) while the claim itself gives nothing. Negate carefully: "for every x" becomes "for some x". For an if-then where assuming "not Q" alone is enough, prove the contrapositive directly; to show a claim is false, give a counterexample instead.

Tip. Ask: Did I assume the claim is FALSE and then derive a genuinely impossible statement from it?

How to Recognize It

Before choosing contradiction, write out exactly what the negation of the claim says and check whether it hands you something concrete to work with.

  1. Does the claim say that something does not exist, such as a largest prime or a fraction equal to 2?

    If yes, supposing it does exist hands you a specific object, which is exactly what contradiction needs. If the claim is an if-then with a usable hypothesis, a direct proof is usually shorter.

  2. Does the claim contain 'for all' or 'every', which will flip when you negate it?

    If yes, the negation is 'at least one fails': 'every multiple of 4 is even' negates to 'some multiple of 4 is odd'. Negating only part of the claim proves nothing.

  3. Is the claim an if-then where assuming only 'not Q' leads straight to 'not P'?

    If yes, write it as a contrapositive proof, which is cleaner. Contradiction assumes P and 'not Q' together and may end at any impossibility, not necessarily at 'not P'.

  4. Is the goal to show that a 'for all' claim is false?

    If yes, you need a counterexample, one case that fails, and no contradiction at all. Contradiction proves a claim true by showing its opposite is impossible.

Proof by Contradiction compared with Direct proof, Contrapositive proof, and Counterexample

All four rows involve a negation or a failing case somewhere, which is why they blur. Ask what you assume and what you aim for: the whole claim false, the hypothesis true, only the conclusion false, or one case that breaks a general claim.

Proof by Contradiction

Meaning
Use this when the claim is a nonexistence or irrationality statement, or assuming its negation is more concrete than proving it directly.
Key test
Did I assume the claim is FALSE and then derive a genuinely impossible statement from it?
Example
Prove that 2 is irrational.

Direct proof

Meaning
Assumes the hypothesis is TRUE and builds forward to the conclusion, with no negation.
Key test
Use when assuming P gives a concrete foothold and you can reach Q directly.
Formula
P⇒Q
Example
Assume n=2k, show n2 is even

Contrapositive proof

Meaning
Proves '¬Q⇒¬P' directly — assumes ONLY the conclusion's negation, not the whole claim's.
Key test
Use for an implication P⇒Q when flipping it reads more cleanly.
Formula
¬Q⇒¬P
Example
Prove 'n odd ⇒n2 odd' to get 'n2 even ⇒n even'

Counterexample

Meaning
DISPROVES a universal claim by exhibiting one case that fails it — the opposite goal.
Key test
Use when you want to show a 'for all' statement is false, not prove a statement true.
Example
n2−n+41 is prime fails at n=41

Formula & Notation

How to read it: Structure: Assume ¬P, derive contradiction, conclude P.

Worked Examples

Example 1 — Irrationality of 2

Easy

Prove that 2 is irrational.
Show the steps and the answer
  1. Assume the opposite: 2=ab for positive integers a and b, with the fraction in lowest terms.

    "Irrational" means no such fraction exists; assuming one does gives two integers to work with, and any fraction can be reduced, so "lowest terms" costs nothing.

  2. Square and clear the fraction: 2=a2b2, so a2=2b2.

    Now the statement is about integers, where even and odd can be used.

  3. Deduce that a is even: a2 is even, and an odd number squared is odd, so a=2c for some integer c.

    This uses the result that an even square comes from an even number.

  4. Substitute: (2c)2=2b2 gives 4c2=2b2, so b2=2c2, and by the same reasoning b is even.

    Now 2 divides both a and b, which contradicts "lowest terms", so the assumption was false.

Answer: Contradiction, so 2 is irrational

Takeaway: Assume the fraction exists in lowest terms and show that top and bottom must both be even; that impossibility proves 2 is irrational.

Example 2 — Just the contrapositive

Standard

Prove: if n2 is even then n is even. A student writes 'assume n2 even and n odd...'. Is this really contradiction?
Show the steps and the answer
  1. Follow the student's route: n odd gives n=2k+1 and n2=2(2k2+2k)+1, which is odd, clashing with "n2 even".

    It is a valid proof by contradiction, but look at which assumption did the work.

  2. Notice that "n2 even" was used only at the very end, to clash with "n2 odd".

    When the hypothesis appears only in the final clash, the real content is "odd n gives odd n2", a direct statement.

  3. Rewrite as the contrapositive: prove "if n is odd, then n2 is odd" directly, with the same algebra.

    A statement and its contrapositive are equivalent, so this proves the claim without assuming anything false.

Answer: Contrapositive is cleaner than contradiction here

Takeaway: If the hypothesis is used only to clash with what you derived from "not Q", the proof is really a contrapositive; write it that way.

Example 3 — Find the mistake: the wrong negation

Application

Claim: for every integer n, n2+n is even. Riya writes: "Suppose that for every integer n, n2+n is odd. But n=1 gives 1+1=2, which is even. Contradiction, so the claim is true." Find the mistake and correct it.
Show the steps and the answer
  1. Write the correct negation: the claim is "for every n, n2+n is even", so its negation is "there is at least one integer n with n2+n odd".

    Negating "for every" gives "there exists", not "for every" with the opposite property.

  2. See why Riya's version fails: refuting "every n2+n is odd" with n=1 still allows some values to be odd and some even.

    Ruling out "all odd" does not rule out "some odd", so the claim is not yet proved.

  3. Assume the correct negation: some integer n has n2+n=n(n+1) odd.

    Factoring shows the expression is a product of two consecutive integers.

  4. Reach the impossibility: one of n and n+1 is even, so n(n+1) is even, contradicting "odd".

    No number is both even and odd, so no such n exists, and n2+n is even for every integer n.

Answer: Riya negated the claim wrongly. Correct negation: some n has n2+n odd. But n2+n=n(n+1) is always even, a contradiction, so the claim holds.

Takeaway: The negation of "for every n, P(n)" is "for some n, not P(n)"; assume anything else and you prove less than you think.

Where You'll See It

  • Two Londoners with the same hair count

    No one has more than 1,000,000 hairs on their head, so there are at most 1,000,001 possible counts (0 to 1,000,000). Suppose London's roughly 9 million people all had different counts: that needs 9 million different numbers, which is impossible. So at least two people have exactly the same number of hairs.

  • Why no zip program shrinks every file

    Suppose a compressor made every 10-bit file shorter. There are 210=1024 such files but only 1+2+4+⋯+512=1023 shorter bit strings, so two different files would compress to the same output and one could not be restored. Contradiction: some files must stay the same size or grow.

Common Mistakes

  1. The slip: Negating only part of the claim

    Instead: the negation of 'for all x, P(x)' is 'there exists x with not P(x)', so flip quantifiers carefully.

  2. The slip: Ending at a strange-but-true statement and calling it a contradiction

    Instead: you must reach something logically impossible, like 1=0 or an integer that is both even and odd.

  3. The slip: Confusing it with contrapositive

    Instead: contradiction assumes the negation of the WHOLE claim and seeks any impossibility; contrapositive only flips an implication and stays direct.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Prove by contradiction that there are no integers a and b with 2a+4b=7.

    Hint: Assume such integers exist. Is the left side even or odd?

  2. For integers a and b with a+b=15, prove by contradiction that a≥8 or b≥8.

    Hint: The negation of "a≥8 or b≥8" is "a≤7 and b≤7".

  3. Prove by contradiction that there is no smallest positive rational number.

    Hint: Suppose r is the smallest. Find a smaller positive rational.

  4. Prove by contradiction that log⁡23 is irrational.

    Hint: Suppose log⁡23=pq with positive integers p and q. Rewrite this without logs.

  5. Claim A: "No odd number is divisible by 4." Claim B: "Every odd number is prime." Which should you attack with a counterexample, and which should you prove by contradiction?

    Hint: Is each claim true or false?

  6. To prove "every integer n has n2≥0", Kim begins: "Assume every integer has n2<0." Correct her opening.

    Hint: How do you negate "every"?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

How does the proof that 2 is irrational actually go?

Assume 2\sqrt{2} equals a fraction ab\frac{a}{b} already reduced to lowest terms. Squaring gives a2=2b2a^2 = 2b^2, so a2a^2 is even, which forces aa to be even; write a=2ca = 2c. Then 4c2=2b24c^2 = 2b^2, so b2=2c2b^2 = 2c^2, and bb is even too. But if aa and bb are both even, the fraction was not in lowest terms, which contradicts the starting assumption.

Does Euclid's argument mean 2×3×5×7×11×13+1 is prime?

No, and this trips up many students. That number is 30,031, which equals 59×50959 \times 509. Euclid's argument says only that the product plus 1 has some prime factor missing from the list. It may be the number itself, or a smaller prime, like 59 here. The proof shows that a new prime exists without promising that the formula produces it.

Why do some mathematicians try to avoid proof by contradiction?

A contradiction proof shows that something must be so, but often not how. Proving that 'nothing exists' leads to a contradiction may give no way to find the thing that exists. A school of mathematics called intuitionism, begun by L. E. J. Brouwer in the early 1900s, refused to accept such existence proofs. Most mathematicians do accept them, but many still rewrite a contradiction proof as a direct one when they can.

Can contradiction prove facts in geometry?

Yes. To show a triangle cannot have two right angles, suppose it does. Those two angles already add to 180∘180^\circ, leaving 0∘0^\circ for the third, so the two sides that should meet at the third corner would be parallel and never meet. That is not a triangle at all. Euclid used contradiction often, and many classical results about what cannot happen in geometry are proved this way.

Learning Path

Proof by Contradiction

You are here

Next →

Nothing after this yet
You need Contradiction (a statement and its negation can't both be true), Logical Statement and Direct Proof first. Proof by contradiction adds a new move: assume the claim is false and derive an impossibility. With it you can prove that numbers such as 2 and log⁡23 are irrational, that there are infinitely many primes, and that certain puzzles have no solution at all.

See Also