A * counterexample* is an example that disproves
a universal ("for all") statement. Obtaining
counterexamples is a very important part of mathematics, because
doing mathematics requires that you develop a *critical
attitude* toward claims. When you have an idea or when someone
tells you something, *test the idea* by trying examples. If
you find a counterexample which shows that the idea is false,
*that's good*: Progress comes not only through doing the right
thing, but also by correcting your mistakes.

Suppose you have a quantified statement:

"All x's satisfy property P": .

What is its negation?

.

In words, the second quantified statement says: "There is an x
which does not satisfy property P". In other words, to prove
that "All x's satisfy property P" is *false*, you
must find an x which *does not* satisfy property P.

* Example.* Explain what you must do to disprove
the statement:

(a) "All professors like pizza".

(b) "For every real number x, ".

(c) " has a root between and ".

(a) To disprove "All professors like pizza", you must find a professor who does not like pizza.

(b) To disprove the statement "For every real number x, ", you must find a real number x for which .

(c) To disprove the statement " has a root
between and ", it's not
enough to say " is between and , but ". The statement to be
disproved is an *existence* statement:

"There is an x such that and ."

You can check that the negation is:

"For all x, it is not the case that both and ."

To *disprove* the original statement is to *prove* its
negation, but a single example will not prove this "for
all" statement.

The point made in the last example illustrates the difference between "proof by example" --- which is usually invalid --- and giving a counterexample.

(a) A single example can't *prove* a universal statement
(unless the universe consists of only one case!).

(b) A single counterexample can *disprove* a universal
statement.

In many cases where you need a counterexample, the statement under consideration is an if-then statement.So how do you give a counterexample to a conditional statement ? By basic logic, is false when P is true and Q is false. Therefore:

To give a counterexample to a conditional statement , find a case where P is true but Q is false.

Equivalently, here's the rule for negating a conditional:

Again, you need the "if-part" P to be true and the "then-part" Q to be false (that is, must be true).

* Example.* Give a counterexample to the
statement

"If n is an integer and is divisible by 4, then n is divisible by 4."

To give a counterexample, I have to find an integer n such is divisible by 4, but n is *not* divisible by
4 --- the "if" part must be true, but the "then"
part must be false. Consider . Then is divisible by 4, but is not divisible by 4. Thus, is a counterexample to the statement.

On the other hand, consider . While is not divisible by 4, is also not divisible by 4. For , the "if" and "then" parts of the statement are both false. Therefore, is not a counterexample to the statement.

* Example.* Consider real-valued functions
defined on the interval . Give a counterexample
to the following statement:

"If the product of two functions is the zero function, then one of the functions is the zero function."

(The *zero function* is the function which produces 0 for all
inputs --- i.e. the constant function .)

Here are two functions whose product is the zero function, neither of which is the zero function:

Here's a picture which makes it clear why their product is always 0:

* Example.* Give a counterexample to the
following statement:

"If , then converges."

You may recall this mistake from studying infinite series.

The harmonic series is

It diverges, even though .

The *converse* of the given statement --- the Zero Limit Test
--- *is* true: If converges, then . Or to put it another
way (taking the contrapositive), if , then *diverges*.

For example, the series diverges, because

An * algebraic identity* is an equation which is
true for all values of the variables for which both sides of the
equation are defined.

For example, here is an algebraic identity for real numbers:

It is true for all .

Since an algebraic identity is a statement about *all* numbers
in a certain set, you can prove that a statement is *not* an
identity by producing a counterexample.

* Example.* Prove that " " is *not* an algebraic
identity, where .

I need to find *specific* real numbers a and b for which the
equation is false.

If an equation is *not* an identity, you can usually find a
counterexample by trial and error. In this case, if and , then

So if and , then , and hence the statement is not an identity.

A common mistake is to say:

" , which is not the same as ."

In the first place, how do you *know* is not the same as ? It is no answer to say that they *look*
different --- after all,
looks very different than 1, but *is* an identity.

In the second place, *is* the same as
if (for instance) and --- and they're equal for many other values of a and
b.

To disprove an identity, you should always give a *specific
numerical counterexample*.

* Example.* Give a counterexample which shows
that "
" is not an identity.

An identity is only asserted for values of the variables for which both sides are defined. So the assertion here is actually

" for and ."

Thus, is a counterexample, since

You should *not* give or as a counterexample. For these values of x, one side
of the purported identity is undefined. Therefore, these cases are
not part of what is claimed, so they can't be counterexamples.

Finally, do not confuse giving a counterexample with *proof by
contradiction*. A counterexample *disproves* a statement
by giving a situation where the statement is false; in proof by
contradiction, you *prove* a statement by assuming its
negation and obtaining a contradiction.

Copyright 2018 by Bruce Ikenaga