Proof by Contrapositive

Prove an if-then statement by assuming its conclusion is false and showing that its hypothesis must be false too.

Advanced25 min18 problems
Practice Problems

Definition

A proof by contrapositive proves an if-then statement p→qp \to q by proving its contrapositive ¬q→¬p\neg q \to \neg p instead. You assume the conclusion is false and show that the hypothesis must then be false.
Why this is allowed (a recap of the lesson Contrapositive): a statement and its contrapositive are logically equivalent. Their columns in the truth table are identical in every row:
pqp→q¬q¬p¬q→¬pFFTTTTFTTFTTTFFTFFTTTFFT\begin{array}{c|c|c|c|c|c} p & q & p \to q & \neg q & \neg p & \neg q \to \neg p \\ \hline F & F & T & T & T & T \\ F & T & T & F & T & T \\ T & F & F & T & F & F \\ T & T & T & F & F & T \end{array}
So once ¬q→¬p\neg q \to \neg p is proven, p→qp \to q is proven too.
The plan of the proof:
  1. 1.Write the contrapositive: negate the hypothesis and the conclusion, then swap them.
  2. 2.Assume ¬q\neg q (the conclusion is false).
  3. 3.Work forward with definitions and algebra, exactly as in a direct proof.
  4. 4.Arrive at ¬p\neg p (the hypothesis is false).
  5. 5.Conclude: the contrapositive is true, so the original statement is true.
When to choose it: when the hypothesis pp gives you little to work with ("n2n^2 is even" says nothing simple about nn), but the negated conclusion ¬q\neg q is concrete ("nn is odd" means n=2k+1n = 2k + 1).
Not the same as proof by contradiction: there you assume pp and ¬q\neg q together and look for *any* contradiction. Here you assume only ¬q\neg q and aim at one fixed target: ¬p\neg p.

Try it now

Which statement is the contrapositive of "If n2n^2 is even, then nn is even"?

Worked Examples

Prove: for every integer nn, if n2n^2 is even, then nn is even.
1

Write the contrapositive

Negate both parts and swap them: "if nn is not even, then n2n^2 is not even" → If nn is odd, then n2n^2 is odd
2

Assume the negated conclusion

Assume nn is odd, so n=2k+1n = 2k + 1 for some integer kk → n=2k+1n = 2k + 1
3

Square and expand

n2=(2k+1)2=4k2+4k+1n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 → n2=4k2+4k+1n^2 = 4k^2 + 4k + 1
4

Bring it into the form 2m + 1

n2=2(2k2+2k)+1n^2 = 2(2k^2 + 2k) + 1, and m=2k2+2km = 2k^2 + 2k is an integer → n2n^2 is odd
5

Conclude

We proved "nn odd ⇒\Rightarrow n2n^2 odd", the contrapositive of the statement → If n2n^2 is even, then nn is even

Common Mistakes

Proving the converse instead of the contrapositive: for "if n2n^2 is even, then nn is even", assuming nn is even and showing n2n^2 is even

Why it's wrong: That proves q→pq \to p, the converse, which is a different statement. A statement and its converse are not equivalent.

Correct: Negate both parts and swap them: assume nn is odd (¬q\neg q) and show n2n^2 is odd (¬p\neg p).

Negating "xx and yy are odd" as "xx and yy are even"

Why it's wrong: The conclusion fails as soon as one of the numbers is even. "Both even" covers only part of the cases, so the proof would be incomplete.

Correct: "Not (aa and bb)" is "not aa or not bb": xx is even or yy is even. Then prove every case.

Negating x≥5x \geq 5 as x≤5x \leq 5

Why it's wrong: The value x=5x = 5 satisfies both x≥5x \geq 5 and x≤5x \leq 5, so x≤5x \leq 5 is not the opposite of x≥5x \geq 5.

Correct: The negation of x≥5x \geq 5 is x<5x < 5, and the negation of x>5x > 5 is x≤5x \leq 5.

Assuming ¬q\neg q and then hunting for "some contradiction"

Why it's wrong: That mixes two methods. In a proof by contrapositive there is no contradiction: you have one clear target.

Correct: Assume ¬q\neg q and work until you reach exactly ¬p\neg p. The search for any contradiction belongs to proof by contradiction.

Interactive Visual

Truth Table

Expressionp → q ↔ ¬q → ¬p
pqp → q¬q¬p¬q → ¬pp → q ↔ ¬q → ¬p
FFTTTTT
FTTFTTT
TFFTFFT
TTTFFTT

T= TrueF= False

Interactive Sandbox

Expression Calculator

Try these:

History

No calculations yet

Practice Problems

18 problems
Problem 1 of 18
Easy
Which statement is the contrapositive of "If n2n^2 is even, then nn is even"?

Why It Matters

Proof by contrapositive is one of the most useful tools in a mathematician's kit:
  • It turns vague hypotheses into concrete ones: "n2n^2 is even" is hard to use, "nn is odd, so n=2k+1n = 2k + 1" is easy to use
  • It handles "or" conclusions neatly: the negation of "x≥5x \geq 5 or y≥5y \geq 5" is the friendly "x<5x < 5 and y<5y < 5"
  • It powers classic results: the proof that 2\sqrt{2} is irrational starts from the fact that n2n^2 even forces nn even, which is proven by contrapositive
  • It is everyday reasoning: "if the alarm works, it beeps in a test" means "no beep, so the alarm is broken"
  • It prepares you for proof by contradiction, the next lesson in this topic, by training you to negate statements correctly
