Encyclopedia > Counterexample

  Article Content

Counterexample

In logic, and especially in its applications to mathematics and philosophy, a counterexample is 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".

Table of contents

Proof

In terms of symbolic logic, counterexamples work as follows:

  • The proposition to be disproved is of the form ∀ x, P(x).
  • The counterexample provides a true statement of the form ¬P(c), where c is the counterexample.
  • Assume that the proposition ∀ x, P(x) is true.
  • By universal substantiation[?], deduce P(c) from this.
  • Next, form the conjunction P(c) ∧ ¬P(c).
  • This is a contradiction, proving that our assumption ∀ x, P(x) is in fact false.

Although this argument is a proof by contradiction, it doesn't rely on double negation[?], so it works in intuitionistic logic as well as in classical logic. However, it does not work in Brazilian logic[?], where contradictions aren't necessarily false. Counterexamples can exist in Brazilian logic, but the above argument must be checked to ensure that the contradiction produced actually is false in the particular case at hand.

Uses

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, you've already proved that all Orcs are evil. Now you're 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've noticed that, even though you can find examples of Orcs that aren't deadly, you nevertheless don't find any examples of Orcs that aren't 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's 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're mostly interested in Uruk-Hai, then this will still be a very useful theorem.

Using counterexamples in this way proved to so useful in the field of topology that the topologists Lynn A. Steen[?] and J. Arthur Seebach, Jr.[?], together with their graduate students, canvassed the field for a wide grouping of examples of topological spaces, publishing the results in the book Counterexamples in Topology[?] (ISBN 0-486-68735-X). If you're wondering whether one property of topological spaces follows from another, this book can usually provide a counterexample if it's false. Since then, several other "Counterexamples in ..." books and papers have followed.

In philosophy

In philosophy, counterexamples are usually used to argue that a certain philosophical position is wrong by showing that it doesn't apply in certain cases. Unlike mathematicians, philosophers can't 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 doesn't 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 didn't expect -- groups of people rather than individual persons. If Callicles accepts this argument, then he must either withdraw his claim or modify it so that the counterexample no longer applies. In fact, he changes his definition to "wiser" instead of "stronger", since no amout of numerical superiority can make people wiser.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Museums in England

... Cambridge Cornwall Barbara Hepworth Museum[?], St. Ives, Cornwall Penlee House, Penzance[?] Tate St. Ives[?] Cumbria Abbot Hall Art Gallery[?], ...

 
 
 
This page was created in 40.9 ms