Shantila's Inside Logic #14

Reductio ad absurdum

Apology.

A few chapters ago I said that the new vI rule was so easy "that even a caveman could do it." I apologize if anyone was offended by this remark. I didn't know those guys were still around.
*

The man who was going to make a confession got shot. He was knocked unconscious but he was not dead. EMT personnel arrived and begin administering artificial respiration. They tore off his shirt and found that the man was wearing a bulletproof vest.

Joe is looking at the bullet that fell out of his shirt. You notice the piece of paper upon which the man had been writing. The paper is covered with symbols of various shapes like & and v and >.

Maybe he was writing some sort of terrorist code. If Joe just shot a terrorist, then Joe might be in big trouble! Is it a terrorist code?

Could this man be a terrorist?

Suppose this man is a terrorist, you think. If so, he is lucky he is not in jail, because obviously he is sloppy and careless. He writes the code in broad daylight in a crowded airport in Detroit. He cannot make "&"s correctly. And, in any case, who ever heard of a terrorist using a gun in a crowded airport to steal a lottery ticket? This is one very sloppy and careless terrorist who is lucky he is not in jail. But wait! you think. Surely by now all the sloppy terrorists in Detroit are in jail. You assumed he is a terrorist. If so he would be in jail by now, and yet he is not in jail. It is impossible for anyone both to be in jail and yet not be in jail at a certain time. Therefore, you conclude, he is NOT a terrorist.

But if he's not a terrorist, what is the confession?

The man about whom you have been thinking wakes up. He looks at you.

"Am I dead?" he asks.

"Not yet," you say.

"Oh," he says.

"Would you like to make the confession?" you ask.

"Where's Shantila?" he asks.

Maybe he means the woman who left?

"Do you mean the woman who was sitting here with you before you pulled out the gun?" you ask.

"Yes," he says. "Shantila."

"She left you," you say. "She's long gone. She left twenty minutes ago."

"Oh, great," he says. "Not again."

**

You reason about the man using an interesting and new form of reasoning. To understand it, consider first that any sentence of the form P&~P is a contradiction.

Sally is in Cleveland right now and Sally is not in Cleveland right now

This sentence can be represented as C&~C. It is easy to see that such sentences cannot be true, simply because of the meanings of "and" and "not." If the first conjunct C is true, the second one ~C must be false; and vice versa. Either way, the conjunction C&~C will be false, since both its conjuncts must be true in order for the conjunction to be true.

Our new rule relies on the fact that contradictions cannot be true. The new rule is similar to Conditional Proof in that we make an additional assumption P to use it. And then we show that we can derive a contradiction Q&~Q based on that assumption P (together, perhaps, with other premises). Since contradictions cannot be true but the additional assumption P leads to a contradiction, we naturally conclude that the additional assumption P cannot be true, given the other premises. So we conclude ~P. This form of reasoning is called reductio ad absurdum --"reducing" the additional assumption to "absurdity".

Reductio ad Absurdum (RA)

If we assume P and can derive a contradiction Q&~Q, for some Q, and if P is one of the assumptions of the contradiction, we may derive ~P as a conclusion based upon the other assumptions of the contradiction.

Your reasoning about the man you suspected of being a terrorist can be represented as follows. You assume, for the sake of the argument, that he is a Detroit terrorist (T). Given this assumption, you can derive a contradiction, given your other premises, which leads you to the conclusion ~T. Your other premises are that he is not in jail (~J); he is sloppy (S); and if he were a sloppy Detroit terrorist, then he would be in jail, (T&S)>J.

79 ~J, S, (T&S)>J } ~T

  1 1. ~J A    
  2 2. S A    
  3 3. (T&S)>J A    
  4 4. T A (for reductio)    
  2,4 5. T&S 2,4 &I    
  2,3,4 6. J 3,5 MP  
  1,2,3,4 7. J&~J 1,6 &I        
  1,2,3 8. ~T 4,7 RA            
         

On line 4 we assumed T and on line 7 we derived a contradiction J&~J. Notice that line 4 (where we assumed T) is one of the assumptions of line 7. And on line 8 we conclude ~T. On the right, we cite the line we are blaming for the contradiction (line 4) as well as the number of the contradiction itself (line 7). The numbers on the left are all those of the contradiction on line 7 except for the one (line 4) which we are blaming for the contradiction. So we "discharge" assumption 4 in the move from line 7 to line 8 and, as with CP, the number of assumptions is reduced by one in a use of RA.

RA is often useful when we are trying to prove a negation ~P. Instead of trying to construct a direct proof of ~P, we assume the opposite P, and then try to derive a contradiction. But RA also can be used to prove non-negated statements P. The way to do it is to assume ~P and then derive ~~P, and then of course we can derive P using DN, as in the following proof.

