Counterexamples

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": $\forall x P(x)$ .

What is its negation?

$\lnot \forall x P(x) \iff \exists x \lnot P(x)$ .

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, $(x + 1)^2 = x^2 + 1$ ".

(c) "$x^3 + 5x + 3$ has a root between $x = 0$ and $x = 1$ ".

(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, $(x + 1)^2 = x^2 + 1$ ", you must find a real number x for which $(x + 1)^2 \ne x^2 + 1$ .

(c) To disprove the statement "$x^3 + 5x + 3$ has a root between $x = 0$ and $x = 1$ ", it's not enough to say "$x = 0.5$ is between $x = 0$ and $x = 1$ , but $(0.5)^3 + 5(0.5) + 3 = 5.625 \ne 0$ ". The statement to be disproved is an existence statement:

"There is an x such that $0 < x < 1$ and $x^3 + 5x + 3 = 0$ ."

You can check that the negation is:

"For all x, it is not the case that both $0 < x < 1$ and $x^3 + 5x + 3 = 0$ ."

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 $P \ifthen Q$ ? By basic logic, $P \ifthen Q$ is false when P is true and Q is false. Therefore:

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

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

$$\lnot (P \ifthen Q) \iff (P \land \lnot Q)$$

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

Example. Give a counterexample to the statement

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

To give a counterexample, I have to find an integer n such $n^2$ 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 $n = 6$ . Then $n^2 = 36$ is divisible by 4, but $n = 6$ is not divisible by 4. Thus, $n = 6$ is a counterexample to the statement.

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

Example. Consider real-valued functions defined on the interval $0 \le x \le 1$ . 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 $f = 0$ .)

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

$$f(x) = \cases{ \dfrac{1}{2} - x & if $0 \le x \le \dfrac{1}{2}$ \cr \noalign{\vskip6pt} 0 & if $\dfrac{1}{2} < x \le 1$ \cr} \hskip0.5in g(x) = \cases{ 0 & if $0 \le x \le \dfrac{1}{2}$ \cr \noalign{\vskip6pt} x - \dfrac{1}{2} & if $\dfrac{1}{2} < x \le 1$ \cr}.$$

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

$$\hbox{\epsfysize=2.5in \epsffile{counterexamples-1.eps}}\quad\halmos$$

Example. Give a counterexample to the following statement:

"If $\displaystyle \lim_{n \to \infty} a_n = 0$ , then $\displaystyle \sum_{n=1}^\infty a_n$ converges."

You may recall this mistake from studying infinite series.

The harmonic series is

$$\sum_{n=1}^\infty \dfrac{1}{n} = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \cdots .$$

It diverges, even though $\displaystyle \lim_{n \to \infty} \dfrac{1}{n} = 0$ .

The converse of the given statement --- the Zero Limit Test --- is true: If $\displaystyle \sum_{n=1}^\infty \dfrac{1}{n}$ converges, then $\displaystyle \lim_{n \to \infty} a_n = 0$ . Or to put it another way (taking the contrapositive), if $\displaystyle \lim_{n \to \infty} a_n \ne 0$ , then $\displaystyle \sum_{n=1}^\infty \dfrac{1}{n}$ diverges.

For example, the series $\displaystyle \sum_{n=1}^\infty \dfrac{3n^2 + 1}{4n^2 - 3}$ diverges, because

$$\lim_{n \to \infty} \dfrac{3n^2 + 1}{4n^2 - 3} = \dfrac{3}{4} \ne 0.\quad\halmos$$

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:

$$\dfrac{1}{x} + 1 = \dfrac{x + 1}{x}.$$

It is true for all $x \ne 0$ .

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 "$(a + b)^2 = a^2 + b^2$ " is not an algebraic identity, where $a, b \in \real$ .

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 $a = 1$ and $b = 2$ , then

$$(a + b)^2 = (1 + 2)^2 = 3^2 = 9, \quad\hbox{while}\quad a^2 + b^2 = 1^2 + 2^2 = 5.$$

So if $a = 1$ and $b = 2$ , then $(a + b)^2 \ne a^2 + b^2$ , and hence the statement is not an identity.

A common mistake is to say:

"$(a + b)^2 = a^2 + 2 a b + b^2$ , which is not the same as $a^2 + b^2$ ."

In the first place, how do you know $a^2 + 2 a b + b^2$ is not the same as $a^2 + b^2$ ? It is no answer to say that they look different --- after all, $(\sin \theta)^2 + (\cos \theta)^2$ looks very different than 1, but $(\sin \theta)^2 + (\cos \theta)^2 = 1$ is an identity.

In the second place, $a^2 + 2 a b + b^2$ is the same as $a^2 + b^2$ if (for instance) $a = 17$ and $b = 0$ --- 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 "$\dfrac{1}{x + 2} = \dfrac{1}{x} + \dfrac{1}{2}$ " 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

"$\dfrac{1}{x + 2} = \dfrac{1}{x} + \dfrac{1}{2}$ for $x \ne 0$ and $x \ne -2$ ."

Thus, $x = 1$ is a counterexample, since

$$\dfrac{1}{x + 2} = \dfrac{1}{3}, \quad\hbox{while}\quad \dfrac{1}{x} + \dfrac{1}{2} = \dfrac{1}{1} + \dfrac{1}{2} = \dfrac{3}{2}.$$

You should not give $x = 0$ or $x = -2$ 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.

Contact information

Bruce Ikenaga's Home Page

Copyright 2019 by Bruce Ikenaga