   Ken Monks
    Dept. of Mathematics
    University of Scranton
    Scranton, PA 18510

**SITE CONTENTS**
Home Page	Software	Courses
Publications	Student Research	Misc

Phone: (570) 941-6101
Fax: (570) 941-5981
Office: STT163-A

Email:

monks@scranton.edu

Proof Strategies

The following is a excerpt from an email message that I sent in reply to a student's question about the right approach to writing proofs. I have included it here as general reference for students in my courses who are just starting to learn how to write proofs.

So how do you find the "right approach"? Well, that is similar to asking a chess master "How do you play chess well?". While the rules of the game are well defined and easy to learn, playing well is not easily defined and easy to learn. It takes a lot of practice, a lot of trial and error, and a lot of studying proofs done by others (e.g. me) to see what "approaches" are effective. Finding the "right approach" is where the ingenuity and creativity and inspiration is involved. Otherwise math proofs would just be done by computers.

That having been said, there are some "strategies" you can use in developing the "right approach". Some of the main strategies are:

1. Try working backwards.

Sometimes instead of starting at the top of the proof and working down towards a conclusion, try starting at the conclusion (what you want to prove) and ask yourself what kind of things you could do to prove it, then work backwards up the proof to see if you can make a whole proof.

2. Try to meet in the middle.

Sometimes you can work backwards and forwards at the same time and try to get the proof to meet up somewhere in the middle.

3. Process of elimination.

In deciding what rule of inference you want to use to prove something, you can look at the entire list of rules of inference that are available to you and eliminate ALL of the rules that can't possibly be used to prove what you want. For example, if you are trying to show "P and Q", then you can't use the "=>+" rule, because there is no "=>" in your conclusion. Once you eliminate all the rules that CAN'T be used, there might only be one or two rules left that CAN be used. If there is only ONE rule left that can be used, then you don't have much choice! If there are only a couple of rules that can be used then you can try each one in order by brute force until you fid one that works.

4. Memorize the recipes!

Especially the ones for logic! You will use them in EVERY proof! There is NO proof that doesn't use logic. You have to know them BY HEART! It is too inefficient to keep looking them up on the recipe sheet to see which ones will work in a problem. It would be like trying to do long division without knowing your times tables. It makes it much easier to "see" the right approach if you carry around all of your "tools" in your head. You will used the logic recipes a ZILLION times in the rest of the course, so just learn them by heart. Internalize them. Try to understand WHY the recipe is what it is.

5. Use what you have.

When you are "stuck" at a certain line in a proof, look at the lines above it that are still active. These are your "raw materials" that you have to work with. In most cases the line you are proving isn't true in its own right, but is only true GIVEN the lines above it. Thus if you are not using those lines as your raw materials you might not be able to prove what you want. Thus you might ask yourself what rules of inference can the lines above be INPUT's for. This is the counterpart to the strategy of "Process of Elimination".

6. Break everything down into pieces and put the pieces back together again.

If you have complicated statements that are already in your proof, try using the "minus" rules to break them down into smaller "pieces".. tinier bite-sized statements. Then try using the "plus" rules to put the pieces back together in a way that produces the statement you are trying to prove. It's like working with Lego's... if you have a Lego house and a Lego car and want to build a Lego boat, you can't just stick the car on the house to make the boat, you have to break apart the Lego house and car into its little individual Lego pieces and put the pieces back together to make a boat. For example, if you have "P and Q" as one of the lines in your proof, you might use the "and-" rule to break it apart into P on a line by itself and/or Q on another line by itself.

7. Never under any circumstances let your intuitive knowledge get in the way.

Keep your intuition out of it. Pretend you don't know ANYTHING. Don't say to yourself "My goodness, "P or ~P" is true, because I KNOW intuitively that it is true. It doesn't matter what you think you know intuitively. That is irrelevant. All that matters is if you can PROVE it is true or not. This goes for any line in the proof. Logic is the study of the relationship between statements which is INDEPENDENT OF THEIR MEANING! It doesn't matter what the statements mean as far as proving them goes. Look at the Toy Proof system. What do the "statements" in the Toy Proof System mean? They don't mean ANYTHING! Yet you can still prove some of them by simply following the rules of inference. The same is true for all of your proofs. While "meanings" we assign to the symbols might be helpful to us in remembering the rules of inference or in deciding on an "approach" to doing a proof, the meanings we assign to the statements are IRRELEVANT in determining whether or not the proof is indeed a proof. If the proof is constructed using only the rules of inference, then it is a proof regardless of what "meaning" you try to assign to the statements. So try to keep your intuitions out of it. As I said before, I have a computer program which can verify proofs. The program has no "intuition" about the "meaning" of the statements. It is just following rules mechanically. This ability to divorce yourself from your intuition when doing proofs is an essential objectivity that you need to be good mathematicians.