Skip to main content

Counterexamples and Proof-Writing Discipline

What This Concept Is​

A counterexample to a universal claim $\forall x \in D,\ P(x) \rightarrow Q(x)$ is a specific element $x_0 \in D$ that satisfies the hypothesis $P(x_0)$ and violates the conclusion $Q(x_0)$. One such element disproves the whole claim; you do not need a second.

Proof-writing discipline is the habit of presenting an argument in a readable, auditable order: definitions used explicitly, hypotheses announced, method stated, steps numbered or connected by linking phrases, and the conclusion tied back to the original statement.

These two topics share a page because both require precision about exactly what the statement says. To find a counterexample you must read the statement correctly enough to know the hypothesis (which your candidate must satisfy) and the conclusion (which your candidate must violate). To write a proof well you must hold that same shape in your head as you work.

A crisp mental model: a counterexample is an element of the negation's witness set (see concept 4). That's why counterexample hunting is the same skill as quantifier negation. Mastering one trains the other.

A short vocabulary worth internalising:

  • Witness: a specific object that makes an existential claim true, or that makes the negation of a universal true.
  • Minimal counterexample: the smallest object (under some measure) that violates a claim. Used in proofs by contradiction on $\mathbb{N}$.
  • Cherry-picking: citing one supporting example as if it proved a universal; the dual mistake to thinking one counterexample is not enough.
  • Strong invariant: a claim chosen to be false only on exactly the configurations you want to rule out -- so "invariant failure" means "counterexample found."

Why It Matters Here​

In a proof-focused module, being able to disprove a statement is as important as proving a true one. Undergraduate exercise sets are full of plausible-sounding universal claims that are false; spotting them saves time. Mathematical maturity shows up as recognising the difference between "this is probably true" and "this has a small counterexample waiting in ${-1, 0, 1, 2}$."

Proof-writing discipline matters because mathematical prose is audited by other humans. A proof whose assumptions, definitions, and conclusion are locatable by eye can be verified in a few minutes. A proof that mixes scratchwork into the final output forces the reader to reconstruct the intent, and that cost scales with proof length.

Later semesters reward both habits heavily. Software specifications in Semester 4 are universal claims; bugs are counterexamples. Architecture review in Semester 7 is essentially a structured counterexample hunt against claimed invariants. Any engineering career lives in the gap between "true" and "probably true" -- you either generate counterexamples quickly or you live with production bugs.

Concrete Examples​

Example 1 -- a universal that collapses with a small witness.

Claim: "For all sets $A$ and $B$, if $A \cup B = A$ then $B = \emptyset$."

Counterexample: let $A = {1, 2}$ and $B = {1}$. Then $A \cup B = {1, 2} = A$ (the hypothesis is satisfied), but $B = {1} \ne \emptyset$ (the conclusion is violated). One witness is enough.

The correct deduction from $A \cup B = A$ is $B \subseteq A$, which is weaker than $B = \emptyset$. The counterexample points exactly at where the attempted stronger claim fails.

Example 2 -- a universal that cannot be counterexampled cheaply.

Claim: "For every integer $n$, $n^2 \ge n$ on $\mathbb{Z}_{\ge 0}$."

Searching for a counterexample is the first move. Try $n = 0$: $0 \ge 0$, ok. Try $n = 1$: $1 \ge 1$, ok. Try $n = 2$: $4 \ge 2$, ok. Every small case confirms the claim. At this point, searching harder is a worse use of time than trying to prove. The strategic signal: small-case testing that keeps confirming the claim is a prompt to switch from counterexample mode to proof mode.

Example 3 -- the degenerate-case instinct.

Claim: "For all functions $f : A \to B$, if $f$ is injective then $|A| \le |B|$."

Before proving, test degenerate cases: $A = \emptyset$. Any function from $\emptyset$ is vacuously injective; $|\emptyset| = 0 \le |B|$ for any $B$; no counterexample. Then $A = {a}$, $|B| = 0$: no functions exist from a nonempty set to $\emptyset$, so the hypothesis is vacuous, no counterexample. The degenerate cases do not break the claim, so the search shifts to proof.

Habit: always poke at $\emptyset$, one-element sets, constant functions, the identity -- these are the free cheap counterexample candidates and they often either break the claim or tighten your intuition about why it holds.

Example 4 -- a counterexample that fails to qualify.

Claim: "Every prime is odd."

A student proposes "$4$" as a counterexample. But $4$ is not prime, so it does not satisfy the hypothesis. Proposing a non-example of the hypothesis disproves nothing. The correct counterexample is $2$: it is prime (hypothesis satisfied) and it is not odd (conclusion violated).

