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.
Bruce Ikenaga's Home Page
Copyright 2018 by Bruce Ikenaga