Methods of Proof

• A theorem is a statement that can be shown to be true.
• A proof is a sequence of statements that demonstrates that a theorem is true.
• Axioms or postulates are the underlying assumptions about mathematical structures.
• Proofs may include axioms, the hypotheses of the theorem to be proved, and previously proved theorems.
• The rules of inference, which are the means used to draw conclusions from other assertions, tie together the steps of a proof.
• Fallacies are common forms of incorrect reasoning.

1. Modus ponens or law of detachment
   • its basis is the tautology ( p ^ ( p --> q ) ) --> q
   • can be expressed in the following form

               p
               p --> q
              ---------
               q
     

   • ``if both an implication and its hypothesis are known to be true then the conclusion of the implication is true''
   • example:

               ``If it snows today, then we will go skiing''
               ``It is snowing today''
              -----------------------------------------------
               ``We will go skiing''
     

2. Simplification
   • basis: ( p ^ q ) --> p
   • form:

              p ^ q
             -------
              p
     

   • example:

              ``It is below freezing and raining now''
              -----------------------------------------
              ``It is below freezing now''
     

3. Modus tollens
   • basis: ( ~q ^ ( p --> q ) ) --> ~p
   • form:

              ~q
               p --> q
             ---------
              ~p
     

4. Hypothetical Syllogism
   • basis: ( ( p --> q ) ^ ( q --> r ) ) --> ( p --> r )
   • form:

              p --> q
              q --> r
             ---------
              p --> r
     

5. Disjunctive Syllogism
   • basis: ( ( p V q ) ^ ~p ) --> q
   • form:

               p V q
              ~p
             ---------
               q
     

1. Fallacy of affirming the conclusion
   • ( ( p --> q ) ^ q ) --> p is not a tautology (it is false when p is false and q is true).
2. Fallacy of denying the hypothesis
   • ( ( p --> q ) ^ ~p ) --> ~q is not a tautology (it is false when p is false and q is true).
3. Begging the question or circular reasoning
   • occurs when one or more steps of a proof are based on the truth of the statement being proved.

• Generally, we will be solving problems of the form, ``If p, then q'' where p and q are statements.
• Symbolically we write such implications as p --> q where --> is called the implication operator.
• A property of the implication operator which may be confusing is that for the implication to be true, we need only show that p being true implies q is true.
• By definition, if p is false then the implication is always true, regardless of the truth value of q. This means that a false statement can imply anything whatsoever.

1. Trivial Proof
   • If the statement q in the implication p --> q is true regardless of the truth value of p, we have a trivial proof.
   • e.g. Prove A ~= {} --> A is a subset of A U B for any set B.
2. Vacuous Proof
   • If the statement p in the implication p --> q is false then the implication is always true.
   • e.g. A is a proper subset of A --> A is a proper subset of A ^ B for any set B, where the containments here are strict.
