1
Cases must be exhaustive
A proof by cases is valid only if the cases cover every possibility. They may overlap; they may not leave a gap.
Lesson · Logic and Proof · Proof
Cases, Counterexamples, and Writing a Proof
Split into cases that are exhaustive, or refute a universal claim with one counterexample. Then the summary of the whole course: what a proof owes its reader, and why checking cases is never enough.
cases cover EVERY possibility, prove the claim in each
counterexample ONE instance refutes ∀x P(x), completely
WLOG only when a genuine symmetry justifies it
checking n = 1..40 proves nothing about n = 41
The last three techniques
Core ideas
What this lesson establishes
Two more techniques, and then the standard everything on this path is held to.
2
One counterexample is a complete refutation
To disprove ∀x P(x) you exhibit a single x with ¬P(x). No further argument is needed or useful.
3
Verification is not proof
n² + n + 41 is prime for n = 0 through 39 and composite at 40. The lab lets you meet that personally.
The material
Cases, counterexamples, and the standard
Two techniques, then what separates a proof from a persuasive argument.
Proof by cases
Definition · Proof by cases
To prove s, find statements c₁, …, cₙ with c₁ ∨ … ∨ cₙ guaranteed true, and prove s under each cᵢ separately. The cases must be exhaustive; they need not be mutually exclusive.
Theorem · n² + n is even for every integer n
For all integers n, the number n² + n is even.
Every integer is even or odd, so these two cases are exhaustive.
Case 1: n is even. Then n = 2k, so n² + n = 4k² + 2k = 2(2k² + k), which is even.
Case 2: n is odd. Then n = 2k + 1, so n² + n = (4k² + 4k + 1) + (2k + 1) = 4k² + 6k + 2 = 2(2k² + 3k + 1), which is even.
In both cases n² + n is even, and the cases cover every integer.
□
A cleaner argument exists — n² + n = n(n + 1), a product of consecutive integers, one of which is even — and finding it is better mathematics. But the case proof is correct, and correctness comes first.
Without loss of generality is a legitimate abbreviation for a case argument, and only when a genuine symmetry makes the remaining cases identical. If proving one case and the other requires different arguments, WLOG is being used to hide a gap.
Disproof by counterexample
Definition · Counterexample
A counterexample to ∀x P(x) is an element c of the domain with ¬P(c). Exhibiting one disproves the statement completely.
This follows directly from “Negating Quantified Statements”: ¬∀x P(x) ≡ ∃x ¬P(x), and an existential is proved by producing a witness. It is why negating a claim before attacking it is worth the two minutes — the negation describes exactly what you are hunting for.
Example · Refuting a plausible claim
"Every positive integer is the sum of at most three squares" is false: 7 requires four (4 + 1 + 1 + 1). One number settles it. The corrected statement — every positive integer is the sum of at most four squares — is Lagrange's theorem, and needs a real proof.
Why checking is not proving
This is the point the whole course has been building toward, and Induction and Recursion exists because of it.
Theorem · Two statements that survive dozens of checks and are false
n² + n + 41 is prime for every n from 0 to 39, and composite at n = 40, where it equals 1681 = 41². And n points on a circle with all chords drawn divide it into 1, 2, 4, 8, 16 regions for n = 1 to 5 — and 31, not 32, at n = 6.
Both are in the lab on this page. Meeting them is more useful than being told about them: the second in particular gives five consecutive powers of two, which is exactly the kind of evidence that feels conclusive and is not.
What a proof owes its reader
- A precise statement. Quantifiers, domain, hypotheses. An imprecise claim cannot be proved or refuted.
- A declared method. "We prove the contrapositive", "suppose for contradiction", "there are two cases". The reader should know the shape before the details.
- Justified steps. Every line follows from a definition, a hypothesis, or a result already established.
- No gaps disguised as brevity. "Clearly" and "it is obvious that" are where errors hide. If it is clear, the reason is short — write it.
- An explicit ending. State what has been proved.
A proof is a social object as much as a logical one: its purpose is to convince a careful, skeptical reader who does not already believe the claim. Everything in “Direct Proof”, “Contraposition and Contradiction” and “Cases, Counterexamples, and Writing a Proof” serves that purpose.
Interactive
Check P(n), then notice checking is not proving
Two of these statements are false
Method
Cases and counterexamples
Coverage for cases; a single instance for a counterexample.
1
Check the cases are exhaustive
State why they cover everything: every integer is even or odd, every real is negative, zero or positive. A gap invalidates the whole proof.
2
Prove the claim in each case separately
Each case is its own small proof and gets the full treatment. Sharing an argument across cases without saying so is where errors enter.
3
Use WLOG only for genuine symmetry
State the symmetry: "by symmetry in x and y, assume x ≤ y". If you cannot state it, do the other case.
4
To disprove, produce the witness
Negate the claim to learn what the counterexample must satisfy, then find one and verify it explicitly. Verification is not optional.
Cases and counterexamples
Score 0 / 0Choose the answer you can justify.
Prove |x + y| ≤ |x| + |y| for all reals
The triangle inequality, by cases on the sign of x + y.
Case 1: x + y ≥ 0.
|x + y| = x + y ≤ |x| + |y|,
since x ≤ |x| and y ≤ |y| always hold.
Case 2: x + y < 0.
|x + y| = −(x + y) = (−x) + (−y) ≤ |x| + |y|,
since −x ≤ |x| and −y ≤ |y| always hold.
Every real number is ≥ 0 or < 0, so the cases are exhaustive. ∎
The two cases are near-mirrors, which invites a WLOG. It would not be legitimate here: the symmetry is between x + y ≥ 0 and x + y < 0, not between x and y, and the second case genuinely uses −x ≤ |x| rather than x ≤ |x|. Writing both is two extra lines and removes all doubt.
Common mistakes
1
Cases with a gap"Positive or negative" omits zero; "greater than or less than" omits equality. State why the cases cover everything, every time.
2
Using WLOG where there is no symmetryIt is the most common way a real gap gets past a reader, because it reads like rigour. If the other case needs a different argument, write it.
3
Offering many examples in place of a proofTwenty confirming instances and zero counterexamples is not weak evidence for a universal claim — it is not evidence of the right kind at all. Induction and Recursion supplies what is.
Check your understanding
✓
Finish when you can state, for any claim, what would refute it, and prove one claim by cases.
That single habit — asking what a counterexample would look like before trying to prove anything — is what this course was for. It tells you whether to hunt for a proof or for a counterexample, and it is the mechanical negation of “Negating Quantified Statements” put to work. Then prove the claim “Direct Proof”'s lab showed you: for every integer n, n³ − n is divisible by 3. Write n³ − n = (n − 1) n (n + 1), split into n = 3k, n = 3k + 1 and n = 3k + 2, and say in each case which factor is the multiple of 3. Divisibility by 6 adds the parity of this lesson's theorem and a fact about 2 and 3 that Number Theory and Cryptography proves.
Note: Induction and Recursion supplies the technique this lesson leaves missing: induction proves a statement for every natural number by proving one implication rather than infinitely many cases. It is the answer to "checking is not proving", and it is two courses away.