Disproof and Counterexamples

Counterexample-hunting is a working tool across mathematics and beyond. In analysis and topology, entire reference books catalogue spaces and functions built purely to violate one plausible-sounding universal claim, from non-metrizable topological spaces to nowhere-differentiable continuous functions; these serve as the field's stress tests for which hypotheses are truly necessary in theorems. In algebra, counterexamples separate classes of structures — a ring that is not an integral domain, a group that is not abelian, a matrix that is invertible over $\mathbb{Q}$ but not over $\mathbb{Z}$ — clarifying exactly which implications hold and which need extra hypotheses. In computer science, model checkers and automated theorem provers search state spaces specifically for counterexamples to safety properties expressed as universal statements over program states; a single found counterexample (a "witness trace") is treated as a complete disproof of correctness, exactly mirroring the logical criterion here. In cryptography, breaking a claimed security property often means exhibiting one attack — one adversary strategy that violates the universal "for all adversaries, the scheme resists forgery" claim — and that single strategy suffices to invalidate the security proof. In statistics and the philosophy of science, Popper's falsifiability criterion, directly modeled on mathematical counterexamples, shapes how empirical universal claims are tested against data. Finally, in combinatorics and graph theory, conjectures are routinely tested computationally against small cases precisely because a single small counterexample (a specific graph, a specific coloring) can end a decades-old conjecture, as happened historically with several Euler-type and Ramsey-type conjectures.

:::quiz[A student wants to disprove $\forall f\,(f\text{ differentiable} \to f\text{ has a maximum})$ over $D=\{$functions on $[0,1]\}$ using $f(x)=x$. Is this valid?]

• Yes, since $f(x)=x$ is differentiable and has no maximum on $[0,1)$ but the domain here is closed $[0,1]$, so check the actual max
• Invalid as stated, since $f(x)=x$ on the closed interval $[0,1]$ attains a maximum at $x=1$, so $Q(f)$ is true and it is not a counterexample ✓
• Valid, since $f$ is a straight line and lines never have maxima
• Invalid, since $f(x)=x$ is not differentiable

Ask the tutor: Can you give me a universal statement with three quantifiers and walk me through exactly what a valid counterexample to it would need to establish?

A universal claim "$\forall x \in D\, P(x)$" is a claim about every element of a domain, potentially infinite. To prove it directly you typically need a general argument covering all cases at once — an argument that works no matter which $x$ someone hands you. But to show the claim is false, the logical burden collapses: you do not need to say anything about most of $D$. You need exactly one element, checked concretely, where $P$ fails. This asymmetry is the heart of the matter, and it comes directly from the semantics of negation applied to quantifiers, which you have already seen: $\lnot \forall x\, P(x)$ is logically equivalent to $\exists x\, \lnot P(x)$. A disproof of a $\forall$-statement is a proof of an $\exists$-statement, and proofs of $\exists$-statements are, by their nature, allowed to be "constructive point-checks" — produce the witness, check the property, done. No sweeping argument about the whole domain is required, which is why counterexamples are often much shorter than the proofs of the theorems they refute. The subtlety enters once statements have more than one quantifier, or hide a quantifier inside an implication. "Every differentiable function is continuous" is true; "every continuous function is differentiable" is false, and the classic witness $f(x) = |x|$ works because it satisfies the hypothesis (continuous at $0$) while violating the conclusion (not differentiable at $0$). Get the direction of the implication backwards and you'll go hunting for the wrong kind of example forever. With nested quantifiers such as $\forall x\, \exists y\, R(x,y)$, the negation $\exists x\, \forall y\, \lnot R(x,y)$ demands an $x$ that defeats every candidate $y$ — a strictly stronger task than defeating a single-quantifier claim, and one that requires its own short universal argument over $y$, even though the outer structure is existential.

Example 1 — a claim about integers, asymmetric and multi-step. Claim to test: "For every integer $n$, if $n^2 - n + 41$ is prime for $n = 0, 1, \dots, k$, then $n^2 - n + 41$ is prime for all positive integers $n$." Rather than test this vague meta-claim, let's test the cleaner and historically famous statement it alludes to:

This has fooled people because it is true for $n = 1, 2, \dots, 40$ (Euler's polynomial). By the Counterexample Criterion, to disprove the universal claim we need exactly one positive integer $a$ for which $a^2 - a + 41$ is not prime — we owe no explanation of the other $39$ successes. Take $a = 41$. Compute:

Since $1681$ has $41$ as a proper divisor with $1 < 41 < 1681$, $1681$ is composite, not prime. Thus $P(41)$ — "$41^2-41+41$ is prime" — is false, so $a = 41 \in \mathbb{Z}^+$ is a counterexample. By the Counterexample Criterion, $\forall n \in \mathbb{Z}^+\,(n^2-n+41 \text{ is prime})$ is false. Notice we did not need to explain why the pattern holds for $n \le 40$; the single failure at $n=41$ is a complete, self-contained refutation. (In fact $a=40$ already works, since $40^2-40+41 = 1601$ is prime — wait, check: we want a failure, and $40$ still gives a prime; the point is that $41$ is the first failure, and finding the first failure is not logically necessary, only convenient. Any single failing $n$ would do.)

Example 2 — a claim about real functions, testing an implication. Claim to test:

where the domain $D = C(\mathbb{R})$ is the set of real-valued functions on $\mathbb{R}$, $P(f)$ is "$f$ is continuous on $\mathbb{R}$," and $Q(f)$ is "$f$ is differentiable on $\mathbb{R}$." By the Corollary above, a counterexample is a function $a=f \in D$ with $P(f)$ true (continuous) and $Q(f)$ false (not differentiable somewhere). Let $f(x) = |x|$. We must verify both halves rigorously. Continuity of $f$ at every $x_0 \in \mathbb{R}$: Given $\varepsilon > 0$, choose $\delta = \varepsilon$. For $|x - x_0| < \delta$, the reverse triangle inequality gives

So $f$ is continuous at every $x_0$, hence continuous on $\mathbb{R}$; $P(f)$ holds. Failure of differentiability at $x_0 = 0$: Consider the difference quotient

The right-hand limit as $h \to 0^+$ is $1$, and the left-hand limit as $h \to 0^-$ is $-1$. Since these one-sided limits disagree ($1 \ne -1$), the two-sided limit $\lim_{h\to 0} \frac{f(h)-f(0)}{h}$ does not exist, so $f$ is not differentiable at $0$. Hence $Q(f)$ is false. So $f(x)=|x|$ satisfies $P(f) \land \lnot Q(f)$, exactly the criterion of the Corollary. Therefore

is false — continuity does not imply differentiability. Again, note the asymmetry with Example 1: here the counterexample must satisfy two conditions (hold the hypothesis, break the conclusion), and both had to be separately proved, with $\varepsilon$–$\delta$ work on one side and a one-sided-limit computation on the other. A function that merely failed to be differentiable, without first being shown continuous, would not refute the implication — it might simply fail to be a legitimate test case if it also failed continuity (in which case $P(f)$ is false and $P(f) \to Q(f)$ is automatically true, vacuously, for that $f$).