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

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

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

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

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