Proof by contradiction | Varsity Tutors

SECTION 1

Historical Context & Motivation

The technique known as proof by contradiction — or reductio ad absurdum — is one of the oldest and most powerful strategies in the mathematician's toolkit. Its core idea is elegantly subversive: rather than constructing a direct path from hypotheses to conclusion, the prover assumes the conclusion is false and then demonstrates that this assumption collapses into a logical impossibility. The resulting contradiction confirms that the original statement must be true. This indirect style of reasoning has shaped the development of mathematics from Euclidean geometry through modern set theory, and it remains indispensable wherever direct arguments are difficult or impossible to construct.

The method appears implicitly in the earliest surviving mathematical texts, but it was the ancient Greeks who elevated it to a systematic proof strategy. Understanding when and why this technique was formalized helps illuminate the logical foundations on which all modern proof theory rests.

~450 BCE

Pythagorean Irrationality

A member of the Pythagorean school (often attributed to Hippasus) proved that √2 is irrational by assuming it could be written as a ratio of integers and deriving a contradiction — one of the earliest recorded uses of reductio ad absurdum.

~300 BCE

Euclid's Elements

Euclid employed proof by contradiction extensively, most famously to show that there are infinitely many primes (Book IX, Proposition 20). His systematic use cemented the technique as a standard tool in mathematical reasoning.

1870s

Cantor's Diagonal Argument

Georg Cantor used a contradiction-based diagonal argument to prove that the real numbers are uncountable, establishing that different sizes of infinity exist and launching modern set theory.

1930s

Gödel and Turing

Kurt Gödel's incompleteness theorems and Alan Turing's proof of the undecidability of the halting problem both relied on contradiction arguments, demonstrating the technique's reach into mathematical logic and computation.

Across these milestones, a recurring theme emerges: proof by contradiction excels precisely when the statement to be proved asserts the nonexistence or impossibility of something. Trying to verify nonexistence directly can be like searching an infinite haystack, but contradiction collapses the search by showing that even a single hypothetical needle leads to absurdity. The central question this lesson addresses is: How do we rigorously structure a proof by contradiction, and when is it the right strategy?

SECTION 2

Core Principles & Definitions

Before wielding proof by contradiction effectively, one must understand the logical machinery that makes it valid. The technique rests on a small number of foundational principles from classical propositional logic. Each principle contributes an essential piece to the argument structure, and together they guarantee that the method is sound — meaning it can never prove a false statement.

Law of Excluded Middle

For any proposition P, exactly one of P or ¬P is true. There is no middle ground. This tautology (P ∨ ¬P) ensures that negating the negation returns us to the original statement.

Negation Introduction

If assuming a proposition Q leads to a contradiction (Q ∧ ¬Q for some statement Q), then the assumption is false. Formally: if ¬P ⊢ ⊥, then P holds. The symbol ⊥ denotes a logical falsehood.

Double Negation Elimination

In classical logic, ¬¬P is logically equivalent to P. This principle allows us to conclude P after we have shown that ¬P is impossible. Note: intuitionistic logic rejects this rule, limiting the scope of contradiction proofs in constructive mathematics.

Consistency Requirement

A consistent logical system cannot contain both a statement and its negation simultaneously. Once we derive both R and ¬R from an assumption, the assumption must be rejected. This is the engine that powers the entire technique.

✦ KEY TAKEAWAY

Think of proof by contradiction as a stress test for a hypothesis. In engineering, you might assume a bridge design can support a certain load, then analyze it until a structural failure emerges — proving the design is inadequate. Similarly, in mathematics you assume the opposite of what you want to prove, apply valid logical steps, and wait for the structure to collapse into a contradiction. The collapse itself constitutes the proof.

It is worth distinguishing proof by contradiction from proof by contrapositive. In a contrapositive proof of P → Q, one proves ¬Q → ¬P directly; no contradiction is derived. In contrast, a proof by contradiction assumes ¬P (or, if proving an implication P → Q, assumes P ∧ ¬Q) and derives a logical impossibility. Both are indirect methods, but the logical structure and the role of negation differ in important ways that affect proof strategy.

