In the previous lesson, you learned that you can prove anything by
proving that it follows from its negation. The corollary to this is that
you can prove the negation of anything by showing that it follows from it.
That is, you can should that ~P is true if you can show that ~P follows
from P. In II.B. of the homework, you had to do a proof of this. To
illustrate the use of this principle, I will use it to derive the law of
noncontradiction, ~(P & ~P), which I've had you derive in two other ways
already.

               1.       P & ~P                  Assumption
               2.       ~P & P                  1, Comm.
               3.       ~P                      2, Simp.
               4.       ~P v ~~P                3, Add.
               5.       ~(P & ~P)               4, DM
               6.   (P & ~P) -> ~(P & ~P)       1-5, CP
               7.   ~(P & ~P) v ~(P & ~P)       6, Impl.
               8.   ~(P & ~P)                   7, Taut.

        You should notice that this derivation is just like the one in the
solutions to the homework--except that it never uses DN. Thus, it is two
lines shorter. Nevertheless, it is still two lines longer than our original
proof for the law of noncontradiction (I.B. in homework 10c). We shall do
something about that.

        In II.A. of the homework, I asked you to derive Q from (P & ~P).
You can do this because anything follows from a contradiction. If you don't
believe me, examine the solution to II.A. You should see that you can add
anything to one member of a contradictory pair, negate it with its
contradiction, and so use DS to derive whatever you added. From this, it
follows that whenever you derive a contradiction from within the scope of
an assumption, you will always be able to derive the negation of your
assumption. Therefore, any assumption that implies a contradiction
also implies its own contradiction. And from what we already know, any
assumption that implies a contradiction must be false, and its
contradiction must be true. So, whenever we derive a contradiction within
the scope of an assumption, we need go no further. We can stop there and
infer that the contradiction of our assumption is true.

        The rule by which we do this is called indirect proof (IP). It
works very much like conditional proof. You begin with an assumption, and
you end by closing the scope of the assumption. You end an indirect proof
when you have a contradiction on one line, and what you derive is the
contradiction of your assumption. Here is a proof of the law of
noncontradiction, which uses IP:

               1.       P & ~P                  Assumption
               2.   ~(P & ~P)                   1, IP

        Proofs don't get any shorter than this. Since it is so short, I'll
give you another example of a proof that uses IP.

        Derive P from

               1.   P v Q
               2.   P v ~Q
               3.       ~P                      Assumption
               4.       Q                       1, 3, DS
               5.       ~Q                      2, 3, DS
               6.       Q & ~Q                  4, 5, Conj.
               7.   P                           3-6, IP

        I used this same problem in the previous lesson, and it took ten
lines there. Before I end this lesson, here's another way to think about
IP: If any assumption implies a contradiction, it must be false, and so its
contradiction must be true.