Indirect Proof

The method of indirect proof provides a powerful technique for proving arguments to be valid. It has been employed since ancient times and is often known by its Latin name: the reductio ad absurdum technique.

You construct an indirect proof by assuming the denial of the conclusion, and then, adding this to the list of premisses, you show that it is possible to deduce an explicit contradiction. Since an explicit contradiction cannot possibly be true, by showing that the denial of the conclusion leads to an explicit contradiction, what you are in effect showing is that it is not possible for all the premisses to be true and yet for the conclusion to be false. In other words if the premisses are all true, then the conclusion must be true, or in other words, the argument is valid.

The general form of an argument is the conjunction of the premisses implies the conclusion:

                            (Premiss  .  Premiss2 . ... Premissn.)  => Conciusion

By using the rules "impl." and "DeMorgan's" this statement can be shown to be equivalent to

                            ~[ (Premiss  .  Premiss2 . ... Premissn   .  ~Conclusion)]

which says, in effect, that "it is false that the conjunction of the premisses and the denial of the conclusion is true".

In an indirect proof, we deny this statement, thus asserting that

                            (Premiss  .  Premiss2 . ... Premissn   .  ~Conclusion)

when we deduce from this a contradiction, we show that this cannot be true, so therefore

                            ~[ (Premiss  .  Premiss2 . ... Premissn   .  ~Conclusion)]

is true, which is equivalent to the original argument.

                        An "explicit contradiction" is any statement of the form:     p  .  ~p

Once an explicit contradiction has been reached, we can in fact prove any conclusion, including the desired one by the following routine:

Step m          p  .  ~p
Step n.          p (first term of explicit contradiction)         m. simp
Step n+l        ~p (second term of explicit contradiction)  m, simp
Step n+2       p v Desired Conclusion (any we like)         n, add
Step n+3       Desired conclusion                                    n+2, n+l, D.S.
To construct an I.P.:

    1) After listing the premisses write a line of the form

                ~(conclusion)                I.P. (indirect proof)

    2) proceed deriving lines using the 19 rules, but now your "intended conclusion" is an explicit contradiction.

    3) as soon as you get a line of the form  p  .  ~p your proof is over. STOP

Remember: Any explicit contradiction will do.
It may be of the form (conclusion)  .  ~(conclusion) , but it does not have to be of this form.