SECTION 3

Visual Explanation

The logical flow of a proof by contradiction can be visualized as a decision tree that inevitably terminates in impossibility. The following diagram traces the architecture of the method from the initial assumption through the derivation chain to the final conclusion.

The flowchart above illustrates the four-step architecture of a proof by contradiction. Beginning at the top with the goal statement P, the prover assumes ¬P (shown in violet), derives logical consequences using valid rules, arrives at a contradiction (pink), rejects the assumption (amber), and concludes that P is true (emerald).

Notice that the hardest creative work lies in Step 2 — choosing which consequences to derive and in what order. The structure of Steps 1, 3, and 4 is essentially formulaic. A well-crafted contradiction proof therefore combines a mechanical scaffolding (assume, derive, reject) with a substantive mathematical argument that produces two mutually exclusive conclusions from the same assumption.

SECTION 4

Logical Framework

Proof by contradiction is grounded in a small set of inference rules from classical propositional and predicate logic. Understanding the formal apparatus ensures that each step in a contradiction proof is airtight and that the technique is applied correctly in different contexts.

NEGATION INTRODUCTION (¬-INTRO)

If Γ, ¬P ⊢ ⊥ then Γ ⊢ P

Γ is the set of background assumptions (axioms, hypotheses). If adjoining ¬P to Γ allows the derivation of a contradiction ⊥, then P follows from Γ alone. The turnstile ⊢ means 'proves' or 'entails.'

DOUBLE NEGATION ELIMINATION

¬¬P ≡ P

In classical logic, negating a negation recovers the original proposition. This equivalence is what allows us to move from 'it is impossible that ¬P' to 'P is true.' This rule does not hold in intuitionistic logic.

CONTRADICTION FORM FOR IMPLICATIONS

To prove P → Q : assume P ∧ ¬Q, derive ⊥, conclude P → Q

When the target statement is a conditional, the contradiction assumption includes both the hypothesis P and the negation of the conclusion ¬Q. This gives the prover maximum raw material from which to derive a contradiction.

⚡ Proof by Contradiction vs. Proof by Contrapositive

To prove P → Q by contrapositive, one directly proves ¬Q → ¬P without seeking a contradiction. To prove P → Q by contradiction, one assumes P ∧ ¬Q and derives ⊥. A contrapositive proof is generally preferred when it is available because it avoids the indirect negation step, but contradiction is necessary when the statement to prove is not naturally an implication or when the negation yields useful structural information.

A critical point for formal correctness: the contradiction can take any form R ∧ ¬R. It does not need to involve the original proposition P directly. For instance, in Euclid's proof of the infinitude of primes, the contradiction is that a certain number is simultaneously prime and not prime — a statement about a constructed integer, not directly about the set of all primes. The prover's task is simply to arrive at any logically impossible conclusion under the assumption ¬P.

SECTION 5

Anatomy of a Classic Proof

To build intuition, let us dissect the most celebrated proof by contradiction in all of mathematics: the proof that √2 is irrational. This argument has been taught for over two millennia, and its structure exemplifies every principle discussed so far. The diagram below labels each logical move so you can see the contradiction machinery at work.

Each box in the diagram corresponds to a logical step. The violet box marks the negation assumption. The cyan boxes trace the algebraic derivation. The pink box highlights the contradiction, and the green box states the final conclusion.

Observe the parity argument at the heart of this proof: the key insight is that if a² is even then a itself must be even (since the square of an odd number is odd). This fact, applied twice, forces both a and b to share a factor of 2, directly contradicting the lowest-terms assumption. The elegance of the proof lies in how a simple number-theoretic observation about evenness produces the desired impossibility.

💡 Why Lowest Terms?

The assumption that a/b is in lowest terms (gcd(a, b) = 1) is crucial because it sets up the contradiction. Without this normalizing assumption, we could not obtain a meaningful impossibility from the fact that both a and b are even. This is a common technique in contradiction proofs involving fractions: always assume the fraction is fully reduced.

