Counter Examples
Counter Examples
Counter examples play an important role in mathematics. Whereas a complicated proof may be the
only way to demonstrate the validity of a particular theorem, a single counter example is all that is
need to refute the validity of a proposed theorem. For example, numbers in the form
22n + 1, where n is a positive integer, were once thought to be prime. These
numbers are prime for n = 1, 2, 3 and 4. But when n = 5, we get
225 + 1 = 4294967297 = (641)(6700417)
a composite number. Conclusion: When faced with a number in the form 22n + 1,
we are not allowed to assume it is either prime or composite, unless we know for sure for some other
reason.
q
A natural place for counter examples to occur is when the converse of a known theorem comes into
question. The converse of an assertion in the form "If P, Then Q" is the assertion "If Q, Then
P".
Example: From Calculus
In Calculus you learn that if a function is differentiable at a point, then it is continuous at that
point. What would the converse assert? It would say that if a function is continuous at a point, then
it is differentiable at that point. But you know this is false. The counter example is f(x) = |x|.
This function is continuous at x = 0, but it is not differentiable at x=0. This one counter example is
all we need to refute the converse.
q
Example: Rational & Irrational Numbers
If a and b are rational numbers, then so is a+b. The proof is very simple. By definition of a rational
number, a = p/q and b = s/t for some quadruple of integers p, q, s, and t and such that q and t are
nonzero. The sum a+b = p/q + s/t = (p t + q s)/(q t), a rational number by definition. What would the
converse say? It would assert "If a and b are real numbers such that a + b is a rational number, then
a and b are rational numbers." But this is false. Just let a = sqrt(2) + 1, where sqrt means the square
root, and b = - sqrt(2). Neither a nor b are rational numbers, but a + b = 1, which is rational.
q
Exercises
- State the converse of "If a and b are even integers then a+b is an even integer". Show
that the converse is not true by producing a counter example.
- State the converse of "If a, b and c are real numbers such that a + b = c, then
(a+b)2 = c2". Show that the converse is not true by producing a counter example.
- State the converse of "If a, b and c are integers such that a divides b, then a divides the
product bc." Show
that the converse is not true by producing a counter example.
- State the converse of "If a and b are rational numbers, then
so is the product ab". Show that the converse is not true by producing a counter example.
Next==>Proof by Exhaustion (Case by Case)
<==Back To Constructive Versus Existential Proofs (Getting
Started)
Back to Proofs