Mathematical Proof: Exhaustion and Disproof by Counter-Example
A statement that claims something is true "for all" cases in a set can be proved two different ways, and the set's size is what decides between them: if it can be listed, it is proved by checking every case there is; if it can't — infinite, or every real number in some range — it is proved instead by a general argument that holds for an arbitrary case without ever listing one. The same kind of statement can be disproved by a single case that fails, whatever the set's size. Three techniques, not one difficulty repeated three times — and which one applies is not a rule to memorise, it falls straight out of what the word "all" actually means.
The card
"For all n in S" = AND over every case in S. Proving it true needs every case covered — by checking each (exhaustion) or a general argument covering them all at once; disproving it needs one false case. Exhaustion (1.2): domain finite and bounded. List every case exactly, check each, state a conclusion — no separate mark for stating the bound itself. General proof / contradiction (1.1): domain infinite or continuous, claim to be PROVED. Rearrange to a form true for every case at once (e.g. a squared term ⩾ 0), or assume it false and derive a contradiction. Counter-example (1.3): claim to be DISPROVED, any domain size. Trial values, exhibit one failure with working shown, stop. Bounded claim → exhaustion. Unbounded/continuous claim to prove → general algebra or contradiction. Any claim to disprove → counter-example. Common losses: case list padded or short; conclusion omitted; product misread as sum; relation applied backwards; columns transposed; numerical examples treated as proof over an infinite domain; a divisibility claim asserted with no quotient shown.
Why it works — Why one counter-example is enough, and why exhaustion needs every case — the same fact, seen from both sides
A claim of the form " is true for every in some set " is not one statement — it is many statements joined together, one for each value of in : AND AND AND … , continuing for every element has. That is what "for every" or "for all" actually means: not a single claim about the set, but a claim about each member of it, all asserted at once. Two facts about AND now decide everything else in this topic. First, an AND is true only when every one of its parts is true — so if you want to prove the whole conjunction, there is no shortcut: you have to establish , and establish , and so on, for every single in . If is finite and small enough to write out, that is exactly proof by exhaustion — list every case, check each one, and the conjunction is proved because you have directly verified every part of it. If is infinite, exhaustion is not slower, it is impossible: there is no way to finish writing out infinitely many checks, which is exactly why the spec's own exhaustion example restricts and to "odd integers less than 7" rather than leaving the set open-ended. Second, and this is the asymmetry that makes disproof cheap: an AND is false the moment even one of its parts is false, regardless of how many other parts are true. AND AND is false if alone is false, whatever and turn out to be. So disproving " is true for every " needs exactly one failing case, exhibited and checked — not because mathematicians are being lenient, but because one false part is structurally sufficient to make the whole AND false. This is also why the spec's counter-example guidance example is allowed to leave unbounded — "for all values of " being an infinite conjunction is not a problem for disproof the way it is for proof, because disproof was never going to need to visit every part in the first place.
Traps — 9
- algebraic-proof-attempted-when-exhaustion-required
- The most-documented single error in this topic, confirmed independently in two separate series. October 2022: "a significant number of attempts... using logical or algebraic approaches. Such attempts were mixed in quality and often unnecessarily long-winded... Some who obtained a cubic expression for the product just concluded it was even without any justification." October 2023, on a different question: "an attempt at an algebraic solution which proved more demanding than that of a numerical one." When a claim is already restricted to a small, explicitly bounded set of cases, listing and checking them is both the method the spec names and — confirmed twice, independently — the faster and safer route.
- numerical-examples-mistaken-for-general-proof
- Confirmed as the single worst-performing question on its own paper: an October 2021 report on a "prove true for all positive x, y" question states "though only a third of candidates were able to score the first mark, there were many who attempted an algebraic proof... there was also a large number who considered that several numerical examples of the inequality holding constituted a proof" — 47% of candidates scored 0 out of 4. This is exhaustion's own logic reaching past where it applies: checking a handful of values and finding the claim true every time proves nothing about a domain with no last case to reach, however many values are checked. Only a general argument — one that holds for an arbitrary case, not a list of specific ones — closes an infinite or continuous domain; see the worked algebraic-proof example above for what that argument actually looks like.
- multiple-of-k-assertion-without-quotient-shown
- Confirmed on a real exhaustion question checking a "multiple of 4" claim — k > 2, so unlike "even" or "multiple of 5," the property is not visible by inspecting a last digit. The real mark scheme is explicit that a bare assertion does not earn the mark: "they can be divided by 4 (on its own) is insufficient without further clarification such as 'to give whole numbers'" (Oct 2023). What it does accept is a minimal but explicit marker that the division genuinely produces a whole number — a calculation such as "," a tick against each value, or the word "prove"/"QED" next to the working — anything that shows the check was actually done, not just declared. For a "multiple of 4" claim, write ", a whole number, so is a multiple of ," not " is divisible by " on its own; the marker cannot tell a genuine check from a guess unless the quotient — or an equivalent explicit clarification — is shown.
- product-misread-as-sum
- Confirmed directly: "the definition of 'product' is not widely understood, with many students considering the sum of a, b and c instead" (Oct 2022). This is not an arithmetic mistake inside an otherwise correct method — it is checking the wrong quantity against every single case, so a perfectly executed exhaustive list still proves nothing about the question actually asked. Read what operation the question names before setting up the check, not after.
- case-defining-relation-applied-backwards
- Confirmed on a real exhaustion question where the cases were generated from a stated relationship between the variables: "sometimes the result of using c = b − 2 instead of c = b + 2" (Oct 2022). A relation like "c is 2 more than b" has a direction; reversing it silently generates a different — and wrong — set of cases from the very first line, so every case checked afterwards is checked against the wrong list, however carefully the rest of the working is done.
- column-values-transposed-between-derived-variables
- Confirmed on the same well-answered exhaustion question as above, as a separate, less prominent cause of lost marks: "a mix up between columns b and c" (Oct 2023). This is not the relation being applied backwards and not an arithmetic slip — each value can be individually correct, but written under the other variable's column head, so the row no longer records the case it claims to. It shows up specifically when two columns are both derived from the same base variable rather than from each other (here b and c are both computed from a, not from one another) — nothing forces the two labels apart the way a stated relation would, so check each entry against its own column head after filling a row in, not only that the pair of numbers is right somewhere in the row.
- case-list-not-exactly-complete
- Confirmed as a specific, separately-documented cause of lost marks, distinct from getting a case wrong: "the addition of extra rows" (Oct 2023) costs marks in one direction, and the mechanism above shows why an incomplete list costs them in the other — a bounded set has an exact size, established in the very first step of the proof, and the finished list has to match it exactly, neither padded with cases outside the stated bound nor missing any inside it.
- conclusion-omitted
- Confirmed on a well-answered exhaustion question, where the cases themselves were rarely the problem: "the solution merely required the sight of three correct rows and a minimal conclusion. Reasons for a loss of marks were:... the omission of a conclusion" (Oct 2023). A completed, correct case list is not yet a finished proof — the sentence stating that every case has been checked and the claim therefore holds is not decoration, it is the step that turns the list into a proof.
- counter-example-search-continued-past-the-first-valid-one
- Confirmed on a real counter-example question: "most candidates understood the principle of finding a counter-example, although many found far more than necessary" (June 2019) — the same report that states the underlying rule directly: "only one counter-example is required to prove that a statement is not true." Once one failing case has been found and justified, the disproof is complete; continuing to search costs time without earning further credit.
Say it out loud
Out loud, from memory, no notes: explain why one counter-example is enough, and why exhaustion needs every case — the same fact, seen from both sides to someone who has never seen this topic — where does your explanation get vague or hand-wavy? That's the exact spot to re-study, and it only works if you check it: read back over the mechanism above the moment you finish talking and mark precisely where you drifted from it.