The following are some suggestions for going about proof problems. It is important to remember that there are many different proof techniques, and in general there is no way of knowing in advance which technique will be most effective. Sometimes several attempts will be needed or different approaches tried. These are some suggestions for guiding your search.

• Examine carefully what it is you are being asked to prove. Is a given property or relation true for all members of a set, or only some? What is the universe of discourse? Are there special properties of the universe of discourse you can apply? (For example, if U is the set of all rational numbers, than you know automatically that any element of U can be written as a/b, where a and b are both integers and b ¹ 0. If U is the set of all odd positive integers, then any element of U can be written as 2p+1, where p is an integer >= 0. And so on.)
• If you are being asked to prove that something exists, it may be possible to prove it by giving an example. Try a few simple cases. If you find an example, you're done. If the universe of discourse is small, you may be able to test every element directly. If the universe of discourse is large (e.g. all integers, all real numbers, all homeowners, etc.) it will be impossible to test them all. Remember, it only has to be true for one for the existence property to hold. But finding that one can be tricky.  Thus, if you don't find an example after trying a few cases, move on.
• If you're being asked to prove that something is true for all elements of the universe of discourse, it may be possible to disprove it by counterexample; that is, by finding a single exception to the rule. The problem here is the same as above; if the set is large, it may not be possible to test every element, and "I checked a few and couldn't find a counterexample" is no proof at all. ("I asked five people, and they're all voting Republican. Therefore everybody in the country is going to vote Republican." Wrong!) Also, there may not be a counterexample; the hypothesis may really be true for all elements of the universe of discourse. Try a few simple cases; if you don't find a counterexample fairly quickly, move on.
• Take a look at what the elements are that you're being asked to prove something about. If they're integers, or objects that can be ordered, an inductive proof may be possible. More importantly: If they're rational numbers rather than whole numbers, an inductive proof may be possible but is unlikely, and if they're real numbers, uncountable, or cannot be ordered, an inductive proof is impossible.
• If the universe of discourse is small, it may be possible to test all elements of the set directly. For example, "For all integers n such that  0 < n < 10, n + 5 < 20." In this example, a proof by cases (showing something is true for all by showing it true for each individual element) will take longer to write down than to work out.
• If the universe of discourse is large, a proof by cases will be impractical. It may be useful to try a few "test" values to gain understanding of the problem, but this is not a proof; this is just testing a few cases to gain understanding.
• If you're being asked to prove that something is not true, i.e. that "There is no x such that...", a proof by contradiction may be fruitful. That is, you assume that such an object x does exist, then deduce what its properties must be, attempting to find a contradiction. If its existence leads to a contradiction, then it cannot exist. The proof that the square root of 2 is irrational runs along those lines.  (If you're curious, and you should be, the full proof is shown in section 3.1 of Rosen.)
• If the property you are trying to prove lends itself to algebraic manipulation, a direct approach is always worth attempting. Begin by writing down your hypothesis symbolically, and try to derive the conclusion directly. Again, if a direct proof doesn't work, try an indirect proof. Can you show that if the hypothesis is false, a contradiction must result? If so, then the hypothesis cannot be false; i.e. it must be true. (The mean value theorem in calculus is proven this way.)

To summarize:

• If you are being asked to prove existence, try to find an example, but don't spend too much time on this if it's not leading anywhere.
• If you're being asked to prove something is true for all, try to disprove by counterexample, but again, don't waste time on a fruitless search.
• If the universe of discourse is small, it may be possible to test each element of the set directly.
• Using a few test cases may help gain understanding and provide a clue on how to solve a proof, but is not a proof itself.
• If you are being asked to prove that something does not exist, try an indirect proof. Otherwise start by trying a direct proof.
• If you're not making progress with a direct proof, try an indirect proof.

EXAMPLES, COUNTEREXAMPLES, AND PROOFS

Students often get themselves confused, and lose points on homework and exams, over the issue of when examples are useful and when they are not.

If you are being asked to prove that something exists, or is true for some or at least one: A single example completes the proof. A counterexample is worthless.
Proposition: At least one person is planning to vote for the Libertarian party.
    Example: Tran said he's planning to vote Libertarian. Therefore at least one person is planning to vote Libertarian. Valid
    Counterexample: Bill said he's not planning to vote Libertarian. Therefore no one is planning to vote Libertarian. Invalid

If you are being asked to prove that something is true for all: A single counterexample disproves the hypothesis. An example is worthless.
Proposition: Everyone is planning to vote for the Republican party.
    Example: Cheryl said she's planning to vote Republican. Therefore everyone is planning to vote Republican. Invalid
    Counterexample: Manuel said he's not planning to vote Republican. So not everyone is planning to vote Republican. Valid

Generalization & Instantiation: If you are being asked to prove something is true for all, you may refer to a specific element of the universal set in the proof only if that element is arbitrary and unspecified. That is, in working the proof, you may find it convenient to refer to an element c of the set. You then show that the hypothesis is true for c and therefore true for all elements of the set. This is valid, provided that the only assumption you have made about c is that it is an element of the set. If you find yourself making statements like: "Suppose c = 3. Then the hypothesis is true, because..." you are only proving that the hypothesis is true for 3, not for all elements of the set. To be valid, your proof must hold for any element c that we may happen to choose.

If you already know that something is true for all elements of the set, then it is true for each individual element of the set. For example: "Let the universal set be the set of all even integers, and c be an element of that set. Then c is even and can be written as c = 2p." Presumably the proof will hinge on the fact that c is even. This is completely valid, and can be used with universal generalization. (If it's true for c, and the only assumption you made about c is that it's a member of U and therefore has whatever properties are implicit in U, you can generalize it to all members of U.)
 
 

Review Mathematical Notation

SI - CS 191 Homepage

CS 191 Course (VU/BIT) Homepage

Brian's Homepage

Email Brian
 
 
 

This page copyleft 1999 Brian K. Hare