Counterexample

In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule or law. 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". More precisely, a counterexample is a specific instance of the falsity of a universal quantification (a "for all" statement).

In mathematics, this term is (by a slight abuse) also sometimes 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.

In mathematics

In mathematics, counterexamples are often used to prove 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.

Rectangle example

Suppose that a mathematician is studying geometry and shapes, and she wishes to prove certain theorems about them. She conjectures that "All rectangles are squares". She can either attempt to prove the truth of this statement using deductive reasoning, or if she suspects that her conjecture is false, she might attempt to find a counterexample. In this case, a counterexample would be a rectangle that is not a square, like a rectangle with two sides of length 5 and two sides of length 7. However, despite having found rectangles that were not squares, all the rectangles she did find had four sides. She then makes the new conjecture "All rectangles have four sides". This is weaker than her original conjecture, since every square has four sides, even though not every four-sided shape is a square.

The previous paragraph explained how a mathematician might weaken her conjecture in the face of counterexamples, but counterexamples can also be used to show that the assumptions and hypothesis are needed. Suppose that after a while the mathematician in question settled on the new conjecture "All shapes that are rectangles and have four sides of equal length are squares". This conjecture has two parts to the hypothesis: the shape must be 'a rectangle' and 'have four sides of equal length' and the mathematician would like to know if she can remove either assumption and still maintain the truth of her conjecture. So she needs to check the truth of the statements: (1) "All shapes that are rectangles are squares" and (2) "All shapes that have four sides of equal length are squares". A counterexample to (1) was already given, and a counterexample to (2) is a non-square rhombus. Thus the mathematician sees that both assumptions were necessary.

Other mathematical examples

See also: Counterexamples in topology and Minimal counterexample

A counterexample to the statement "all prime numbers are odd numbers" is the number 2, as it is a prime number but is not an odd number. Neither of the numbers 7 or 10 is a counterexample, as neither contradicts the statement. In this example, 2 is the only possible counterexample to the statement, but only a single example is needed to contradict "All prime numbers are odd numbers". Similarly the statement "All natural numbers are either prime or composite" has the number 1 as a counterexample as 1 is neither prime nor composite.

Euler's sum of powers conjecture was disproved by counterexample. It asserted that at least n n^th powers were necessary to sum to another n^th power. The conjecture was disproven in 1966 with a counterexample involving n = 5; other n = 5 counterexamples are now known, as are some n = 4 counterexamples.

Witsenhausen's counterexample shows that it is not always true for control problems that a quadratic loss function and a linear equation of evolution of the state variable imply optimal control laws that are linear.

Other examples include the disproofs of the Seifert conjecture, the Pólya conjecture, the conjecture of Hilbert's fourteenth problem, Tait's conjecture, and the Ganea conjecture.

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.

See also

• Exception that proves the rule
• Contradiction

Further reading

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.
• Michael Copobianco & John Mulluzzo (1978) Examples and Counterexamples in Graph Theory, Elsevier North-Holland ISBN 0-444-00255-3.