# Dictionary Definition

counterexample n : refutation by example

# User Contributed Dictionary

## English

### Noun

- An exception to a proposed general rule; a specific instance of the falsity of a universally quantified statement.

#### Translations

instance of the falsity

- Czech: protipříklad

# Extensive Definition

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.

## 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).

## 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, 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.

### 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.

counterexample in Bulgarian: Контрапример

counterexample in Catalan: Contraexemple

counterexample in Czech: Protipříklad

counterexample in German: Gegenbeispiel

counterexample in Spanish: Contraejemplo

counterexample in Esperanto:
Kontraŭekzemplo

counterexample in French: Contre-exemple

counterexample in Italian: Controesempio

counterexample in Hebrew: דוגמה נגדית

counterexample in Japanese: 反例

counterexample in Polish: Kontrprzykład

counterexample in Portuguese:
Contra-exemplo

counterexample in Romanian: Contraexemplu

counterexample in Russian:
Контрпример