Proof by Cases — Mathematics Knowledge System

Overview

Proof by cases (also called proof by exhaustion or case analysis) establishes a statement P by splitting the situation into finitely many sub-situations C₁, C₂, ..., Cₙ that together cover every possibility, and then proving P separately within each case. The method rests on a simple disjunction: if C₁ ∨ C₂ ∨ ... ∨ Cₙ is guaranteed to hold (the cases are exhaustive), and P follows from each Cᵢ individually, then P follows overall — there is no gap between the cases for a counterexample to hide in. Two things must be checked with care: exhaustiveness (the cases really do cover every possibility, with no situation falling through the cracks) and validity within each case (the argument for P under Cᵢ must actually only use the assumption Cᵢ, not sneak in facts that hold elsewhere). The method is often the natural response when a direct or contrapositive argument would otherwise require juggling several unrelated sub-arguments at once, and it becomes proof by exhaustion in the extreme when the 'cases' are simply every element of a large but finite set, as in the 1976 computer-assisted proof of the four color theorem.

Intuition

Think of proof by cases as sorting mail into a fixed set of bins that you have proven, in advance, cover every possible piece of mail — no letter can fail to land in some bin. If you can show that whatever bin a letter ends up in, it always gets delivered correctly, then every letter gets delivered correctly, without you ever needing a single argument that works uniformly for all letters at once. A classic elementary example splits on parity: to prove a fact about 'any integer n', it is often enough to prove it separately assuming n is even and assuming n is odd, since every integer is one or the other and never both — those two cases exhaust ℤ.

Formal Definition

Definition

Given a goal P and sub-statements C₁, ..., Cₙ that are jointly exhaustive over the domain in question:

C_1 \lor C_2 \lor \cdots \lor C_n \quad \text{(the cases exhaust all possibilities)}

Exhaustiveness

(C_1 \implies P) \land (C_2 \implies P) \land \cdots \land (C_n \implies P)

P holds in every case

\left[ (C_1 \lor \cdots \lor C_n) \land \bigwedge_{i=1}^{n} (C_i \implies P) \right] \implies P

Proof-by-cases inference rule

Worked Examples

Every integer is either even or odd; these two cases are exhaustive.
$n \text{ even} \lor n \text{ odd}$
Case 1: n is even, so n = 2k. Then n² + n = 4k² + 2k = 2(2k² + k), which is even.
$n = 2k \implies n^2+n = 2(2k^2+k)$
Case 2: n is odd, so n = 2k+1. Then n² + n = (2k+1)² + (2k+1) = 4k²+6k+2 = 2(2k²+3k+1), which is even.
$n = 2k+1 \implies n^2+n = 2(2k^2+3k+1)$

Answer: In both exhaustive cases n² + n is even, so it is even for every integer n.

Practice Problems

Difficulty 2/10

Prove that for every integer n, n(n+1) is even, by casing on the parity of n.

Difficulty 3/10

Prove that max(a,b) + min(a,b) = a + b for all real numbers a, b, by cases on whether a ≥ b or a < b.

Difficulty 4/10

What is the difference between 'proof by cases' and 'proof by exhaustion', if any?

Quiz

Summary

Proof by cases splits the domain into exhaustive cases C₁, ..., Cₙ and proves the goal P separately within each one.
Validity requires both exhaustiveness (no situation is missed) and a correct argument for P inside every individual case.
Proof by exhaustion is the same technique taken to an extreme, checking every element of a large finite set one at a time, as in the four color theorem.

References

WebsiteWikipedia — Proof by exhaustion