How to Structure Proofs
General Structure
The following is an example of the structure you should use when proving something by structural induction (rule induction for abstract syntax). This will be the case for most proofs in this class.
Theorem: If X then A. Proof by induction on the structure of the derivation J.
Rules to Prove By
Induction Hypothesis Structure
Depending on the structure of your induction hypothesis, you may make different assumptions and must prove different things.
Induction Hypothesis   Can Assume Must Prove
If X and Y then A.   X and Y A
If X or Y then A. (1) X A
  AND(2) Y A
If X then A and B.   X A and B
If X then A or B.   X A or B
Most of these are pretty straightforward, but notice the second case where the condition is X or Y. In this case, there are two things to prove. You must show that if you are given just X or just Y, you will always be able to prove A.
Suggestions on proof writing blatantly stolen from Dave Walker. Page maintained by frances@cs. Last updated 8/30/2004.