The discipline: a counterexample must satisfy the hypothesis and violate the conclusion, both at once. Skipping either check leaves the argument defective.

Common Confusion / Misconceptions​

  1. "Any weird object counts as a counterexample." Only objects that satisfy the hypothesis are candidates. A counterexample to "if $x$ is prime then $x > 1$" cannot be $x = -7$ unless $-7$ is a prime in your definition.
  2. Confusing counterexample with lack of proof. Failing to find a proof is not the same as a counterexample existing. Fermat's Last Theorem went three centuries without a proof and without a counterexample.
  3. Mixing scratchwork with the final proof. Scratch explorations, abandoned sub-attempts, and figure-it-out-as-you-go narration all belong in your notebook, not in the submitted proof. The final proof is the successful path, told cleanly.
  4. Implicit definitions. A proof that never writes down "by definition, $f$ is injective iff …" silently asks the reader to trust that the student invoked the right definition. Writing the definition once, inline, makes the proof audit-able without pattern matching.

How To Use It​

For counterexamples:

  1. Read the statement and identify hypothesis and conclusion separately.
  2. Test small, canonical, or degenerate values first: $0$, $1$, $-1$, the empty set, the constant function.
  3. For each candidate: (a) verify the hypothesis holds, (b) verify the conclusion fails. Both checks are mandatory.
  4. If the first handful of candidates satisfy the claim, switch to proof mode and work forward.
  5. Present the counterexample as: "Let $x_0 = \ldots$. Then $P(x_0)$ because…; and $Q(x_0)$ fails because…."

For proof-writing discipline:

  1. Open with the target and the chosen method ("We prove $P \rightarrow Q$ by contrapositive.").
  2. State the working assumption ("Assume $\lnot Q$.") and any definitions you will unpack.
  3. Use one idea per sentence or per bullet; avoid run-on algebra.
  4. Mark iff direction changes, case changes, and contradiction assumptions explicitly.
  5. Close with a sentence that reconnects to the original theorem statement.
  6. Reread once; delete any line that does not move the argument toward the goal.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). A counterexample to an algorithm correctness claim is a bug input. Test-driven development is institutionalised counterexample hunting. Proof-writing discipline maps to code documentation: a well-commented algorithm is a proof in prose.
  • Semester 4 (systems). Fuzz testing is mass counterexample production. Invariant violations found by fuzzers correspond to hypothesis-satisfying, conclusion-violating witnesses.
  • Semester 6 (distributed systems). Model checkers enumerate reachable states seeking a counterexample to a safety claim; when they find one, they print a minimal execution trace that is a direct analogue of a minimal counterexample proof.
  • Semester 7 (architecture). Code-review comments often have the form "counterexample: what happens when X? In that case Y breaks." Architecture reviews specifically use counterexample hunting to audit ADR claims.

Check Yourself​

  1. What must a counterexample do to qualify? Why are both conditions (hypothesis satisfied, conclusion violated) necessary?
  2. Why is a proof harder to trust if definitions never appear explicitly? Give an example where the same calculation works in two different definitions.
  3. When should you stop hunting for a counterexample and switch to proof mode? What is the practical signal?
  4. Why is "I could not find a counterexample" not the same as "the claim is true"?
  5. How does proof-writing discipline interact with the other techniques in this cluster (direct, contrapositive, contradiction, cases, iff)?
  6. Rewrite a sloppy one-paragraph "proof" you wrote earlier in this course so the hypothesis, method, and conclusion are each locatable at a glance.

Mini Drill or Application​

Do each of the following:

  1. Give a counterexample to "every transitive relation is symmetric." State which pair of elements witnesses the failure and verify both hypothesis and conclusion conditions.
  2. Give a counterexample to "every injective function on $\mathbb{Z}$ is surjective." Choose a standard function and verify both conditions.
  3. Give a counterexample to "if $A \cap B = A \cap C$, then $B = C$." Give explicit small sets.
  4. For one of the following, decide whether it is true or false and either prove it or disprove it: "For every real $x$, $x^2 + 1 > 0$." / "For every integer $n$, $n^2 - n$ is divisible by $3$."
  5. Take a proof you wrote in the last week. Rewrite it so every assumption, every definition invoked, and the concluding sentence are visible on first reading.

Read This Only If Stuck​

Closing Note​

Counterexample hunting and clean proof writing are the twin habits that separate a student from a practitioner. Both are learned by practice, not by theory. Aim to produce one well-formatted proof per week and one found counterexample per week for the rest of this module, then the rest of Semester 1. By Semester 2 the skills become invisible infrastructure.