Counterexample
From Wikipedia, the free encyclopedia
In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule, i.e., a specific instance of the falsity of a universal quantification (a "for all" statement).
For example, consider the proposition "all students are lazy". Because this statement makes the claim that a certain property (laziness) holds for all students, even a single example of a diligent student will prove it false. Thus, any hard-working student is a counterexample to "all students are lazy".
In mathematics, this term is (by a slight abuse) also frequently used for examples illustrating the necessity of the full hypothesis of a theorem, by considering a case where a part of the hypothesis is not verified, and where one can show that the conclusion does not hold.
Contents |
[edit] Proof
In terms of symbolic logic, counterexamples work as follows:
- The proposition to be disproved is of the form FORALL x P(x).
- The counterexample provides a true statement of the form NOT P(c), where c is the counterexample.
- Assume that the proposition FORALL x P(x) is true.
- By universal instantiation, deduce P(c) from this.
- Next, form the conjunction P(c) AND NOT P(c).
- This is a contradiction, proving that our assumption FORALL x P(x) is in fact false.
Although this argument is a proof by contradiction, it does not rely on double negation, so it works in intuitionistic logic as well as in classical logic.
The phrase "the exception proves the rule" appears to be contradictory. A common misconception is that when this was originally stated as a maxim, "proof" meant "test". In fact, as the OED explains, the origin of the expression is a legal maxim, the meaning of which, in general terms, is that when something is treated as an exception, we can infer that there is a general rule to the contrary.
The above can also be understood by noticing that the negation of the phrase "for all x, P(x)" is nothing else but "there is x such that not P(x)" (where P(x) is any proposition depending on x).
[edit] Uses
[edit] In mathematics
In mathematics, counterexamples are often used to probe the boundaries of possible theorems. By using counterexamples to show that certain conjectures are false, mathematical researchers avoid going down blind alleys and learn how to modify conjectures to produce provable theorems.
For a toy example, consider the following situation: Suppose that you are studying Orcs, and you wish to prove certain theorems about them. For example, suppose you have already proved that all Orcs are evil. Now you are trying to prove that all Orcs are deadly. If you have no luck finding a proof, you might start to look instead for Orcs that are not deadly. When you find one, this is a counterexample to your proposed theorem, so you can stop trying to prove it.
However, perhaps you have noticed that, even though you can find examples of Orcs that are not deadly, you nevertheless do not find any examples of Orcs that are not dangerous at all. Then you have a new idea for a theorem, that all Orcs are dangerous. This is weaker than your original proposal, since every deadly creature is dangerous, even though not every dangerous creature is deadly. However, it is still a very useful thing to know, so you can try to prove it. On the other hand, perhaps you've noticed that none of the counterexamples that you found to your original conjecture were Uruk-Hai. Then you might propose a new conjecture, that all Uruk-Hai are deadly. Again, this is weaker than your original proposal, since most Orcs are not Uruk-Hai. However, if you are mostly interested in Uruk-Hai, then this will still be a very useful theorem.
A mathematical counterexample would be something like this: If you had a theorem that said "all numbers that are not negative are positive," and someone pointed out that zero is not negative, but is also not positive, then zero would be a counterexample. This is a very obvious counterexample, but the same basic idea carries into more complicated areas of mathematics.
Using counterexamples in this way proved to be so useful that there are several books collecting them:
- Lynn Arthur Steen and J. Arthur Seebach, Jr.: Counterexamples in Topology, Springer, New York 1978, ISBN 0-486-68735-X.
- Joseph P. Romano and Andrew F. Siegel: Counterexamples in Probability and Statistics, Chapman & Hall, New York, London 1986, ISBN 0-412-98901-8.
- Gary L. Wise and Eric B. Hall: Counterexamples in Probability and Real Analysis. Oxford University Press, New York 1993. ISBN 0-19-507068-2.
- Bernard R. Gelbaum, John M. H. Olmsted: Counterexamples in Analysis. Corrected reprint of the second (1965) edition, Dover Publications, Mineola, NY 2003, ISBN 0-486-42875-3.
- Jordan M. Stoyanov: Counterexamples in Probability. Second edition, Wiley, Chichester 1997, ISBN 0-471-96538-3.
[edit] In philosophy
In philosophy, counterexamples are usually used to argue that a certain philosophical position is wrong by showing that it does not apply in certain cases. Unlike mathematicians, philosophers cannot prove their claims beyond any doubt, so other philosophers are free to disagree and try to find counterexamples in response. Of course, now the first philosopher can argue that the alleged counterexample does not really apply. Alternatively, the first philosopher can modify their claim so that the counterexample no longer applies; this is analogous to when a mathematician modifies a conjecture because of a counterexample.
For example, in Plato's Gorgias, Callicles, trying to define what it means to say that some people are "better" than others, claims that those who are stronger are better. But Socrates replies that, because of their strength of numbers, the class of common rabble is stronger than the propertied class of nobles, even though the masses are prima facie of worse character. Thus Socrates has proposed a counterexample to Callicles' claim, by looking in an area that Callicles perhaps did not expect — groups of people rather than individual persons. Callicles might challenge Socrates' counterexample, arguing perhaps that the common rabble really are better than the nobles, or that even in their large numbers, they still are not stronger. But if Callicles accepts the counterexample, then he must either withdraw his claim or modify it so that the counterexample no longer applies. For example, he might modify his claim to refer only to individual persons, requiring him to think of the common people as a collection of individuals rather than as a mob. As it happens, he modifies his claim to say "wiser" instead of "stronger", arguing that no amount of numerical superiority can make people wiser.
