Skip to main content
⚡ Calmops
🤖 AI 🏗️ Architecture 🌐 Web 🗃️ Database ⚙️ DevOps 🌍 Network 💻 Programming 🧮 Algorithms 📐 Software Eng. ☁️ Cloud 🔒 Security 📈 Finance More →

Proof by Contradiction: Proving by Assuming the Opposite

Created: December 19, 2025 9 min read

Introduction

Proof by contradiction (also called reductio ad absurdum) is a powerful proof technique where you assume the opposite of what you want to prove and show that this assumption leads to a contradiction.

Understanding proof by contradiction is essential for:

  • Mathematics: Proving theorems that are difficult to prove directly
  • Computer Science: Verifying algorithm properties
  • Philosophy: Analyzing logical arguments
  • Formal Verification: Proving system properties
  • Critical Thinking: Identifying logical inconsistencies

This comprehensive guide explores proof by contradiction, its structure, applications, and when to use it.

What is Proof by Contradiction?

Definition

A proof by contradiction is a proof that:

  1. Assumes the negation of what you want to prove
  2. Uses logical reasoning to derive a contradiction
  3. Concludes that the original statement must be true

Structure

Goal: Prove P

Assume: ¬P (the opposite of what we want to prove)

Step 1: [Logical inference from ¬P]
Step 2: [Logical inference]
...
Step n: [Derive a contradiction: Q ∧ ¬Q]

Conclusion: Since ¬P leads to a contradiction, P must be true

Why It Works

Proof by contradiction works because:

  • Law of Excluded Middle: Either P or ¬P must be true
  • Consistency: A contradiction means our assumption is false
  • Logical Necessity: If ¬P is false, then P must be true

Basic Structure

The Contradiction

A contradiction is a statement of the form Q ∧ ¬Q (something and its opposite).

Examples:

  • “The number is both even and odd”
  • “The set is both empty and non-empty”
  • “The statement is both true and false”

Types of Contradictions

Type 1: Direct Contradiction

Assume: ¬P
Derive: P
Contradiction: P ∧ ¬P

Type 2: Contradiction with Known Fact

Assume: ¬P
Derive: Q (where Q is known to be false)
Contradiction: Q is both true and false

Type 3: Contradiction with Premises

Assume: ¬P
Derive: R (where R contradicts a premise)
Contradiction: R contradicts the premises

Classic Examples

Example 1: √2 is Irrational

Theorem: √2 is irrational (cannot be expressed as a ratio of integers)

Proof:

Assume: √2 is rational
Then: √2 = p/q for some integers p and q with no common factors

Squaring both sides:
2 = p²/q²
2q² = p²

This means p² is even, so p must be even.
Let p = 2k for some integer k.

Substituting:
2q² = (2k)² = 4k²
q² = 2k²

This means q² is even, so q must be even.

But now both p and q are even, contradicting our assumption that they have no common factors.

Therefore, √2 cannot be rational, so √2 is irrational.

Example 2: There are Infinitely Many Primes

Theorem: There are infinitely many prime numbers

Proof:

Assume: There are finitely many primes
Let p₁, p₂, ..., pₙ be all the primes

Consider the number: N = (p₁ × p₂ × ... × pₙ) + 1

N is not divisible by any of p₁, p₂, ..., pₙ because:
- N ÷ p₁ leaves remainder 1
- N ÷ p₂ leaves remainder 1
- ... and so on

So either:
1. N is prime (contradicting that we listed all primes), or
2. N has a prime factor not in our list (contradicting that we listed all primes)

Either way, we have a contradiction.

Therefore, there must be infinitely many primes.

Example 3: No Largest Even Number

Theorem: There is no largest even number

Proof:

Assume: There is a largest even number, call it M

Then M = 2k for some integer k.

Consider M + 2 = 2k + 2 = 2(k + 1)

M + 2 is also even and M + 2 > M.

This contradicts our assumption that M is the largest even number.

Therefore, there is no largest even number.

Example 4: √3 is Irrational

Theorem: √3 is irrational

Proof:

Assume: √3 is rational
Then: √3 = p/q for integers p, q with gcd(p,q) = 1

Squaring: 3 = p²/q²
So: 3q² = p²

This means p² is divisible by 3, so p is divisible by 3.
Let p = 3m.

Substituting: 3q² = (3m)² = 9m²
So: q² = 3m²

This means q² is divisible by 3, so q is divisible by 3.

But now both p and q are divisible by 3, contradicting gcd(p,q) = 1.

Therefore, √3 is irrational.

Logical Proofs by Contradiction

Example 1: Prove a Disjunction

Theorem: From (p → q) and ¬q, we can conclude ¬p

Proof:

Assume: p is true (the opposite of what we want to prove)

From (p → q) and p, we get q (by Modus Ponens).

But we know ¬q is true.

This contradicts q being true.

Therefore, p must be false, so ¬p is true.

Example 2: Prove Uniqueness

Theorem: If a = b and a = c, then b = c (uniqueness of equality)

Proof:

Assume: b ≠ c (the opposite of what we want to prove)

We know a = b and a = c.

By transitivity: b = a = c, so b = c.

This contradicts our assumption that b ≠ c.

Therefore, b = c.

When to Use Proof by Contradiction

Good Candidates for Proof by Contradiction

1. Proving Negations

  • “There is no largest prime”
  • “√2 is not rational”
  • “No perfect square ends in 2”

2. Proving Uniqueness

  • “There is exactly one solution”
  • “The limit is unique”

