One Failure Can Settle a Universal Claim
The previous tutorial distinguished proofs that exhibit a witness from proofs that establish existence without identifying one. A counterexample is an especially important kind of witness: it is an object that demonstrates that a proposed universal claim is false. Instead of trying to check every possible input, we find one permitted input at which the claim fails.
Let \(D\) be a domain and \(P(x)\) a condition on elements of \(D\). The universal claim \(\forall x\in D,\ P(x)\) says that \(P(x)\) holds for every element of the domain. A counterexample to this claim is an element \(c\in D\) for which \(P(c)\) is false. Equivalently, it is an element \(c\in D\) satisfying \(\neg P(c)\).
The requirement \(c\in D\) matters. If the claim is about integers, a real number that is not an integer cannot refute it, even if the property fails at that real number. The property must also fail at the chosen input: an unusual-looking value is not a counterexample if it still satisfies the claim.
The logical relationship is given by the Negation of a Universal Statement, established earlier in Negating Universal Statements: the negation of “for every \(x\in D\), \(P(x)\)” is “there exists \(x\in D\) such that \(P(x)\) is false.” Finding a counterexample is therefore an existence task. We need only produce one valid witness to the failure.
This is different from trying several inputs and observing that the claim works for them. A handful of successful tests can increase confidence or suggest a pattern, but a universal statement includes every element of its domain. To disprove it, one failure suffices; to prove it, checking a few cases usually does not.
How to Search for a Counterexample
A useful search begins by translating the claim into the conditions a failure must satisfy. For a statement of the form \(\forall x\in D,\ P(x)\), ask what \(x\) would have to do for \(P(x)\) to be false. If the property is an inequality, reverse the inequality or examine equality cases. If the statement is conditional, a failure requires the hypothesis to hold while the conclusion fails; an input where the hypothesis is false is not a counterexample.
After translating the desired failure, look for inputs where the expression becomes simple or where a familiar pattern is stressed. Zero, one, negative values, fractions between zero and one, equal inputs, and inputs with opposite signs are often useful when the domain permits them. These are starting points, not a checklist that guarantees success. The candidate must still be tested against the exact claim.
Identify the domain and the property asserted for every permitted input.
Negate the property. For a conditional, require its hypothesis to be true and its conclusion to be false.
Try values that make the relevant expressions easy to calculate or expose a boundary, sign, or equality issue.
Verify that the candidate is allowed and calculate explicitly that the property does not hold there.
Conclude that the universal assertion is false. Do not claim more than the counterexample establishes.
Worked Example: A False Inequality on the Real Numbers
Claim to test. For every real number \(x\), \(x^2\geq x\).
To make the inequality fail, we need \(x^2<x\). The number \(x=\frac12\) is real, so it belongs to the domain. At this value, $$ x^2=\left(\frac12\right)^2=\frac14<\frac12=x. $$ Thus the proposed inequality fails at \(x=\frac12\). This is a counterexample, and the universal claim is false.
The choice is more informative than, for example, testing \(x=2\), where \(4\geq2\) holds. It is not necessary to determine every real number for which the inequality fails. A single verified failure settles the question of whether the inequality holds for all real numbers.
Counterexamples to Conditional Claims
A universal claim often has a conditional form: “For every \(x\in D\), if \(A(x)\), then \(B(x)\).” To refute it, it is not enough to find an input for which \(B(x)\) is false. We must also have \(A(x)\) true. If the hypothesis is false, the conditional is true at that input under the standard meaning of implication, so that input does not expose a failure.
The negation of an implication, established in Negating a Mathematical Statement, requires its hypothesis and the failure of its conclusion. Thus the counterexample conditions are $$ c\in D,\qquad A(c)\text{ is true},\qquad B(c)\text{ is false}. $$ This compact checklist prevents a common error: choosing a value that violates the conclusion but does not satisfy the stated hypothesis.
Worked Example: Checking the Hypothesis Before the Conclusion
Claim to test. For every real number \(x\), if \(x>0\), then \(x^2>x\).
The hypothesis is \(x>0\), and the conclusion is \(x^2>x\). Choose \(x=\frac12\). First, the hypothesis holds because \(\frac12>0\). But $$ x^2=\frac14<\frac12=x, $$ so the conclusion \(x^2>x\) is false. The candidate is real, satisfies the hypothesis, and makes the conclusion fail. Therefore it is a counterexample to the universally quantified conditional.
By contrast, \(x=-1\) would not be a counterexample to this claim. Although the conclusion \(x^2>x\) is false there, the hypothesis \(x>0\) is also false. The conditional does not fail at that input. A counterexample must meet both parts of the test.
Worked Example: Refuting a Proposed Equality
Claim to test. For all real numbers \(a\) and \(b\), $$ |a+b|=|a|+|b|. $$
Choose \(a=2\) and \(b=-2\). Both are real, so the pair is in the stated domain \(\mathbb R^2\). The two sides evaluate to $$ |a+b|=|2+(-2)|=|0|=0 $$ and $$ |a|+|b|=|2|+|-2|=2+2=4. $$ Since \(0\ne4\), the equality fails for this pair. Thus \((2,-2)\) is a counterexample to the claim.
This does not contradict the Triangle Inequality established earlier: that result says \(|a+b|\leq |a|+|b|\), not that equality always holds. The counterexample helps distinguish a true inequality from a stronger equality claim that is false.
Two Useful Limits on What Examples Show
A counterexample has a precise but limited force. It disproves the particular universal assertion that it violates. It does not automatically prove that the opposite statement holds for every input. For instance, finding one \(x\) with \(x^2<x\) shows that \(x^2\geq x\) is not true for all real \(x\); it does not show that \(x^2<x\) for all real \(x\). A claim and its negation may both fail to be universal.
The opposite caution is just as important. If several carefully chosen inputs all satisfy a proposed rule, those checks do not prove it for an infinite domain. They may help discover a conjecture, test a calculation, or suggest how a proof might work. A proof still needs an argument that covers every permitted input, such as the direct-proof and proof-by-cases methods developed earlier in this course.
When the domain has only finitely many elements, however, checking every input does prove a universal claim. This provides a useful contrast with infinite domains.
Checking Every Input in a Finite Domain
If \(D\) consists of exactly the distinct elements \(d_1,d_2,\ldots,d_n\), then the universal statement \(\forall x\in D,\ P(x)\) is true exactly when every one of the finite list of statements \(P(d_1),P(d_2),\ldots,P(d_n)\) is true. In this setting, exhaustive checking is possible: there are no untested elements left in the domain.
Proof. Suppose first that \(\forall x\in D,\ P(x)\). Each \(d_i\) belongs to \(D\), so the universal statement gives \(P(d_i)\) for every index \(i\) from \(1\) through \(n\). Therefore all the listed propositions hold, and their conjunction is true.
Conversely, suppose \(P(d_1),P(d_2),\ldots,P(d_n)\) all hold. Let \(x\in D\) be arbitrary. Since the displayed list contains every element of \(D\), \(x=d_i\) for some index \(i\). The corresponding statement \(P(d_i)\) is true, so \(P(x)\) is true. Because \(x\) was arbitrary in \(D\), \(\forall x\in D,\ P(x)\). Both implications are established, proving the equivalence.
Worked Example: Exhaustively Checking a Three-Element Domain
Let \(D=\{-2,0,3\}\), and consider the claim that \(x^2\geq x\) for every \(x\in D\). Since the domain has three elements, we check all three: $$ (-2)^2=4\geq-2,\qquad 0^2=0\geq0,\qquad 3^2=9\geq3. $$ Each instance holds, and these are all the elements of \(D\). By the finite-domain proposition, the universal claim is true on this particular domain.
This exhaustive check does not prove the same assertion for all real numbers. The real domain contains values such as \(\frac12\), which are not among the three values checked, and at that value \(x^2<x\). The domain is part of the statement, not a detail that can be omitted.
A Reliable Standard for a Counterexample
When testing a conjecture, it is useful to separate discovery from verification. During discovery, try special values, look for sign changes, simplify the expression, and consider whether equality or a boundary case causes trouble. This stage may involve several unsuccessful candidates. That is normal: an unsuccessful search does not show that no counterexample exists.
Once a candidate appears to work, write a short, exact verification. State its domain membership, substitute it into the relevant expression, and display the inequality or unequal values that contradict the claim. For a conditional, explicitly check the hypothesis and then show that the conclusion fails. This turns a numerical suspicion into a mathematical argument.
The candidate need not be unusual or complicated. Simple values often make stronger counterexamples because the failure is transparent. Nor must a counterexample be unique. If several inputs violate a claim, any one of them is enough to refute its universal form. A counterexample also does not identify the full set of failures, give a corrected theorem, or establish what happens at every other input.
Check Your Understanding
For each question, identify what must be checked before concluding that a proposed input is a counterexample.
- What two conditions must an element \(c\) satisfy to be a counterexample to \(\forall x\in D,\ P(x)\)?
- A claim says, “For every real number \(x\), if \(x<0\), then \(x^2>0\).” Is \(x=0\) a counterexample? Explain which condition is decisive.
- Find a counterexample to the claim that \(x^2>x\) for every real number \(x\), and show the calculation that verifies the failure.
- Why does a value that makes the conclusion of a conditional false fail to be a counterexample if the hypothesis is false at that value?
- Several values satisfy a proposed rule on the real numbers. Why does this not, by itself, prove the rule for every real number?
- For a domain consisting of exactly four listed elements, what must be checked to establish a universal claim by exhaustive verification?