Course contentsShow
← Mathematics
Lesson 2498 of 3,12150. Discrete Math — Logic and ProofFree lesson

Proof by Contradiction: Common Patterns

Recognizing when contradiction is the natural choice, such as proving uniqueness, irrationality, or nonexistence.

Proof by Contradiction: Common Patterns

You'll learn when proof by contradiction is the most natural technique: proving uniqueness, irrationality, or nonexistence.

The Natural Fit

While you can use proof by contradiction for many statements, certain mathematical claims practically invite it. Recognizing these patterns saves time and leads to cleaner proofs.

Three Classic Patterns

1. Proving Nonexistence

When asked to prove "there does not exist an object with property P," assume such an object does exist and derive a contradiction. This is often the only straightforward approach.

Example: Proving no largest prime number exists. Assume there is a largest prime p, construct a new candidate prime from the product of all primes plus one, reach contradiction.

2. Proving Irrationality

To show a number is irrational (cannot be written as p/q), assume it can be written as a fraction in lowest terms, then derive that both numerator and denominator share a common factor—contradicting "lowest terms."

Example: The classic proof that √2 is irrational assumes √2 = p/q, squares both sides, and shows both p and q must be even.

3. Proving Uniqueness

To prove "there exists exactly one object with property P," first prove existence (usually direct), then assume two distinct objects both satisfy P. Show they must actually be identical—contradicting "distinct."

Example: Proving a function has a unique fixed point: assume two different fixed points x₁ and x₂, use the function's properties to show x₁ = x₂.

Why These Patterns Work

These statements are inherently negative ("not rational," "does not exist," "no other exists"). Assuming the opposite gives you something concrete to work with—an object, a fraction, a second solution—which you can manipulate until logic breaks down.

Key Takeaway: Proof by contradiction is the natural choice when proving nonexistence, irrationality, or uniqueness—cases where assuming the opposite gives you tangible objects to reason about until reaching a logical impossibility.