SECTION 6

Worked Example: Infinitely Many Primes

Let us work through Euclid's proof that there are infinitely many prime numbers. This is perhaps the most widely cited proof by contradiction, and it showcases how the method handles existential statements about infinite collections.

Theorem: There are infinitely many prime numbers.

Step 1 — State the negationAssume, for the sake of contradiction, that there are only finitely many prime numbers. Then we can list all of them as p₁, p₂, …, pₙ for some positive integer n.

Assumption: the complete list of primes is {p₁, p₂, …, pₙ}

Step 2 — Construct a new numberDefine the number N = p₁ × p₂ × … × pₙ + 1. That is, N is the product of all primes on our list, plus one. Since each pᵢ ≥ 2, the number N is strictly greater than every prime on the list.

N = p₁ · p₂ · … · pₙ + 1

Step 3 — Analyze divisibilityConsider any prime pᵢ from our list. Since N = (p₁ × p₂ × … × pₙ) + 1, dividing N by pᵢ gives a quotient with remainder 1. Therefore, no prime on the list divides N.

For all i: pᵢ ∤ N (pᵢ does not divide N)

Step 4 — Apply the Fundamental Theorem of ArithmeticBy the Fundamental Theorem of Arithmetic, every integer greater than 1 has at least one prime factor. So N must have a prime factor q. But q cannot be any of p₁, p₂, …, pₙ because none of them divides N. This means q is a prime not on our supposedly complete list.

∃ prime q such that q ∣ N and q ∉ {p₁, …, pₙ}

Step 5 — Identify the contradiction and concludeWe assumed that {p₁, …, pₙ} was the complete list of all primes, yet we have found a prime q that is not on the list. This is a contradiction: the list is both complete and incomplete. Therefore the original assumption — that there are finitely many primes — must be false.

∴ There are infinitely many prime numbers. ∎

⚠️ Common Misconception

A frequent error is claiming that N itself must be prime. This is not necessarily true — N might be composite. The key point is that N has a prime factor not on the list, whether that factor is N itself or some smaller prime. For example, if our list were {2, 3, 5}, then N = 31, which happens to be prime. But if our list were {2, 7, 11}, then N = 155 = 5 × 31, which is composite, and the new primes discovered are 5 and 31.

SECTION 7

Strengths, Limitations & Comparisons

Proof by contradiction is a versatile strategy, but like any tool it has situations where it excels and others where alternative approaches may be preferable. The table below compares it with the other major proof techniques encountered in a discrete mathematics course.

Comparison of major proof techniques in discrete mathematics

Technique	Strategy	Best Used When
Direct Proof	Assume P; derive Q step by step	The logical path from hypothesis to conclusion is clear and constructive
Proof by Contrapositive	Prove ¬Q → ¬P instead of P → Q	The negation of the conclusion provides a more useful starting point than the hypothesis itself
Proof by Contradiction	Assume ¬P (or P ∧ ¬Q); derive ⊥	Proving nonexistence, uniqueness, or irrationality; when the negation gives structural leverage
Proof by Induction	Prove base case; prove P(k) → P(k+1)	Statements indexed by natural numbers; recursive or sequential structures
Constructive Proof	Exhibit an explicit object satisfying the claim	Existential claims where a witness can be explicitly constructed

🎯 WHEN TO CHOOSE CONTRADICTION

Choose proof by contradiction when the statement involves negation, nonexistence, or uniqueness — situations where the negation provides more concrete objects to manipulate than the original claim. For example, 'there is no largest prime' becomes 'assume a finite list of all primes,' which gives you a specific, manipulable object. Conversely, if a direct proof is available and reasonably short, prefer it: direct proofs are typically easier to read, easier to verify, and provide constructive insight into why a statement is true, not merely that it is true.

