The Big Idea
Counterexamples and contradictions both expose failure, but they work in different ways.
A counterexample is an allowed case that makes a general claim false. It directly disproves the claim.
A proof by contradiction begins by assuming that the desired claim is false. If that assumption logically produces an impossibility, the assumption must be rejected and the original claim must be true.
Counterexamples attack a statement. Contradiction attacks the negation of a statement. Both depend on exact language, correct domains, and valid reasoning.
Two Different Logical Tools
| Feature | Counterexample | Proof by contradiction |
|---|---|---|
| Purpose | Disprove a universal or conditional claim | Prove a proposition |
| Starting move | Search the domain for a failing case | Assume the negation of the desired conclusion |
| Successful endpoint | One case that satisfies the conditions and violates the conclusion | An impossibility forced by the temporary assumption |
| Logical effect | Shows the original statement is false | Shows the assumed negation is false |
What Counts as a Counterexample?
Consider the claim:
\[ \text{For every real }x,\quad x^2\ge x. \]
The value \(x=\frac12\) is a counterexample because
\[ \left(\frac12\right)^2=\frac14\lt\frac12. \]
The example belongs to the real-number domain and makes the stated predicate false. That one case is enough to disprove the universal claim.
A counterexample is not merely an unusual example. It must satisfy every stated hypothesis while violating the conclusion.
Counterexamples to Conditional Claims
A universal conditional has the form
\[ \forall x\in D,\quad P(x)\to Q(x). \]
To disprove it, find an \(x\in D\) for which
\[ P(x)\land\neg Q(x) \]
is true. The hypothesis must succeed and the conclusion must fail.
For example:
\[ \text{If }n^2\gt25,\text{ then }n\gt5, \qquad n\in\mathbb{R}. \]
The value \(n=-6\) is a counterexample because \(36\gt25\) while \(-6\gt5\) is false.
What Does Not Count?
For the claim “If \(n^2\gt25\), then \(n\gt5\),” consider these attempted counterexamples:
| Value | Hypothesis | Conclusion | Counterexample? |
|---|---|---|---|
| \(n=-6\) | True | False | Yes |
| \(n=2\) | False | False | No; the hypothesis fails |
| \(n=7\) | True | True | No; it supports the claim |
| \(n=3i\) | Outside the real domain | Not applicable | No |
The checklist is strict: right domain, true hypothesis, false conclusion.
Quantifiers Explain the Power of One Example
The negation of a universal claim is existential:
\[ \neg\forall x\in D\,P(x) \quad\equiv\quad \exists x\in D\,\neg P(x). \]
Therefore, one counterexample disproves “every.” But one failing example does not disprove an existential claim. To disprove
\[ \exists x\in D\,P(x), \]
we must prove that every allowed object fails:
\[ \forall x\in D\,\neg P(x). \]
Quantifiers determine how much evidence is logically enough.
Counterexamples to Biconditionals
A biconditional contains two directions:
\[ P(x)\leftrightarrow Q(x) \quad\equiv\quad \bigl(P(x)\to Q(x)\bigr)\land\bigl(Q(x)\to P(x)\bigr). \]
To disprove it, break either direction:
- Find \(P(x)\land\neg Q(x)\), or
- find \(Q(x)\land\neg P(x)\).
The claim “An integer is divisible by \(4\) if and only if it is even” is false. The integer \(6\) is even but not divisible by \(4\), so the reverse direction fails.
Search Strategically for Counterexamples
Random testing can help, but targeted testing is usually faster. Try:
- the smallest and largest allowed values,
- zero, one, and negative values when permitted,
- boundary points where an inequality changes,
- objects with symmetry or degeneracy,
- cases that barely satisfy the hypothesis,
- cases excluded from familiar examples, and
- values that make a denominator, square root, or logarithm delicate.
Before calculating, negate the conclusion. This tells you exactly what kind of object to seek.
A Counterexample Can Improve a Conjecture
Suppose examples suggest:
\[ x^2\ge x\qquad\text{for every real }x. \]
The counterexample \(x=\frac12\) does more than say “wrong.” Solving
\[ x^2\ge x \quad\Longleftrightarrow\quad x(x-1)\ge0 \]
reveals the exact domain on which the inequality holds:
\[ x\le0\quad\text{or}\quad x\ge1. \]
A failed conjecture often contains the outline of a better theorem. The counterexample helps locate the missing condition.
What Is a Contradiction?
A contradiction is a proposition that cannot be true in the stated system. The clearest logical form is
\[ R\land\neg R. \]
Other forms include deriving \(0=1\), showing that one integer must be both even and odd, or violating an established theorem.
A surprising result is not automatically a contradiction. The endpoint must genuinely conflict with a definition, assumption, proved fact, or itself.
The Structure of Proof by Contradiction
In classical logic, to prove a proposition \(P\) by contradiction:
- Assume the negation \(\neg P\).
- Combine that assumption with definitions, hypotheses, and established results.
- Use valid deductive steps to derive a contradiction.
- Conclude that \(\neg P\) cannot hold.
- Therefore \(P\) is true.
Symbolically:
\[ \neg P\to\bot \qquad\therefore\qquad P, \]
where \(\bot\) represents contradiction or falsehood.
Proving a Conditional by Contradiction
To prove \(p\to q\), assume the one situation that would make the conditional false:
\[ p\land\neg q. \]
If this combination produces a contradiction, then no case can satisfy \(p\) while violating \(q\). Therefore \(p\to q\).
This is closely related to proving the contrapositive \(\neg q\to\neg p\). In a contrapositive proof, we start from \(\neg q\) and derive \(\neg p\). In a contradiction proof, we assume both \(p\) and \(\neg q\) and derive impossibility.
Worked Proof: \(\sqrt2\) Is Irrational
Claim. The real number \(\sqrt2\) cannot be written as a ratio of integers.
Assume for contradiction that \(\sqrt2\) is rational. Then
\[ \sqrt2=\frac{a}{b}, \]
where \(a,b\in\mathbb{Z}\), \(b\ne0\), and the fraction is in lowest terms. Squaring gives
\[ 2=\frac{a^2}{b^2} \qquad\Longrightarrow\qquad a^2=2b^2. \]
Thus \(a^2\) is even, which implies that \(a\) is even. Write \(a=2k\). Substituting,
\[ (2k)^2=2b^2 \qquad\Longrightarrow\qquad b^2=2k^2. \]
Therefore \(b^2\), and hence \(b\), is even. Both \(a\) and \(b\) are divisible by \(2\), contradicting the assumption that \(\frac ab\) was in lowest terms.
The rationality assumption leads to an impossibility. Therefore \(\sqrt2\) is irrational.
Why Does an Even Square Force an Even Integer?
The proof above uses the fact
\[ n^2\text{ even}\to n\text{ even}. \]
Its contrapositive is easy to verify. If \(n\) is odd, then \(n=2k+1\) for some integer \(k\), so
\[ n^2=(2k+1)^2=2(2k^2+2k)+1, \]
which is odd. Therefore an integer whose square is even cannot be odd; it must be even.
Naming supporting results keeps a contradiction proof from hiding important steps.
Contradiction Is Useful for Nonexistence and Uniqueness
Contradiction proofs are especially natural when a claim says that an object cannot exist or that two supposedly different objects must actually be the same.
To prove nonexistence, assume such an object exists and derive impossibility.
To prove uniqueness, suppose two objects \(x\) and \(y\) both satisfy the defining condition. Then show that assuming \(x\ne y\) leads to a contradiction, forcing \(x=y\).
This pattern appears in solutions to equations, inverse functions, optimization, geometry, and abstract algebra.
A Valid Contradiction Must Come from the Temporary Assumption
A proof fails if the contradiction comes from an unrelated mistake, an inconsistent hidden premise, or an invalid algebraic step.
Watch for:
- dividing by an expression that may equal zero,
- squaring or taking roots without tracking sign restrictions,
- assuming the desired conclusion somewhere in the argument,
- using a theorem outside its domain,
- calling a merely unexpected statement impossible, and
- starting from assumptions that were already inconsistent before the negation was added.
The contradiction must be a logical consequence of the temporary negation together with legitimate background facts.
Choose the Clearest Proof Route
Proof by contradiction is powerful, but it is not automatically the best method. A direct proof often explains more clearly why the conclusion holds.
| Situation | Promising approach |
|---|---|
| The hypotheses naturally transform into the conclusion | Direct proof |
| The negation has a useful concrete form | Contradiction or contrapositive |
| The claim says an object cannot exist | Contradiction |
| The claim says an object is unique | Assume two distinct candidates and derive contradiction |
| The claim is a universal statement suspected to be false | Search for a counterexample |
The goal is not to use the most dramatic method. It is to expose the logic with the fewest unnecessary turns.
Computation and Counterexample Search
A program can test many cases quickly, making computation excellent for discovering counterexamples. One verified output may completely disprove a universal conjecture.
Failure to find a counterexample is different. Searching a billion cases without finding one provides evidence but usually does not prove an infinite claim.
Computational results should also be checked against the exact domain, numerical precision, overflow, and implementation details. A software error is not a mathematical counterexample.
A Counterexample-and-Contradiction Routine
To test a universal claim
- State the domain and hypotheses.
- Negate the conclusion.
- Search for a case satisfying the hypotheses and the negated conclusion.
- Verify every condition explicitly.
- If a case works, state exactly which direction or clause it breaks.
To prove by contradiction
- Write the desired proposition clearly.
- Form its exact negation.
- Assume that negation temporarily.
- Derive consequences using only valid steps.
- Name the precise contradiction.
- Reject the negation and conclude the original proposition.
Common Confusions
Does an example that fails the hypothesis disprove a conditional?
No. A counterexample to \(p\to q\) must make \(p\) true and \(q\) false.
Can one failed example disprove an existential statement?
No. Other witnesses may exist. To disprove existence, show that every allowed object fails the predicate.
Is a surprising conclusion automatically a contradiction?
No. A contradiction must be logically impossible in the stated framework, such as \(R\land\neg R\) or a violation of an established fact.
Is proof by contrapositive the same as proof by contradiction?
They are related but structured differently. Contrapositive proof derives \(\neg p\) from \(\neg q\); contradiction assumes \(p\land\neg q\) and derives impossibility.
Does not finding a counterexample prove the statement?
Usually not over an infinite domain. It increases confidence but leaves untested cases unless a deductive argument covers them all.
Working Summary
A counterexample disproves a universal claim by satisfying its hypotheses and violating its conclusion. A proof by contradiction proves a proposition by showing that its negation forces an impossibility.
Quantifiers explain why one counterexample can defeat “every,” while domains determine whether a proposed case is allowed. Contradiction proofs require an exact negation, valid deductions, and a genuine impossibility. Used carefully, both tools reveal where a mathematical claim succeeds, fails, or needs refinement.
Check Your Understanding
Give a counterexample to “Every prime number is odd.”
The number \(2\) is prime and is not odd. It satisfies the subject condition and violates the claimed property.
Why is \(n=2\) not a counterexample to “If \(n^2\gt25\), then \(n\gt5\)”?
Because the hypothesis \(n^2\gt25\) is false when \(n=2\). A conditional counterexample must make the hypothesis true.
What should you assume to prove \(P\) by contradiction?
Assume \(\neg P\), then derive a genuine contradiction from that assumption and established facts.
What should you assume to prove \(p\to q\) by contradiction?
Assume the false case \(p\land\neg q\), then show that this combination is impossible.
What contradiction completes the proof that \(\sqrt2\) is irrational?
The assumed lowest-terms fraction \(\frac ab\) is forced to have both \(a\) and \(b\) even, so they share a factor of \(2\). That contradicts the lowest-terms assumption.