80 ~P>R, ~P>~R } P

  1 1. ~P>R A    
  2 2. ~P>~R A    
  3 3. ~P A    
  1,3 4. R 1,3 MP    
  2,3 5. ~R 2,3 MP    
  1,2,3 6. R&~R 4,5 &I  
  1,2 7. ~~P 3,6 RA        
  1,2 8. P 7, DN            
         

Here we want to derive P. But when we examine our two premises, there does not appear to be any "direct" way to derive it, so we assume ~P, and then we are able to get a contradiction R&~R on line 6, and then we use RA to conclude ~~P on line 7, and finally we use DN to get P on line 8.

When direct attempts to prove a valid sequent fail or do not seem promising, it is usually a good bet to try the RA strategy: simply assume the opposite of what you want to prove, and then try to derive a contradiction.

Here is an example in which both CP and RA are used in a single proof of the following logical truth.

81 } ~P > ~(P&Q)

  1 1. ~P A (for CP)    
  2 2. P&Q A (for RA)    
  2 3. P 2, &E    
  1,2 4. P&~P 1,3 &I  
  1 5. ~(P&Q) 2,4 RA        
  --- 6. ~P > ~(P&Q) 1,5 CP            
         

Here we assume ~P on line 1 for CP, and we wish to derive ~(P&Q). How can we do that? Well, we now assume P&Q on line 2, our goal being to derive a contradiction based on that assumption. We are able to do that on line 4 so we use RA on line 5; and we complete the proof with CP on line 6.

*

Given the set of Rules in our system, there may be several different ways to construct a proof of a valid argument. For example, consider this argument.

If she loves me she won't steal my car. But she is stealing my car. So she doesn't love me.

Let L stand for "she loves me" and S for "she is stealing my car." We can represent this argument by this sequent:

L>~S, S } ~L

We can prove this sequent in two ways; the first way does not use RA and the second does use RA. Here is the first way:

  1 1. L>~S A    
  2 2. S A    
  2 3. ~~S 2, DN    
  1,2 4. ~L 1,3 MT  

In this this proof we use the rules DN and MT in a straightforward way.

Here is an alternative proof that uses RA. Since we are trying to prove ~L, we assume L and derive a contradiction.

  1 1. L>~S A    
  2 2. S A    
  3 3. L A (for RA)    
  1,3 4. ~S 1,3 MP    
  1,2,3 5. S & ~S 2,4 &I    
  1,2 6. ~L 3,5 RA  

Each of these proofs is fine as a proof of the valid sequent

L>~S, S } ~L

This shows that we can use RA, but we do not need to use RA, to prove this sequent. But there are other valid sequents (such as 79, 80 and 81 proved earlier in this chapter) that we could not prove without our new Rule RA.

 
*Practice

14.1 Give an example in English of a contradiction.

14.2 Use the Rules of our system to construct proofs for each of the following sequents.

82 Q>S, Q>~S } ~Q

83 ~Q, P, (R&P)>Q } ~R

84 ~Q>(P&~R), P>R } Q

85 P>Q, P>R, R>~Q } ~P

86 ~P&Q, (~S&Q)>P } S

87 } ~R > ~(R&Q)

88 P>Q } ~(P&~Q)

89 ~(P&Q), P } ~Q

14.3 Symbolize each of the following arguments, and use any of our Rules to construct derivations to show that each is valid, using the abbreviations given.

(a) The man will confess. If the man confesses and also gives her eight million dollars, then the woman will stay. The woman will not stay. So the man will not give her eight million dollars. (S: The woman will stay. C: The man will confess. E: The man will give the woman eight million dollars.)

(b) She would marry him if he raised some cash. But if he raised cash, he would blow it gambling. She will not marry him if he blows his cash gambling. Therefore the fact is he is not going to raise cash. (M: She will marry him. R: He raises cash. G: He will blow his cash gambling.)

(c) The Falcons won if they both were able to make their inside shots and stop UCLA's fast break. They did stop UCLA's fast break, but they did not win. Therefore they were not able to make their inside shots. (F: The Falcons won. I: The Falcons made their inside shots. S: The Falcons stopped UCLA's fast break.) (Note: This is an example of an argument that cannot be proved given our Rules without using RA.)

(d) If the caveman did it, then so can you. If you can do it and Joe can do it, then it is too easy. Joe can do it but it is not too easy. So the caveman did not do it and neither did you. (C: The caveman did it. Y: You can do it. J: Joe can do it. E: It is too easy.) (Hint: You will use &I on the last line to complete this proof.)

14.4 The following argument can be proved in two different ways, given our rules. Symbolize this argument and construct two different proofs of it. (Note: See the example in this chapter about the car theft.)

The ice cream has melted. If you can have pie, then Sally didn't eat it. If the ice cream melted, then Sally ate the pie. So you can't have pie. (M: The ice cream melted. P: You can have pie. S: Sally ate the pie.)