The Central Idea
Suppose a claim says
\[ \forall x\in S,\;P(x). \]To disprove it, we need one \(x\in S\) for which
\[ \neg P(x) \]is true.
Symbolically,
\[ \boxed{ \exists x\in S\text{ such that }\neg P(x) } \]is enough to refute
\[ \forall x\in S,\;P(x). \]One Counterexample Is Enough
A universal claim must survive every permitted case.
Therefore a single failure is decisive.
If someone claims
\[ \text{every integer is positive}, \]then
\[ -1 \]is enough to disprove the statement.
Why Counterexamples Work Logically
The negation of a universal statement is existential:
\[ \neg(\forall x\,P(x)) \Longleftrightarrow \exists x\,\neg P(x). \]A counterexample provides exactly that existential witness.
Thus counterexamples are not merely persuasive examples; they directly prove the negation of a universal claim.
A First Example
Claim:
\[ \text{Every prime number is odd.} \]Counterexample:
\[ 2. \]The number \(2\) is prime but not odd.
Therefore the universal claim is false.
The Counterexample Must Satisfy the Hypotheses
To refute
\[ P(x)\Longrightarrow Q(x), \]a counterexample must satisfy
\[ P(x) \]while failing
\[ Q(x). \]Thus a counterexample to a conditional statement has the form
\[ \boxed{P(x)\land\neg Q(x).} \]Example: A False Conditional
Claim:
\[ n\text{ is even}\Longrightarrow 4\mid n. \]Choose
\[ n=6. \]Then \(6\) is even, so the hypothesis is satisfied.
But
\[ 4\nmid6. \]Therefore \(6\) is a valid counterexample.
A Nonexample Is Not Necessarily a Counterexample
Suppose the claim is
\[ n\text{ even}\Longrightarrow n^2\text{ even}. \]Choosing
\[ n=3 \]does not refute the claim.
The hypothesis “\(n\) is even” is false.
Therefore \(3\) is outside the cases the theorem promises to cover.
Counterexamples to Equivalences
A biconditional
\[ P\Longleftrightarrow Q \]asserts both
\[ P\Longrightarrow Q \]and
\[ Q\Longrightarrow P. \]To disprove the biconditional, it is enough to disprove either direction.
Example: Divisibility Equivalence
Claim:
\[ 4\mid n \Longleftrightarrow 2\mid n. \]The forward direction is true:
\[ 4\mid n\Longrightarrow2\mid n. \]But the reverse direction fails.
Take
\[ n=6. \]Then
\[ 2\mid6 \]but
\[ 4\nmid6. \]Therefore the biconditional is false.
Counterexamples to Algebraic Claims
Algebraic identities are especially easy to test with carefully chosen values.
Consider the false claim
\[ (a+b)^2=a^2+b^2. \]Choose
\[ a=1,\qquad b=1. \]Then
\[ (1+1)^2=4, \]while
\[ 1^2+1^2=2. \]Since \(4\ne2\), the identity is false.
Counterexamples to Inequalities
Suppose someone claims
\[ x^2>x \]for every real number \(x\).
Choose
\[ x=\frac12. \]Then
\[ x^2=\frac14 \]and
\[ \frac14<\frac12. \]Therefore the claim is false.
Boundary Values Are Good Places to Search
False universal claims often fail at:
- \(0\);
- \(1\);
- \(-1\);
- small integers;
- endpoints;
- equality cases;
- empty sets;
- degenerate geometric configurations.
These values frequently expose assumptions hidden in informal reasoning.
Example: Zero Exposes a Hidden Assumption
Claim:
\[ \frac{x}{x}=1 \]for every real number \(x\).
At
\[ x=0, \]the expression
\[ \frac00 \]is undefined.
Thus the claim is not valid for every real number.
A correct version requires
\[ x\ne0. \]Counterexamples Reveal Missing Conditions
A good counterexample often suggests how to repair a false theorem.
If
\[ \frac{x}{x}=1 \]fails only at \(x=0\), then adding the restriction
\[ x\ne0 \]repairs the statement.
Counterexamples therefore help refine conjectures.
Counterexamples and Conjectures
A conjecture is a proposed statement believed to be true.
Before trying to prove it, test it against:
- small cases;
- boundary cases;
- negative values;
- zero;
- extreme values;
- structurally unusual examples.
One failure ends the search for a proof of the original statement.
Testing Is Not Proving
Suppose a claim holds for
\[ n=1,2,3,\ldots,1000. \]That does not prove it holds for every positive integer.
A universal statement requires a general proof.
Finite testing can increase confidence or discover counterexamples, but it cannot establish an unrestricted universal claim by itself.
Example: A Pattern That Eventually Fails
Consider
\[ f(n)=n^2+n+41. \]This expression produces prime values for many small nonnegative integers.
But at
\[ n=41, \]we obtain
\[ 41^2+41+41 = 41(41+2) = 41\cdot43, \]which is composite.
Therefore the formula does not always produce primes.
Counterexamples in Set Theory
Set identities and implications can also be disproved with small finite sets.
Small sets are useful because membership can be checked explicitly.
Example: False Set Equality
Claim:
\[ A\cup B=A\cap B \]for all sets \(A,B\).
Choose
\[ A=\{1\}, \qquad B=\{2\}. \]Then
\[ A\cup B=\{1,2\}, \]while
\[ A\cap B=\varnothing. \]Therefore the claimed equality is false.
Counterexamples in Function Theory
Suppose someone claims:
Every function from \(\mathbb R\) to \(\mathbb R\) is injective.
Consider
\[ f(x)=x^2. \]Then
\[ f(1)=1 \]and
\[ f(-1)=1. \]Since \(1\ne-1\), the function is not injective.
Therefore the universal claim is false.
Counterexamples in Graph Theory
Small graphs can refute overly broad graph claims.
Suppose someone claims:
Every connected graph is a tree.
A triangle graph is connected but contains a cycle.
Therefore it is not a tree.
The triangle is a counterexample.
Counterexamples in Geometry
Geometric statements may fail in special or limiting configurations.
Useful candidates include:
- right angles;
- isosceles cases;
- collinear points;
- degenerate triangles;
- parallel lines;
- coincident points.
Counterexamples with Negative Numbers
Claims discovered from positive examples often fail for negative inputs.
Consider:
\[ \sqrt{x^2}=x. \]Choose
\[ x=-3. \]Then
\[ \sqrt{(-3)^2} = \sqrt9 = 3 \]but
\[ x=-3. \]Therefore the correct identity is
\[ \sqrt{x^2}=|x|. \]Counterexamples with Fractions
Integer intuition may fail for rational or real numbers.
Suppose someone claims:
\[ x^2\ge x \]for every real number \(x\).
Choose
\[ x=\frac12. \]Then
\[ \frac14<\frac12. \]The claim fails.
Counterexamples with Empty Structures
Empty sets and empty collections can expose hidden nonemptiness assumptions.
If a theorem claims that every finite set has a maximum, the empty set is a counterexample unless the theorem specifies that the set is nonempty.
Therefore the correct theorem is:
\[ \boxed{\text{Every nonempty finite set of real numbers has a maximum}.} \]Counterexamples and Quantifiers
Counterexample strategy depends strongly on quantifier order.
To refute
\[ \forall x\,\exists y\,P(x,y), \]we must show
\[ \exists x\,\forall y\,\neg P(x,y). \]One input \(x\) must fail no matter which \(y\) is chosen.
Example: Quantifier Order Matters
Consider the claim:
\[ \forall x\in\mathbb R,\;\exists y\in\mathbb R\text{ such that }xy=1. \]Choose
\[ x=0. \]Then for every real \(y\),
\[ 0\cdot y=0\ne1. \]Thus \(x=0\) is a counterexample.
The corrected statement requires
\[ x\ne0. \]Counterexamples to “If and Only If” Claims
When testing
\[ P\Longleftrightarrow Q, \]search for:
- a case where \(P\) is true and \(Q\) is false;
- a case where \(Q\) is true and \(P\) is false.
Either one disproves the biconditional.
Counterexamples and Converse Statements
A theorem may be true while its converse is false.
Example:
\[ 4\mid n\Longrightarrow2\mid n \]is true.
The converse
\[ 2\mid n\Longrightarrow4\mid n \]is false.
The counterexample
\[ n=6 \]separates the two statements.
Counterexamples and Inverse Statements
The inverse of
\[ P\Longrightarrow Q \]is
\[ \neg P\Longrightarrow\neg Q. \]It need not be true.
Counterexamples help prevent accidental assumption that a theorem also proves its converse or inverse.
Counterexamples as Diagnostic Tools
A counterexample does more than say “false.”
It can reveal:
- a missing hypothesis;
- a domain restriction;
- a failed algebraic step;
- a boundary case;
- a mistaken converse;
- a hidden division by zero;
- a pattern that holds only in a smaller class.
Minimal Counterexamples Can Be Especially Informative
If many counterexamples exist, the smallest or simplest one is often the most useful.
A minimal counterexample may reveal the exact point where a pattern begins to fail.
This connects counterexample search with extremal reasoning.
Example: Smallest Counterexample to a Pattern
Suppose a conjecture holds for
\[ n=1,2,\ldots,20 \]but fails at \(n=21\).
The value \(21\) is a counterexample.
If no smaller failure exists, it is the minimal counterexample.
Studying that first failure may suggest how the theorem should be revised.
Counterexamples Generated by Computation
Computation can be useful for searching large finite ranges.
If a program finds a valid counterexample and the result can be independently verified, the universal statement is disproved.
But a long search that finds no counterexample does not by itself prove an infinite universal claim.
A Computer-Found Counterexample Still Needs Verification
If software reports that \(x\) is a counterexample, verify:
- \(x\) belongs to the theorem's domain;
- the hypotheses hold for \(x\);
- the conclusion fails;
- the computation itself was interpreted correctly.
Counterexamples versus Contradiction
A counterexample directly disproves a universal statement by producing a failing case.
Proof by contradiction assumes the negation of a desired claim and derives an impossibility.
The two methods can interact, but they are logically different.
Counterexamples versus Nonexamples
A nonexample is simply an object that does not fit a definition or category.
A counterexample specifically refutes a claim.
Every counterexample is relevant to a proposition.
A nonexample may have no proof-theoretic role at all.
Counterexamples versus Exceptions
An “exception” may refer informally to a case outside a stated rule.
In mathematics, if a theorem claims to cover that case, then the exception is actually a counterexample and the theorem is false.
A valid theorem must either exclude the case explicitly or prove that the case cannot occur.
How to Search Systematically
When testing a universal claim, try:
- the smallest admissible values;
- zero if allowed;
- negative values if allowed;
- fractions or irrational values if the domain permits them;
- boundary and equality cases;
- empty or singleton structures;
- highly symmetric cases;
- degenerate cases;
- objects where a denominator, factor, or condition becomes special.
Reverse-Engineer the Failure
For a conditional claim
\[ P(x)\Longrightarrow Q(x), \]search specifically for
\[ P(x)\land\neg Q(x). \]This is more efficient than testing arbitrary values.
Ask:
“What would an object look like if the hypothesis were true but the conclusion failed?”
Common Error: The Example Is Outside the Domain
If a theorem concerns positive integers, then
\[ -2 \]cannot serve as a counterexample.
A counterexample must belong to the stated domain.
Common Error: The Hypothesis Is False
To refute
\[ P\Longrightarrow Q, \]the example must satisfy \(P\).
If \(P\) is false, then the example does not test the promised cases.
Common Error: The Conclusion Still Holds
An example may satisfy the hypotheses but also satisfy the conclusion.
That example supports the claim but does not disprove it.
A valid counterexample requires
\[ \neg Q. \]Common Error: Several Examples Are Treated as Proof
Ten successful examples do not prove a universal claim.
One failing example disproves it.
This asymmetry is fundamental:
\[ \boxed{ \text{examples can refute universals, but finite examples cannot prove them}. } \]Common Error: A Numerical Approximation Is Mistaken for Failure
If two expressions produce close decimal values, numerical rounding may create the appearance of inequality.
Whenever possible, verify counterexamples exactly.
Exact arithmetic is especially important in identities and number-theoretic claims.
Common Error: Ignoring Hidden Restrictions
A candidate may seem to refute a theorem until all hypotheses are read carefully.
For example, a theorem about
\[ x>0 \]cannot be refuted with \(x=-1\).
Always check the complete statement.
Common Error: Calling a Counterexample a Proof of the Opposite Universal
If one example shows
\[ \neg P(x), \]then we know
\[ \exists x\,\neg P(x). \]We do not automatically know
\[ \forall x\,\neg P(x). \]One counterexample disproves a universal; it does not establish the opposite universal statement.
Common Error: Failing to State Why the Example Refutes the Claim
A clear counterexample argument should explicitly say:
- the example belongs to the domain;
- the hypotheses hold;
- the conclusion fails;
- therefore the universal claim is false.
A Reliable Procedure for Counterexample Proofs
- Write the universal or conditional claim precisely.
- Identify the domain.
- For a conditional, identify the hypothesis \(P\) and conclusion \(Q\).
- Search for an object satisfying \(P\land\neg Q\).
- Check small, boundary, zero, negative, fractional, or degenerate cases.
- Verify that the candidate belongs to the domain.
- Verify that every hypothesis holds.
- Show explicitly that the conclusion fails.
- Conclude that the universal statement is false.
- When useful, identify a corrected version of the theorem.
Example: Full Counterexample Workflow
Disprove:
\[ \forall x\in\mathbb R,\; \sqrt{x^2}=x. \]Step 1: Identify the domain.
The claim covers every real number.
Step 2: Search a vulnerable region.
Positive values satisfy the formula, so test a negative value.
Choose
\[ x=-2. \]Step 3: Evaluate both sides.
\[ \sqrt{x^2} = \sqrt{(-2)^2} = \sqrt4 = 2. \]But
\[ x=-2. \]Therefore,
\[ \sqrt{x^2}\ne x. \]Step 4: Conclude.
Since \(x=-2\) lies in the stated domain and the claimed equality fails, the universal statement is false.
The corrected identity is
\[ \boxed{\sqrt{x^2}=|x|}. \]Practice 1: Prime Numbers
Disprove:
\[ \text{Every prime number is odd.} \]Practice 2: Divisibility
Disprove:
\[ n\text{ even}\Longrightarrow4\mid n. \]Practice 3: Algebraic Identity
Disprove:
\[ (a+b)^2=a^2+b^2 \]for all real numbers \(a,b\).
Practice 4: Inequality
Disprove:
\[ x^2\ge x \]for every real number \(x\).
Practice 5: Square Root
Disprove:
\[ \sqrt{x^2}=x \]for every real number \(x\).
Practice 6: Set Identity
Disprove:
\[ A\cup B=A\cap B \]for all sets \(A,B\).
Practice 7: Function Claim
Disprove:
Every function \(f:\mathbb R\to\mathbb R\) is injective.
Practice 8: Quantifiers
Disprove:
\[ \forall x\in\mathbb R,\;\exists y\in\mathbb R \text{ such that }xy=1. \]Practice 9: Invalid Counterexample
A theorem concerns positive integers.
A student offers \(n=-3\) as a counterexample.
Explain the problem.
Practice 10: Conditional Counterexample
To refute
\[ P(x)\Longrightarrow Q(x), \]what two facts must a valid counterexample satisfy?
Practice Answers
Practice 1
Choose
\[ \boxed{2}. \]The number \(2\) is prime but even, so the universal claim is false.
Practice 2
Choose
\[ \boxed{n=6}. \]Then \(6\) is even, but
\[ 4\nmid6. \]Practice 3
Choose
\[ a=b=1. \]Then
\[ (1+1)^2=4, \]while
\[ 1^2+1^2=2. \]Practice 4
Choose
\[ x=\frac12. \]Then
\[ x^2=\frac14<\frac12=x. \]Practice 5
Choose
\[ x=-1. \]Then
\[ \sqrt{x^2}=1 \]while
\[ x=-1. \]Practice 6
Let
\[ A=\{1\}, \qquad B=\{2\}. \]Then
\[ A\cup B=\{1,2\}, \]but
\[ A\cap B=\varnothing. \]Practice 7
Choose
\[ f(x)=x^2. \]Since
\[ f(1)=f(-1)=1 \]with \(1\ne-1\), the function is not injective.
Practice 8
Choose
\[ x=0. \]Then for every real \(y\),
\[ xy=0\ne1. \]Therefore the universal-existential claim is false.
Practice 9
The candidate
\[ -3 \]does not belong to the stated domain of positive integers.
Therefore it cannot refute the theorem.
Practice 10
A valid counterexample must satisfy
\[ \boxed{P(x)} \]and
\[ \boxed{\neg Q(x)}. \]In other words, the hypothesis must hold while the conclusion fails.
What to Remember
A counterexample disproves a universal statement by exhibiting one valid failure:
\[ \boxed{ \neg(\forall x\,P(x)) \Longleftrightarrow \exists x\,\neg P(x). } \]- one valid counterexample is enough to disprove a universal claim;
- a counterexample to \(P\Rightarrow Q\) must satisfy \(P\land\neg Q\);
- the example must belong to the stated domain;
- small, boundary, zero, negative, fractional, empty, and degenerate cases are good places to search;
- counterexamples often reveal missing hypotheses or needed domain restrictions;
- finite testing can find counterexamples but cannot prove an unrestricted universal statement;
- a counterexample disproves a universal claim but does not prove the opposite universal claim;
- state explicitly why the candidate satisfies the hypotheses and violates the conclusion.
The strategic question is: If this statement were false, what is the simplest object that would satisfy all of its assumptions while making the conclusion fail?
Where We Go Next
Counterexamples complete this sequence of core discrete proof strategies. Together, direct proof, contrapositive reasoning, contradiction, induction, case analysis, invariants, pigeonhole reasoning, extremal arguments, existence proofs, and counterexamples form a practical proof toolbox for the discrete mathematics that follows.
The next section can build on these methods by applying them to increasingly structured discrete objects, counting arguments, graphs, algorithms, and stochastic reasoning.