Next: Types of Proof Up: NOTES ON METHODS OF Previous: Definitions and Theorems

# Disproving Statements

Some conjectures are false. Verifying that a conjecture is false is often easier than proving a conjecture is true. Despite that, showing a conjecture is false may have its own challenges and usually requires a deep knowledge of the subject.

Some statements are often shown to be false by a counter examples. Such statements have the form ``For all x in X conclusion''. This is shown to be false by finding one element of X which does not satisfy the conclusion. As an example, consider the statement ``For all prime numbers p, 2p+1 is prime''. This statement is true for the primes 2, 3 and 5. It is also true for the primes 11 and 23. However, the statement is an assertion for all primes. Clearly the statement is not true for the prime 7 (since 15 = 3 5) and we have obtained a counter example to the statement.

For finite sets, statements of the form such as ``There exists an x such that conclusion'' can be refuted by example. By testing each element of the set and showing no element satisfies the conclusion we have shown the statement is false through an exhaustive search. This would also refute the statement ``There exists a unique x such that conclusion''. However, a statement of this form might be false for another reason, namely that there are two or more elements of the set that satisfy the conclusion. Again, this statement could be refuted through a counter example. For example consider the statement ``The equation has a unique solution''. This statement is false in the integers since both 1 and -1 satisfy the equation and we have disproved it using a counter example. Note that the statement is true in the positive integers.

As we noted above, some statements remain conjectures for many years (or even centuries) due to the fact that a proof cannot be constructed (or discovered) or that a counter example cannot be found. There are many famous conjectures and famous theorems that were conjectures for many years (The 4 color theorem and Fermat's Last Theorem, for example).

Next: Types of Proof Up: NOTES ON METHODS OF Previous: Definitions and Theorems

Peter Williams
Sun Sep 15 22:27:27 PDT 1996