Skip to content

Proof by Counterexample

Refutation method — instantiates Computability Boundary Mapping

Refutes an over-broad universal claim — that some method handles an entire class — by exhibiting one well-formed instance on which it demonstrably fails.

Much of the trouble the boundary map guards against comes from claims that quietly over-reach: "our checker catches every case," "this holds for all inputs," "the algorithm is correct." Proof by Counterexample attacks exactly that shape of claim, and only that shape. Its defining move is asymmetry: a single well-formed instance on which the universal claim fails refutes it completely, while no number of passing instances would prove it — so the mechanism is a decisive destroyer of over-broad claims and a producer of nothing positive. It does not build a procedure or settle a class; it puts one crisp instance on the table and forces the claim to retreat to where it actually holds.

Example

For roughly two centuries Euler's conjecture held that no n-th power is a sum of fewer than n smaller n-th powers. It was a clean universal — until a single counterexample appeared: 27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵, four fifth powers summing to a fifth power. That one identity, checkable by hand, ended the conjecture. It proved nothing about which larger claim might be true in its place; it simply demonstrated that the universal, as stated, was false and had to be narrowed. The whole force of the refutation lived in one valid, in-scope instance.

How it works

The mechanism does not search a space or build a general argument; it exhibits one instance and demonstrates the claim fails on it. Its entire burden is that the instance is legitimate: well-formed under the problem's own encoding, and genuinely inside the scope the claim asserts — an out-of-scope instance refutes nothing. A single verified failure is complete; there is no need to enumerate further, which is what makes counterexampling cheap relative to proving the positive. The payoff is not a theorem but a relocated boundary: the claim's scope must shrink to exclude the region the counterexample exposed.

Tuning parameters

  • Search strategy — where to look for the breaking instance: targeted at a suspected weak spot, random, or aimed at boundary and edge cases. Edge cases are where over-broad claims most often crack.
  • Minimality — whether to report the first counterexample found or hunt for the smallest. A minimal counterexample localizes why the claim fails and is easier to reason about.
  • Validity bar — how strictly the instance must satisfy the claim's stated preconditions. Loosening it produces cheap but illegitimate "refutations" that a defender rightly rejects.

When it helps, and when it misleads

Its strength is decisive economy: one instance retires an over-broad claim and honestly redraws the scope boundary, which is precisely the correction the archetype needs when a team has mistaken a restricted result for a universal one. Its failure mode is the inverse fallacy — treating the absence of a counterexample as proof of the claim; searching and finding none means only that you did not find one, never that the universal is true. A counterexample that violates the claim's real preconditions is a second trap: it refutes a strawman, not the actual claim. The discipline is falsifiability[^falsify]: a universal can be refuted by one instance but never confirmed by finitely many, so counterexampling settles the negative direction only and must be paired with a constructive or impossibility proof for the positive.

How it implements the components

  • quantifier_and_scope_map — it operates directly on the universal quantifier of the claim, supplying the existential witness (∃ an instance where it fails) that negates the asserted ∀.
  • scope_boundary — a valid counterexample relocates the scope boundary, forcing the claim to be narrowed to the region where it genuinely holds.

It refutes a specific claim but never certifies a whole class impossible — that class-level impossibility is Diagonalization Impossibility Proof's certificate — nor does it build the positive procedure, which is Constructive Algorithm and Correctness Proof's.

References

Falsifiability (Popper) — a universal claim can be decisively refuted by a single counterexample but never conclusively verified by any finite number of confirming instances. This asymmetry is the whole leverage of the method.