| << Chapter < Page | Chapter >> Page > |
The
RAA), Latin for
reduction to absurdity, seems very strange:If we can prove that is true, then we can prove the negation of our premise.Huh!?! What on Earth does it mean to prove that false is true?
This is known as proof-by-contradiction . We start by making a single unproven assumption. We then try toprove that is true. Clearly, that it nonsense, so we must have done something wrong. Assuming we didn't make any mistakesin the individual inference steps, then the only thing that could be wrong is the assumption. It must not hold. Therefore, we havejust proven its negation.
This form of reasoning is often expressed via contrapositive . Consider the slogan
If you paid list price, you didn't buy it at SuperMegaMart.(This is a contrapositive, because the real statement the advertisers want to make isthat if you buy it at SuperMegaMart, then you won't pay list price.), which we'll abbreviate . You know this slogan is true,and you just made a SuperMegaMart purchase ( ), and are suddenly wanting a proof that you got a good deal. Well, suppose we didn't. That is, suppose . Then by the truth of the marketing slogan,we infer . But this contradicts (that is, from and together we can prove that is true). The problem must have been our pessimistic assumption ; clearly that couldn't have been true,and we're happy to know that .
Spot the proof-by-contradiction used in The Simpsons:
Bart, filing through the school records:
Hey, look at this: Skinner makes $25,000 per year!
Other kids:
Ooooh!
Milhouse:
And he's 40 years old; that makes him a millionaire!
Skinner, indignantly:
I wasn't a principal when I was 1!
Milhouse:
And, he paints houses during the summer … he's a billionaire!
Skinner:
If I were a billionaire, would I still be living with my mother?[Kids' laughter]
Skinner, to himself:
The kids just aren't responding to logic anymore!
In the particular set of inference rules we have chosen to use, RAA is surprisingly important.It is the only way to prove formulas that begin with a single
¬. This is an example of reasoning about our logic system.It shows us that while we might have some redundant inference rules,RAA isn't one of them. The only other rule which produces formulas starting with an initial
¬is ¬Intro. Is this also essential, or could westill prove all the same things even without ¬Intro?
We'll prove .
| 1 | subproof: | ||
| 1.a | Premise for subproof | ||
| 1.b | ∧Elim (left), line 1.a, where , and | ||
| 1.c | ∧Elim (right), line 1.a, where , and | ||
| 1.d | Intro, lines 1.b,1.c, where | ||
| 2 | RAA, line 1, where |
Here's another relatively simple example which uses RAA. Show that the modus tollens rule holds:
| 1 | Premise | ||
| 2 | Premise | ||
| 3 | subproof: | ||
| 3.a | Premise for subproof | ||
| 3.b | ⇒Elim, lines 1,3.a | ||
| 3.c | Intro, lines 2,3.b | ||
| 4 | RAA, line 3 |
Notification Switch
Would you like to follow the 'Pdf generation test course' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|