19.  USING INDIRECT DERIVATIONS

Direct derivations are possible when the original premises can be broken down (or transformed) into individual expressions that then allow us to use our basic set of introduction and eliminaton rules.  But what if an argument form is valid and we cannot use a direct derivation?  We have the alternative (which actually will work for any valid argument) of using an indirect derivation, meaning we assume that the intended conclusion is false and show that this could happen only if we also found something false in our premises.  What it means to find something false is that somehow, with a false conclusion, we can show that statements in the premises or derived from them would contradict each other.
Remember our basic definition of validity: something about the pattern rules out having all true premises and a false conclusion, so for an argument to be valid and still have a false conclusion at least one of the premises must be false.

Indirect derivations will work for any valid argument but, if a direct derivation is possible, you will ordinarily find that it allows for a shorter proof.  However, there are times when you may not see easily enough how to work with various rules to do this, so those are the times when it is a good idea to do an indirect proof instead (and it may even be shorter).

The arrangement of an indirect proof is somewhat different in that we indent for what we call a subordinate proof.  We begin with the hypothesis (HIP, standing for "hypothesis in an indirect proof") ) that the conclusion really is false (just as we have with our consistency trees), then show that this would lead to a contradiction.  We then "discharge the hypothesis" (and no longer indent) in the line following. 

Example:  If Alice studies and has a good memory, then she will get most of the answers correct and she will pass the test.  Alice did pass the test and she study, but she did not get most of the answers correct.  It follows that she does not have a good memory.

(S & M) -> (A & P), P & S, ~A |- ~M

1.  (S & M) -> (A & P)
2.  P & S
3.  ~A             / show~M
    4.  M            HIP          here we start by hypothesizing that the conclusion really is false in order to develop an indirect proof
                                       note how we have begun indenting
    5.  S            2,  Simp
    6.  S & M     4,5,  Conj
    7.  A & P      1,6,  MP
    8.  A             7,  Simp
    9.  A & ~A    3,8,  Conj     this is the key: we have arrived at an expression that is necessarily false
10.  ~M            4-9,  IP         ~M must be true since if M were true we would end up contradicting ourselves in our premises, which we assume is not the case

If you think back to some things you may have seen earlier in working with truth tables, arguments in which the premises do already contradict each other are said to be valid--and here all we mean is that the conclusion does follow, not that it actually has to be true in itself.

Example:  If Alice studies then she will pass.  Alice did not pass, but we know she studied.  Therefore, Alice is wearing a blue dress.

S -> P, ~P & S |- W

If we test for validity with a truth table we find that there is no bad line.
P  S  W  ||  S -> P | ~ P & S  | W
1  1  1        1          0      1
1  1  0        1          0      0
1  0  1        1          0      1
1  0  0        1          0      0
0  1  1        0          1      1
0  1  0        0          1      0
0  0  1        1          0      1
0  0  0        1          0      0


note that we would have the same result if we turned around our original conclusion and said she was not wearing a blue dress

1.  S -> P
2.  ~P & S    / W
    3.  ~W         HIP
    4.  S            2,  Simp
    5.  P            1,4,  MP
    6.  ~P          2,  Simp
    7.  P & ~P    5,6,  Conj
8.  W               3-7,  IP

A special use for indirect proofs is establishing that an expression is a tautology (an expression that because of its form is always true).  We refer to these as zero-premise arguments.

If Alice studies and passes, then she cannot both be studying and not passing.
|- (S & P) -> ~(S & ~P)

    1.  ~[(S & P) -> ~(S & ~P)]      HIP
    2.  ~[~(S & P) v ~(S & ~P)]      1,  Impl
    3.  (S & P) & (S & ~P)             2,  DM
    4.  S & P                                3,  Simp
    5.  P                                      4,  Simp
    6.  S & ~P                              3,  Simp
    7.  ~P                                     6,  Simp
    8.  P & ~P                              5,7,  Conj
9.  (S & P) -> ~(S & ~P)              1-8,  IP       

EXERCISES (ON YOUR OWN)

Symbolize each of the following arguments (both of which are intended to be valid) and use indirect derivations.

1.  If Alice studies then she will get most of the answers correct, and if she gets most of the answers correct then she will pass the test.  Therefore, if Alice does not pass the test then she did not study.  [use S,A,P]
2.  Knowing that Alice studies only if she is not working and she is not working only if she does not have a job proves that unless she is not studying she does not have a job.   [use S,W,J]

Go to the answer key
REVIEW EXERCISES:

Symbolize using the suggested notation, then provide indirect derivations.  Copy and paste the problems into an email to me as you have before, then fill in your answers.  Yes, these are the same problems you did for me in your last review exercise, but now I am asking you to develop your skill in working with an indirect proof.  Remember to indent for the subordinate proof.

1.  If the tests are long or they are difficult, then students are not happy.  Students who work hard will be happy, and the students are working hard.  Therefore, the tests must not be long.  [L,D,H,W]
2.  Unless Alice studies she will not pass.  She does need to pass in order to graduate.  Therefore, she will graduate only if she studies.  [S,P,G]
3.  If every student is ambitious then all the teachers are happy.  Not all teachers are happy.  Therefore, there are students who are not ambitious.
[Sx,Ax,Tx,Hx]
4.  Not all students are ambitious.  Any student who is not ambitious does not work hard.  Only students who work hard have good grades.  Therefore, some students do not have good grades.
[Sx,Ax,Wx,Gx]
5.  If Jill is a good student then she is ambitious.  Anyone who is ambitious works hard.  All honor students are good students.  Therefore, if Jill is an honor student she works hard.  [Gx,Sx,Ax,Wx,Hx,j]
6.  No good students are lazy.  Only good students are honor students.  Some individuals are honor students.  Therefore, there are students who are not lazy.
[Gx,Sx,Lx,Hx; hint: do not symbolize "individuals"]