Learn · The Concrete Discrete Math of Real Systems

seedling

One Broken Case Ends “Always”

A single witness can destroy “always,” while contradiction can prove that the witness you seek cannot exist — two proof moves already hiding in every minimal bug report.

discrete-math, proof, counterexamples, contradiction, debugging, learn

Program testing can be used to show the presence of bugs, but never to show their absence.

— Edsger W. Dijkstra, “The Programming Task Considered as an Intellectual Challenge,” 1969

Chapter 2 computed the shape of failure: a universal claim is false when one counterexample exists. Here you will use that asymmetry deliberately, shrink a witness until it explains rather than merely surprises, prove an absence by contradiction, and distinguish disproof from the positive proof that Chapter 4 will supply.

The bug report that outweighs a test suite

“Sorting twice never changes the result.” A thousand generated arrays pass. Then one input fails:

records = [(name: "Ada", score: 7), (name: "Ada", score: 7)]
first sort  = [record 1, record 2]
second sort = [record 2, record 1]

If record identity matters, the claim is over. The thousand successes and the one failure do not vote. “For every input $x$ , sorting twice is unchanged” has the form $\forall x\,P(x)$ . Chapter 2 already computed its negation: $\exists x\,\neg P(x)$ . The failing array is that $x$ .

Commit to what the evidence licenses.

The counterexample law. To disprove $\forall x\,P(x)$ , it is enough to exhibit one admitted value $a$ and establish $\neg P(a)$ .

Assume $P(a)$ is false for an admitted $a$ . If $\forall x\,P(x)$ were true, then instantiating “every $x$” at $a$ would make $P(a)$ true. That contradicts the observed false value. Therefore the universal claim is false.

In plain English: “all” promises every case, so one case is entitled to collect the whole promise.

Shrink until the cause has nowhere to hide

A 40 MB crash input disproves a claim but teaches little. A six-byte input that preserves the crash often exposes the missing assumption. That is why fuzzers shrink and why good bug reports remove unrelated steps. The smallest witness is not logically stronger; it is explanatorily sharper.

The boundary matters. A byte sequence rejected by the public parser is not a counterexample to a claim about admitted documents. Before celebrating a witness, check that it inhabits the quantified domain. Many supposed impossibility results are only domain disagreements.

Counterexample — an object inside a universal claim's stated domain for which its predicate is false. Learn more.

Proving there is nothing to find

Counterexamples disprove universal claims. Sometimes the task points in the opposite direction: prove no object with certain properties exists.

Consider the claim that $\sqrt{2}$ cannot equal a fraction of integers. Suppose it can, and choose integers $p$ and $q$ with no common factor such that $\sqrt{2}=p/q$ . Squaring gives $p^2=2q^2$ , so $p^2$ is even. An odd integer has an odd square, hence $p$ is even; write $p=2k$ . Substitution gives $q^2=2k^2$ , so $q$ is even too. Then $p$ and $q$ share the factor 2, contradicting how they were chosen.

The supposed fraction manufactures an impossibility. Therefore no such fraction exists.

Proof by contradiction — assume the negation of the desired claim and derive two statements that cannot both hold. The assumption must then be false. Learn more.

If assuming $\neg P$ logically entails both $Q$ and $\neg Q$ , then $P$ is true.

Chapter 1's implication law says an implication is false only when its premise is true and conclusion false. If $\neg P$ entails a contradiction, there is no possible row on which $\neg P$ is true. Therefore $\neg P$ is false, so $P$ is true.

In plain English: follow the alternative all the way. If it requires the world to contain an impossibility, the alternative was never available.

Contradiction is not “I dislike the consequence.” The final pair must be formally incompatible: a number both even and odd, a strict order with $x<x$ , a minimal fraction whose numerator and denominator share a factor. Without the collision, the proof is only a story with a dark ending.

Contraposition is often the shorter road

To prove $P \to Q$ , you may instead prove its contrapositive $\neg Q \to \neg P$ . Chapter 1's truth table showed they forbid the same row. This often turns an awkward construction into a direct check.

“If $n^2$ is even, then $n$ is even” is easier backward. If $n$ is odd, write $n=2k+1$ . Then $n^2=4k^2+4k+1$ , which is odd. Therefore, by contraposition, an even square must have an even root.

Do not confuse this with the converse. Proving $Q \to P$ generally proves a different statement—the same reversal error the first chapter put on four rows.

Lessons

One admitted counterexample conclusively disproves a universal claim; successful tests do not prove it.
Shrinking preserves the verdict while removing places for the cause to hide.
Contradiction proves an absence by showing that the assumed object would force incompatible facts.
Contraposition proves the original implication because it forbids the same truth-table row; the converse does not.
A proof or disproof is only as honest as its stated domain.

Practice

Completion — choose the witness.

Discrimination — absence versus missing evidence.

Transfer — turn a specification into a bug report.

The asymmetry left behind

One case can take “always” away. It cannot give “always” back. Testing more cases never crosses that gap. To prove an unbounded family, we need a finite argument whose shape repeats with the family.

What kind of argument can turn one checked step into infinitely many?

References

Dijkstra. “The Programming Task Considered as an Intellectual Challenge.” EWD273, 1969. — the epigraph's primary source and the black-box-testing argument surrounding it
Euclid. “Elements, Book X.” Clark University edition, c. 300 BCE. — a classical proof of the irrationality of the square root of two
Demaine, Abel & Chapman. “Contradiction and Induction.” MIT OpenCourseWare, 2024. — a modern proof-method treatment with worked contradiction and induction arguments

Chapter 3 of The Concrete Discrete Math of Real Systems — counterexamples, minimal witnesses, contradiction, and contraposition as practical tools for proofs and debugging.