3. Direct Proof
   • You prove the implication p --> q by assuming p is true and using your background knowledge and the rules of logic to prove q is true.
   • The assumption ``p is true'' is the first link in a logical chain of statements, each implying its successor, that ends in ``q is true''.
   • p --> statement 1 --> statement 2 --> ... --> statement n --> q
   • e.g. Prove ``If a number is divisible by 6, then it is also divisible by 3''.
   • Direct Proof
     • Assume x is divisible by 6

       --> x = k X 6          for some k in Z, by definition 
                                 of division
       --> x = k X (2 X 3)    known fact about numbers
       --> x = (k X 2) X 3    known property of multiplication
       --> x = m X 3          where m = k X 2 is an integer
       --> x is divisible by 3
       

     • A shorter version of the same proof: x is divisible by 6 --> exists k in Z such that x = 6k --> x = (2k)3 --> x is divisible by 3.
     • Often a direct proof will be more complicated, for example you may have to prove subsidiary results that you later use in one of your implications.
     • A useful technique in constructing direct proofs is working backwards. You examine your conclusion (q) and try to determine what statements would imply it. You can then ask the same question about that statement, etc. Combined with working forwards (what does p imply?) you can work towards the middle.
     • p --> s(1) --> s(2) --> ?...? --> s(k) --> s(k+1) --> q
     • Your job is reduced to closing the gap.
   • Indirect Proof (Proof by Contraposition)
     • In symbolic logic, the tilde (~) is used to indicate the negation of a statement.
     • If p is the statement, ``It is raining'', then ~p is ``It is not raining''.
     • A result of symbolic logic is that p --> q is equivalent to the implication ~q --> ~p, i.e. p --> q = ~q --> ~p.
     • The statement ~q --> ~p is called the contraposition of p --> q.
     • e.g. ``If it is raining, then I'll stay indoors'' is equivalent to the contraposition, ``If I am not indoors, then it is not raining''.
     • In an indirect proof you assume that the conclusion q is false and proceed to show that the premise p is false also.
     • The actual method is a direct proof that ~q --> ~p, the problem is making sure that the contrapositive was determined properly.
     • In converting from English to logic and vice-versa, the following holds

       p only if q                        ~q --> ~p = p --> q
       
       p if q                             q --> p
       
       p is sufficient for q              p --> q
       
       p is necessary for q               q --> p
       
       p is sufficient and necessary      p <--> q
       for q (i.e. p if and only if q)
       

     • The best approach in doing a proof by contrapositive is to restate the original problem in the form, ``If p, then q''. The contrapositive is then, ``If not q, then not p''.
     • e.g. Proof by contraposition
       • ``If x is divisible by 6, then x is divisible by 3''
       • Note: the contrapositive is the implication, ``If x is not divisible by 3, then x is not divisible by 6''.
       • Premise: x is not divisible by 3
       • --> x ~= k X 3 for_all k in Z
       • --> x ~= 2m X 3 for_all m in Z
       • --> x ~= m X 6 for_all m in Z
       • --> x is not divisible by 6.
     • Note: the statements p --> q and q --> p are not equivalent. q --> p is called the converse of p --> q and the converse of an implication cannot be used to prove that the implication is true. A converse may or may not be true but its truth value has no relation to the truth of the original implication.
     • e.g. The implication ``if a > 5, then a > 2'' is true but its converse, ``if a > 2, then a > 5'' is not.
     • Often theorems are stated as ``p if and only if q'' or symbolically, p <--> q. This means that each statement implies the other, or p --> q and q --> p. Therefore, p <--> q = ( p --> q ) ^ ( q --> p ). To prove such a statement, you must prove it both ways. The usual notation used in such a proof is:
       • --> (Assume p, prove q)
       • <-- (Assume q, prove p)
   • Proof by Contradiction
     • This method works by assuming your implication is not true, then deriving a contradiction.
     • Recall that if p is false then p --> q is always true, thus the only way our implication can be false is if p is true and q is false.
     • In practice then, we assume our premise is true but our conclusion is false and use these assumptions to derive a contradiction. This contradiction may be a violation of a law or a previously established result. Having derived the contradiction you can then conclude that your assumption (that p --> q is false) was false and so the implication is true.
     • Be careful with this method: make sure that the contradiction arise because of your original assumptions, not because of a mistake in method. Also, if you end up proving ~p then you could have used proof by contraposition.
     • e.g. Prove by contradition: ``If x + x = x then x = 0''.
       • Assume x + x = x and x ~= 0.
       • Then 2x = x and since x ~= 0 we can divide both sides by x to get 2 = 1 which is a contradiction.
       • Our assumption that the implication ``If x + x = x then x = 0'' is false is itself false, therefore the original implication is proven to be true.
   • Proof by Case
     • Some implications come in the form, p1 V p2 V ... V pn --> q. In words, ``p1 or p2 or ... or pn imply q''. In this case you can prove that each of the separate implications, p_i --> q is true. Notice that you must prove all of these implications, not just some of them. Often these cases will be derived in the course of the proof.