A noted limitation of proof by contradiction is its non-constructive nature. A contradiction proof of an existential statement (∃x such that P(x)) demonstrates that the object exists without necessarily producing it. In computer science and constructive mathematics, this distinction matters: an algorithm requires a constructive witness, not merely the knowledge that a search cannot fail. Some mathematical communities (following the intuitionistic tradition of Brouwer and Heyting) accept only constructive proofs, making proof by contradiction unavailable as a general-purpose tool in those frameworks.

SECTION 8

Connections to Advanced Theory

Proof by contradiction is not merely a discrete math technique — it is a foundational method that scales into the most sophisticated areas of mathematics and theoretical computer science. Understanding its connections to advanced topics reveals why mastering this technique early is so valuable.

How foundational contradiction proofs connect to advanced mathematics

Foundational Concept	Advanced Extension	Role of Contradiction
Irrationality of √2	Transcendence theory (e − π conjectures, Lindemann–Weierstrass theorem)	Contradiction remains the primary method for proving numbers are irrational or transcendental
Infinitude of primes	Analytic number theory (Dirichlet's theorem on primes in arithmetic progressions)	Contradiction arguments generalize to show infinitely many primes satisfying given congruence conditions
Uncountability of ℝ	Set theory and cardinal arithmetic (continuum hypothesis, forcing)	Cantor's diagonal argument is a contradiction proof; diagonalization recurs throughout computability and set theory
Halting problem	Computability theory (Rice's theorem, undecidability results)	Self-referential contradiction (a program that halts iff it doesn't) is the key technique for proving undecidability

In model theory, the compactness theorem can be proved via contradiction: if a set of sentences has no model, then some finite subset must already be contradictory. In topology, many fundamental results — such as the Baire Category Theorem — use contradiction to establish that certain sets cannot be 'too small' in a topological sense. The technique's reach is essentially unbounded: wherever mathematical reasoning pushes against impossibility, proof by contradiction is likely to appear.

🔮 Looking Ahead: Constructive Alternatives

As you advance, you may encounter settings where proof by contradiction is restricted or unavailable — particularly in type theory and proof assistants (Coq, Lean, Agda). These systems often default to intuitionistic logic, requiring constructive proofs. Learning when a contradiction proof can be 'constructivized' and when it cannot is a rich area of modern logic.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

In a proof by contradiction, why is it essential that the logical system be consistent? What would go wrong if a system allowed both R and ¬R to be true simultaneously?

PROBLEM 2 — BASIC CALCULATION

Prove by contradiction: If n² is odd, then n is odd.

PROBLEM 3 — INTERMEDIATE

Prove by contradiction that √3 is irrational.

PROBLEM 4 — APPLIED

In a computer network with n nodes, prove by contradiction that if more than n − 1 pairs of nodes share the same password, then at least one node must use that password for at least two distinct connections. (Hint: model the network as a graph and consider the maximum number of edges in a tree.)

PROBLEM 5 — CRITICAL THINKING

Consider the following statement: 'There is no largest integer.' Write a rigorous proof by contradiction. Then reflect: could this statement also be proved directly (without contradiction)? If so, write a direct proof and compare the two approaches in terms of clarity and constructive content.

SUMMARY

Summary

Proof by contradiction (reductio ad absurdum) establishes the truth of a statement P by assuming ¬P and deriving a logical impossibility. The technique rests on the Law of Excluded Middle, negation introduction, and double negation elimination from classical propositional logic. The standard workflow is: (1) assume the negation, (2) derive logical consequences using axioms and known theorems, (3) arrive at a statement of the form R ∧ ¬R, and (4) conclude the original statement is true.

The method is especially powerful for proving nonexistence, irrationality, and infinitude results — contexts where the negation provides concrete objects to manipulate. Landmark examples include the irrationality of √2, the infinitude of primes, Cantor's uncountability theorem, and the undecidability of the halting problem. While proof by contradiction is non-constructive and unavailable in intuitionistic frameworks, it remains one of the most versatile and widely applied techniques in classical mathematics and computer science.