What a Counterexample Must Do
In the previous tutorial, we saw how quantifier order determines what a statement asks us to prove. That same structure guides a disproof. If a statement claims that a property holds for every object in a domain, a counterexample is one object in that domain for which the property fails. Finding one is enough: it shows that the universal claim is false.
The challenge is not merely to find an unusual object. It must belong to the stated domain and fail the exact claim being made. For a conditional statement, the input must satisfy the hypothesis while violating the conclusion. For a claim that every input has a suitable witness, the counterexample must be an input for which no permitted witness works. Reading the quantifiers and conditions carefully tells us what we need to construct.
The requirement \(x_0\in A\) matters. A number outside the stated domain cannot contradict the claim, even if it would make the conclusion fail. The earlier Theorem (Negation of Quantified Statements) expresses the logic behind this method: to negate a universal claim, find an element that fails its condition. In practice, we must still construct that element and verify every relevant detail.
Worked Example: A Universal Inequality
Consider the claim that \(x^2\geq x\) for every real number \(x\). To disprove it, we need a real input at which the inequality goes the other way. Try \(x=\frac12\), which belongs to \(\mathbb{R}\). Substitution gives
Since \(\frac14<\frac24\), the claimed inequality fails at this input. Thus \(\frac12\) is a counterexample, and the universal claim is false. Notice that we did not need to determine every real number for which the inequality fails; one verified input suffices.
Match the Counterexample to the Claim
For inequalities and equations, a useful first step is to translate “fails” into a concrete condition. If the claim is \(f(x)\leq g(x)\), failure means \(f(x)>g(x)\). If it is \(f(x)=g(x)\), failure means \(f(x)\ne g(x)\). This translation helps distinguish a promising candidate from one that actually works.
For a conditional claim, there is an additional check. An input for which the hypothesis is false does not disprove the implication: the conditional makes no demand on such an input. The counterexample must make the hypothesis true and the conclusion false. The following criterion records this requirement precisely.
Proof. Suppose first that there is an \(x_0\in A\) for which \(P(x_0)\) is true and \(Q(x_0)\) is false. At \(x_0\), the conditional \(P(x_0)\Rightarrow Q(x_0)\) has a true hypothesis and a false conclusion, so it is false. Consequently, it is not true that the conditional holds for every element of \(A\).
Conversely, suppose the universal conditional claim is false. Then it fails at some \(x_0\in A\), meaning that \(P(x_0)\Rightarrow Q(x_0)\) is false. A conditional is false exactly when its hypothesis is true and its conclusion is false. Thus \(P(x_0)\) is true and \(Q(x_0)\) is false, as required. \(\square\)
Worked Example: Divisibility Does Not Pass to the Number
Consider the claim that for every integer \(n\), if \(4\) divides \(n^2\), then \(4\) divides \(n\). The domain is the integers, and the hypothesis is the divisibility condition \(4\mid n^2\). We test \(n=2\), which is an integer. Its square is \(2^2=4=4\cdot1\), so \(4\mid 2^2\). But \(4\nmid 2\): there is no integer \(k\) with \(2=4k\), since that equation would give \(k=\frac12\), which is not an integer.
The hypothesis is therefore true and the conclusion false at \(n=2\). By the Counterexample Criterion for a Conditional Claim, \(n=2\) disproves the universal statement. Checking only that \(n^2\) is divisible by \(4\) would not be enough; the failure of the conclusion must also be established.
When the Claim Contains an Existential Quantifier
Some universal claims promise more than a property at each input. A statement such as “for every \(x\), there is a \(y\) satisfying a condition” gives each input its own opportunity to have a witness. To disprove it, we need an input for which no allowed \(y\) works. This is stronger than showing that one particular choice of \(y\) fails.
The quantifier order from the previous tutorial makes the task clear: first identify the input that defeats the claim, then account for every possible witness in the stated domain. Often a simple property rules out all candidates at once.
Worked Example: No Real Square Has a Negative Value
Consider the claim that for every real number \(x\), there is a real number \(y\) such that \(y^2=x\). Choose \(x=-1\), a real number. We must show that no real \(y\) satisfies \(y^2=-1\). For every real \(y\), its square is nonnegative: if \(y\geq0\), then \(y^2\geq0\); if \(y<0\), then \(-y>0\), so \(y^2=(-y)^2>0\). In either case \(y^2\geq0\), which rules out \(y^2=-1\).
Thus \(x=-1\) has no real witness \(y\), and the universal-existential claim is false. A single failed choice of \(y\) would not establish this: the argument works because it excludes every real \(y\) at once.
Constructing a Witness from a Proposed Candidate
Sometimes the statement concerns a candidate that is itself chosen universally. Then a useful strategy is to start with an arbitrary proposed candidate and construct an input that defeats it. The resulting counterexample may depend on the candidate; this is appropriate when the claim says that every candidate has a certain property.
Proof. Let \(M\) be an arbitrary integer. Choose \(n=M+1\). Since the sum of two integers is an integer, \(n\in\mathbb{Z}\). Also,
so \(n>M\). This construction works for every integer \(M\). If some integer \(M\) were largest, there could be no integer greater than \(M\), contradicting the integer \(M+1\) just constructed. Hence no integer is largest. \(\square\)
This proof uses a different pattern from the fixed examples above. The number \(2\) disproves the divisibility claim regardless of any proposed input; by contrast, \(M+1\) is built from the candidate \(M\). When a claim has the form “every candidate has property \(R\),” looking for a construction that depends on the candidate can be more effective than searching for one fixed object.
Worked Example: A Polynomial Claim That Survives Small Tests
Consider the claim that \(n^2+n+41\) is prime for every nonnegative integer \(n\). A few small values may look consistent with the claim, but they cannot establish that it holds for all such integers. Try the allowed input \(n=41\). Direct substitution gives
Both factors \(41\) and \(43\) are integers greater than \(1\), so \(1763\) is composite, not prime. Since \(41\) is a nonnegative integer and the claimed property fails there, \(n=41\) is a counterexample. This example illustrates why checking many initial cases is not a substitute for proving a universal statement: a counterexample may occur only after those cases.
Use the Claim to Guide the Search
There is no single numerical trick that produces every counterexample. The claim itself suggests what to try. For an inequality, test values where the two sides may change order, such as negative numbers, zero, or numbers between zero and one. For a divisibility statement, try small integers with different remainders. For a statement involving an existential witness, look for an input that violates a necessary property of every possible witness. These are search strategies, not proofs; once a candidate is found, it must still be checked exactly.
Make sure the proposed input belongs to the set named in the claim.
Write down what must be true for the claimed property to fail, including which conditions of a conditional must hold.
Use the structure of the claim to guide the search; if the claim concerns every proposed candidate, consider constructing an input from that candidate.
Substitute the candidate and show explicitly that it is in the domain and that the required failure occurs.
A common pitfall is to report a value without checking the domain or the hypothesis. Another is to treat several successful tests as a proof that a universal claim is true. Testing can help locate a counterexample, but no finite collection of successful cases establishes a statement over an infinite domain. Conversely, one fully verified counterexample does settle that the universal claim is false.
Check Your Understanding
For each question, identify what a counterexample would have to satisfy before choosing one.
- What two facts must be verified for an input to disprove a universal conditional claim?
- Why does an input outside the stated domain fail to count as a counterexample?
- To disprove “for every real \(x\), there is a real \(y\) with \(y^2=x\),” why must the argument rule out every real \(y\) for the chosen \(x\)?
- How does the construction \(M+1\) depend on a proposed integer \(M\), and what does it show?
- Why can testing many initial values of a universal claim not replace a proof?