3. Proving Impossibility

  • “It’s impossible to trisect an angle with compass and straightedge”
  • “You cannot divide by zero”

4. When Direct Proof is Difficult

  • The conclusion is negative
  • The direct approach seems complicated
  • The contrapositive is also difficult

Poor Candidates for Proof by Contradiction

1. Simple Positive Statements

  • Better to use direct proof
  • Proof by contradiction is unnecessarily complex

2. When Contrapositive Works

  • Proof by contrapositive is often simpler
  • Proof by contradiction is more roundabout

Proof by Contradiction vs. Other Techniques

Contradiction vs. Direct Proof

Direct Proof: Assume premises, derive conclusion Contradiction: Assume negation of conclusion, derive contradiction

Example: Prove that if n is even, then n² is even

Direct Proof:

Assume n is even.
Then n = 2k.
So n² = 4k² = 2(2k²), which is even.

Proof by Contradiction:

Assume n² is odd.
Then n² = 2m + 1 for some integer m.
If n were even, n = 2k, so n² = 4k² = 2(2k²), which is even.
This contradicts n² being odd.
Therefore, n must be odd... wait, this doesn't work!

The direct proof is simpler here.

Contradiction vs. Contrapositive

Contrapositive: Prove ¬Q → ¬P instead of P → Q Contradiction: Assume ¬P and derive a contradiction

Example: Prove that if n² is even, then n is even

Contrapositive:

Prove: If n is odd, then n² is odd.
Assume n is odd: n = 2k + 1.
Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd.

Contradiction:

Assume n is odd.
Then n = 2k + 1.
So n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd.
But we assumed n² is even.
Contradiction!
Therefore, n must be even.

Both work, but contrapositive is more direct.

Common Mistakes

Mistake 1: Deriving the Wrong Contradiction

Wrong:

Assume: ¬P
Derive: Some unrelated fact Q
Conclude: Therefore P

Correct: The contradiction must be with the assumption or known facts.

Mistake 2: Assuming Too Much

Wrong:

Assume: ¬P
Assume: Some other unrelated statement R
Derive: Contradiction
Conclude: Therefore P

Correct: Only assume ¬P; don’t add extra assumptions.

Mistake 3: Circular Reasoning

Wrong:

Assume: ¬P
Derive: P (directly, without reasoning)
Conclude: Contradiction, so P

Correct: The derivation must follow logically from the assumption.

Practice Problems

Problem 1: Prove by Contradiction

Theorem: If n² is odd, then n is odd

Solution:

Assume: n is even (opposite of what we want to prove)
Then: n = 2k for some integer k
So: n² = 4k² = 2(2k²), which is even

But we know n² is odd.

This contradicts n² being even.

Therefore, n must be odd.

Problem 2: Prove Uniqueness

Theorem: The additive identity is unique (there is only one 0)

Solution:

Assume: There are two additive identities, 0 and 0'

Then: 0 + x = x for all x
And: 0' + x = x for all x

Consider 0 + 0' = 0' (using the first property)
And: 0 + 0' = 0 (using the second property)

So 0 = 0', contradicting our assumption that they are different.

Therefore, the additive identity is unique.

Problem 3: Prove Impossibility

Theorem: There is no integer that is both even and odd

Solution:

Assume: There exists an integer n that is both even and odd

Then: n = 2k for some integer k (n is even)
And: n = 2m + 1 for some integer m (n is odd)

So: 2k = 2m + 1
Therefore: 2(k - m) = 1
So: k - m = 1/2

But k and m are integers, so k - m is an integer.

This contradicts k - m = 1/2.

Therefore, no integer can be both even and odd.

Problem 4: Prove a Logical Statement

Theorem: From (p ∨ q) and ¬p, we can conclude q

Solution:

Assume: ¬q (opposite of what we want to prove)

We know (p ∨ q) is true, so at least one of p or q is true.
We know ¬p is true, so p is false.

Since p is false and (p ∨ q) is true, q must be true.

But this contradicts our assumption that ¬q.

Therefore, q must be true.

Online Learning Platforms

Interactive Tools

  • “How to Prove It” by Daniel J. Velleman - Comprehensive proof guide
  • “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook
  • “A Concise Introduction to Logic” by Patrick J. Hurley - Accessible introduction
  • “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook

Academic Journals

  • Journal of Symbolic Logic - Leading journal on mathematical logic
  • Studia Logica - International journal on logic and philosophy
  • Logic and Logical Philosophy - Open access journal

Software Tools

  • Prolog - Logic programming language
  • Coq - Interactive theorem prover
  • Isabelle - Generic proof assistant
  • Z3 - SMT solver

Glossary of Key Terms

  • Assumption: Statement assumed to be true at the start of a proof
  • Contradiction: Statement of the form Q ∧ ¬Q
  • Contrapositive: Equivalent form of a conditional
  • Proof by Contradiction: Proof technique assuming negation of conclusion
  • Reductio ad Absurdum: Latin term for proof by contradiction
  • Negation: Opposite of a statement

Conclusion

Proof by contradiction is a powerful technique for proving statements that are difficult to prove directly. By mastering proof by contradiction, you develop the ability to:

  • Prove negative statements
  • Prove uniqueness
  • Prove impossibility
  • Handle complex logical arguments
  • Understand the structure of logical reasoning

The next article in this series will explore Proof by Induction, a technique for proving statements about all natural numbers or recursively defined structures.

Have you used proof by contradiction in mathematics or logic? What was the most interesting contradiction you’ve derived? Share your examples in the comments below!

Comments