Once you can negate statements and switch viewpoints, many proofs that look impossible directly become a few lines long.

Real World Applications

Quality Control

Inspectors use contrapositive reasoning to rule out cases without weighing every item twice.

Example:

Rule: if a pack of 4 boxes weighs at least 2000 g, then at least one box weighs at least 500 g. Contrapositive: if every box weighs less than 500 g, the pack weighs less than 2000 g.

1Try It Yourself

A machine fills 4 boxes and none of them can hold more than 495 g.

Show with the contrapositive that the pack cannot reach 2000 g.

Step 1: Write the mathematical expression

Largest possible total of the 4 boxes:

Testing Software

Programmers test code with the contrapositive: if the code is correct, a test gives the right output, so a wrong output proves a bug.

Example:

A function should compute f(n)=3n+2f(n) = 3n + 2. We proved: if f(n)f(n) is odd, then nn is odd. Contrapositive: an even nn must give an even result.

2Try It Yourself

A test calls the function with n=8n = 8 and the program returns 27.

What should the correct output be, and what does 27 tell you?

Step 1: Write the mathematical expression

Compute the correct value f(8)f(8):

Check Digits in Codes

Many codes use a simple rule to catch typing errors. The contrapositive tells you when a code is certainly wrong.

Example:

Rule: if a code is valid, then the sum of its digits is divisible by 9. Contrapositive: if the digit sum is not divisible by 9, the code is not valid.

3Try It Yourself

Someone types the code 4726.

Use the contrapositive to decide whether the code can be valid.

Step 1: Write the mathematical expression

Sum of the digits:

Key Takeaways

  • 1A proof by contrapositive proves p→qp \to q by proving ¬q→¬p\neg q \to \neg p
  • 2It works because a statement and its contrapositive are logically equivalent (identical truth table columns)
  • 3Plan: assume the conclusion is false, work forward, reach the hypothesis being false
  • 4Choose it when the negated conclusion is concrete, for example "nn is odd" gives n=2k+1n = 2k + 1
  • 5Negate carefully: "and" becomes "or", "or" becomes "and", ≥\geq becomes <<
  • 6Unlike proof by contradiction, you assume only ¬q\neg q and aim at one target, ¬p\neg p

Frequently Asked Questions

Because they are logically equivalent: in the truth table, p→qp \to q and ¬q→¬p\neg q \to \neg p are false in exactly the same row (pp true, qq false) and true in all others. Proving one proves the other.
Because they are logically equivalent: in the truth table, p→qp \to q and ¬q→¬p\neg q \to \neg p are false in exactly the same row (pp true, qq false) and true in all others. Proving one proves the other.
Look at the hypothesis. If it is hard to use (a statement about n2n^2, a product, a sum) while the negated conclusion gives you a formula (n=2kn = 2k, n=2k+1n = 2k + 1, x<5x < 5 and y<5y < 5), the contrapositive is usually shorter.
In proof by contradiction you assume pp and ¬q\neg q and look for any impossible situation. In proof by contrapositive you assume only ¬q\neg q and must reach the specific statement ¬p\neg p. Every proof by contrapositive can be rewritten as a contradiction proof, but not every contradiction proof is a contrapositive.
Not automatically. The converse q→pq \to p is a separate statement. For example, "if n2n^2 is even, then nn is even" and its converse "if nn is even, then n2n^2 is even" are both true, but each needs its own proof.

Glossary

Contrapositive
The statement ¬q→¬p\neg q \to \neg p formed from p→qp \to q by negating both parts and swapping them
Proof by contrapositive
A proof of p→qp \to q that assumes ¬q\neg q and derives ¬p\neg p
Logically equivalent
Two statements that have the same truth value in every row of the truth table
Negation
The statement "not pp" (¬p\neg p), true exactly when pp is false
Converse
The statement q→pq \to p; it is not equivalent to p→qp \to q
Even / odd integer
An integer of the form 2k2k (even) or 2k+12k + 1 (odd), where kk is an integer

Formula Card

Contrapositive equivalence

p→q  ≡  ¬q→¬pp \to q \;\equiv\; \neg q \to \neg p

Proving the right side proves the left side

Negating "and"

¬(a∧b)≡¬a∨¬b\neg(a \land b) \equiv \neg a \lor \neg b

Not both: at least one fails

Negating "or"

¬(a∨b)≡¬a∧¬b\neg(a \lor b) \equiv \neg a \land \neg b

Neither: both fail

Even and odd

n=2kn = 2k (even),   n=2k+1\; n = 2k + 1 (odd)

The concrete forms you get after negating "even" or "odd"

Today's challengeOne problem, three tries

More in This Topic

Introduction to Mathematical Proofs

Advanced25 min

Direct Proof

Advanced25 min

Two-Column Proofs

Intermediate25 min

Paragraph Proofs

Advanced30 min