Chapter 5, Tutorial 4
Indirect Proof:
Reductio Ad Absurdum
What a name! It makes logic sound so competitive: one takes the other side's claims and shows they are so wrong as to reduce to absurdity!
Look, Joe. You say that your checking balance is positive. But you also say that your only activity since yesterday is to spend $227.50 and deposit $38. Yet you just told us that your account balance yesterday was under $170. So....what have you been smoking?
Well, you, a nicer person than me, might say...
...that while Joe says his account balance is greater than 0 he also says that it's less than 170 - 227.50 + 38. And this means that the balance B is -$19.50, that is, almost $20 in the red. So, on the one hand it's claimed that the balance is greater than zero but calculation shows from the rest of what Joe says that he's in the negative. In other words, Joe has contradicted himself. Not all of what he tells us can be true: it's absurd to think what Joe thinks.
Let's say that Joe tells you this:
3 x ( 7 + 4) = (3 x 7) + 4
You say:
Couldn't be. Because suppose for the moment that it is true.
Assume:
3 x ( 7 + 4) = (3 x 7) + 4, that means
3 x ( 11 ) = ( 21 ) + 4, which means
33 = 25,
which is absurd! Indeed, this is a contradiction of the obvious 33 ≠ 25.
Thus, you conclude that Joe was wrong. In fact, you've done a kind of derivation proving he's wrong! OK, then, let's take stock:
We've just seen that one can take a claim and show it is wrong. We assume for the moment that it's true, then see that it really "reduces" to absurdity on closer inspection. And this inspection is just a little derivation of a contradiction!
Also, well worth noting: Our derivations have premises. We were premising basic facts about arithmetic. From these, we assumed "for the moment" that Joe was right, and showed that this assumption leads to contradiction.
Well, we can do that in our setting. We need only add a way to make "an assumption for the moment" and a little side-argument that takes Joe's thinking and show's it wrong. The side-argument corresponds to our blue-grey box just above.
So, we next build this assumption-and-side-argument-for-the-moment stuff into our derivation scheme!
Let's look at a more contrived example, but one we can easily symbolize in SL.
we know one thing about Joe, that he's getting an 'A' on at least one exam but he's not getting a B on any: 'A&~B'. We may even suppose that Joe knows this.
But, and here's the trouble, poor Joe says that he he will get an 'A' on some exam just in case he gets a 'B' on some other: 'A=B'. Joe isn't being crazy here: he's not saying he'll get both an 'A' and a 'B' on one and the same exam. But there is still a problem. For 'A&~B' is true and from that we'll show that 'A=B' cannot be. (You can probably see why already: you know that the truth table for 'A=B' contradicts that for 'A&~B', yes?)
We'll start our derivation as normal:
we have a premise 'A&~B' that we take to be true.
| Premise | 1 | A&~B |
But there is one odd thing about the beginning of this derivation...it has that empty box at the end.
What's up with that?
That empty box marks an additional column for our "side argument". What we will do is "pretend" that we think 'A=B' is true. Just as we did when we assumed "3 x ( 7 + 4) = (3 x 7) + 4", we'll show that our new assumption is fated to contradiction. All this pretense, all this assuming goes in the side argument: the boxes on the far right.
So, we begin our side-argument with Joe's mistaken claim:
| Premise | 1 | A&~B | |||
| Assumption | 2 | ....what if | A=B |
The claim is highlighted. Now, all we have to do is make a few calculations to see why it's mistaken.
First, apply EQ to the assumption.
| Premise | 1 | A&~B | |||
| Assumption | 2 | ....what if | A=B | ||
| 2 EQ | 3 | then... | (A>B)&(B>A) |
This is just to apply our standard rules, our standard thinking, to Joe's assumption to see where it leads...
One way to see where it leads is to apply &E to both 1 and 3:
| Premise | 1 | A&~B | |||
| Assumption | 2 | ....what if | A=B | ||
| 2 EQ | 3 | then... | (A>B)&(B>A) | ||
| 3 &E | 4 | then... | A>B | ||
| 1 &E | 5 | then... | A |
| Premise | 1 | A&~B | |||
| Assumption | 2 | ....what if | A=B | ||
| 2 EQ | 3 | then... | (A>B)&(B>A) | ||
| 3 &E | 4 | then... | A>B | ||
| 1 &E | 5 | then... | A | ||
| 4,5 MP | 6 | then... | B |
and &E again to show the "absurdity", a contradiction
| Premise | 1 | A&~B | |||
| Assumption | 2 | ....what if | A=B | ||
| 2 EQ | 3 | then... | (A>B)&(B>A) | ||
| 3 &E | 4 | then... | A>B | ||
| 1 &E | 5 | then... | A | ||
| 4,5 >E | 6 | then... | B | ||
| 1 &E | 7 | then... | ~B |
So, everything in the additional column on the right leads up to the contradiction. This shows that it's initial assumption, that on line 2, must be wrong, must be false.
Careful now, this is important. Because 'A=B' is shown false -- it couldn't be true! -- we know that '~(A=B)' is true. (This by our truth table definition of '~'.)
we jump out of the side-argument and back into the normal column. We are going to reject everything in this side argument -- after all it has led us to absurdity! -- and so explicitly say that 'A=B' is false and '~(A=B)' is true.
| Premise | 1 | A&~B | |||
| Assumption | 2 | ....what if | A=B | ||
| 2 EQ | 3 | ....then... | (A>B)&(B>A) | ||
| 3 &E | 4 | ....then... | A>B | ||
| 1 &E | 5 | ....then... | A | ||
| 4,5 >E | 6 | ....then... | B | ||
| 1 &E | 7 | ....then... | ~B | ||
| 2-7 RD | 8 | ~(A=B) |
This is our last essential rule. It's called 'RD' for "reductio". The idea is that if the side-argument leads to contradiction, then we know it's assumption must be wrong and we can say we've proven its negation by the rule RD.
Oh, and there's a difference in how we sight. With RD, unlike all our other rules, we cite only the whole sub-argument, 2-7.
OK, we'll see how much sense all that makes by doing a few examples. Next...