10.3 Indirect Proof
The last set of rules we will study are also the most powerful: the method of indirect proof gives us the rules of negation introduction and elimination.
Table of Contents
10.3.1 Principle of Indirect Proof
If your assumptions lead to absurdity, then your assumptions must be false.
Indirect Proof
The last set of rules we will study are also the most powerful: the method of indirect proof, also called “proof by contradiction” or reductio ad absurdum. The principle of indirect proof says that, if an assumption leads to a contradiction, then the assumption must be false. Recall that a contradiction is a sentence of the form P & ~P. From a truth table, we can see that a contradiction cannot possibly be true:
| P | ~P | P & ~P |
| T | F | F |
| F | T | F |
Since a contradiction cannot possibly be true, and it necessarily also false, the antecedent of any conditional which has a contradiction on the consequent must also be false. For instance, in any row where Q => (P & ~P) is true, then Q must be false:
| P | Q | ~P | P & ~P | Q => (P & ~P) |
| T | T | F | F | F |
| T | F | F | F | T |
| F | T | T | F | F |
| F | F | T | F | T |
We know from the rule of conditional proof that if an assumption leads to something, then the conditional with the assumption in the antecedent and the thing it leads to in the consequent is true. So, if an assumption leads to a contradiction, then the assumption must be false.
Notice one funny fact about indirect proof: if the basic premises of an argument are contradictory, then anything can be proved by indirect proof.
Proof by Contradiction
On the next two pages, we’ll look at the two rules used in symbolic logic to represent indirect proof, Negation Introduction (~I) and Negation Elimination (~E). First, however, we should look at some examples in ordinary English to help make sense of how Proof by Contradiction is supposed to work.
Suppose that you believe somebody is lying, but you want to prove it. For instance, they claim that they delivered a package to your front door, but now the package which they claim to have delivered is not there; they claim it must have been stolen, but you doubt they delivered it to begin with. You also know that if they delivered the package, then they would have had to walk across your muddy front lawn to do so. If they walked across your muddy front lawn, then there would be muddy shoe-prints on your front porch. There are no muddy shoe-prints on your front porch. Assuming they are telling the truth about delivering the package, it would have to both be the case that there are and are not muddy shoe-prints on your front porch; that is a contradiction, so they did not deliver the package.
To give another example, suppose that a professor suspects that a student purchased a paper online instead of writing it themselves. When the professor asks the student to explain what is written in the paper, the student claims to have forgotten most of what they wrote. The professor notices, however, that a passage of the purchased paper is quoted directly from German, and the quote is then explained in English in the paper. The student does not speak German. But the student would not forget speaking German if they spoke German. So, assuming that the student wrote the paper, the student both spoke German at the time it was written and did not speak German at the time it is written, a contradiction. So, the student did not write the paper.
We’ll now look at the two forms of indirect proof, negation introduction (~I) and negation elimination (~E).
10.3.2 Negation Introduction
If the way you’re going leads to a dead end, then it isn’t the way you’re going.
Negation Introduction (~I)
The rule of Negation Introduction (~I) says that when the assumption of any sentence leads to a contradiction, then we can conclude the negation of the sentence is true.It has this form, where n and n+1 indicate that any number of lines might occur within the scope of the assumption before a contradiction is reached.
1. | P (assumption)
… |
n. | Q & ~Q
n+1. | ~P (1-n, ~I)
Note that Q & ~Q need not occur on the same line; because of the rule &I, we know they can occur one after another and the argument structure is still valid:
1. | P (assumption)
… |
n. | Q
n+1 | ~Q
n+2 | ~P (1-n+1, ~I)
Typically, to use negation introduction, there must be some basic premises which will lead to a contradiction the claim in the assumption line, which then is used or reiterated within the scope of the assumption to produce a contradiction. For instance:
1. ~(B v D) (Basic)
2.| D (assumption)
3. | B v D (2 vI)
4. | ~(B v D) (1, Reit.)
5. ~D (2-5 ~I)
However, there are some claims which can be proved without any premises using negation introduction. Something which can be proven without any basic premises is called a Theorem of logic. In the proof of a theorem, the first line of the proof is an assumption. For instance, we can prove that P v ~P is a theorem using ~I:
1. | ~(P v ~P) (assumption)
2. | ~P & ~~P (1, DEM)
3. | ~~P (2 &E)
4. | P (3 DN)
5. | ~P (2 &E)
6. ~~(P v ~P) (1-5 ~I)
7. P v ~P (6 DN)
Examples with Negation Introduction
First Example
“Nobody washed the dishes. If Vince washed the dishes, then somebody washed the dishes. Assume Vince washed the dishes. Then somebody washed the dishes. But nobody did. So, Vince didn’t wash the dishes.”
Let:
S = Somebody washed the dishes.
V = Vince washed the dishes.
Proof:
1. ~S (basic)
2. V => S (basic)
3. | V (assumption)
4. | S (2, 3 MP)
5. | ~S (1 Reit.)
6. ~V (3-5 ~I)
Second Example
“Doug and Angela claim that neither of them flew to New York, but I know that Doug flew to New York if Bri flew there, and either Angela or Bri flew there. Assume they are telling the truth. Then Angela didn’t fly to New York, so Bri did, so Doug did. But then Doug both did and didn’t fly to New York, which is a contradiction. So, either Doug or Angela flew to New York.”
Let:
D = Doug Flew to NY
A = Angela Flew to NY
B = Bri Flew to NY
Proof:
1. B => D (basic)
2. A v B (basic)
3. | ~(D v A) (assume)
4. | ~D & ~A (3 DEM)
5. | ~A (4 &E)
6. | B (2, 5 DS)
7. | D (1, 6 =>E)
8. | ~D (4 &E)
9. ~~(D v A) (3, ~I)
10. D v A (9 DN)
Complete all of the following exercises to practice using negation introduction. Remember that /C. indicates the conclusion you are supposed to prove. Remember that negation introduction requires assuming the conclusion is false, by assuming the conclusion *without* the negation the conclusion would otherwise have.
10.3.3 Negation Elimination
If he wasn’t lying, then his nose wouldn’t grow; but it did grow, so, he is lying.
Negation Elimination (~E)
The rule of Negation Elimination (~E) says that when the assumption of a negated sentence leads to a contradiction, then we can remove the negation sign from the assumption and conclude that it is true. It has this form, where n and n+1 indicate that any number of lines might occur within the scope of the assumption before a contradiction is reached.
1. | ~P (assumption)
… |
n. | Q & ~Q
n+1. | P (1-n, ~E)
Again, remember that Q and ~Q can occur on separate lines within the assumption line, since we know, given the rule &I, that they could be put together on the same line.
Negation Elimination (~E) is equivalent to the rule of Negation Introduction (~I) combined with the rule of double negation (DN). We could prove the same thing in this way instead:
1. | ~P (assumption)
… |
n. | Q & ~Q
n+1. | ~~P (1-n, ~I)
n+2 | P (n+1, DN)
So, strictly speaking, we don’t need to add the rule of ~E, if we were willing to use ~I and DN instead; for simplicity and efficiency, however, it’s better to save a step and have a rule that lets us remove a negation in addition to a rule that lets us add one.
Examples with Negation Elimination
First Example
“Argie claims that she didn’t poison the cat, but nobody else has poison, and whoever poisoned the cat had poison. Assume Argie didn’t poison the cat. Then somebody else has poison. But nobody else has poison. So, Argie poisoned the cat.”
Let
A = Argie poisoned the cat.
S = Somebody else has poison.
C = Somebody else poisoned the cat.
Proof:
1. ~S (basic)
2. C => S (basic)
3. ~A => C (basic)
4. | ~A (basic)
5. | C (3, 4 MP)
6. | S ( 2, 5 MP)
7. | ~S (1, Reit.)
8. A (4-7 ~E)
Notice that we used reiteration on line 7 to repeat line 1 within the scope line, since 1 wasn’t within the scope line.
Second Example
“Gil claims he didn’t go to the liquor store. Well, either Gil went to the liquor store, or there is still money in his wallet. Gil’s wallet is empty. If Gil’s wallet is empty, then there is not still money in his wallet. Assume Gil did not go to the liquor store. Then there would be money in his wallet. So, Gil’s wallet would not be empty. But Gil’s wallet is empty. So, Gil did go to the liquor store.”
Let
L = Gil went to the liquor store.
M = There is money in Gil’s walle
E = Gil’s wallet is empty
Proof
1. L v M (basic)
2. E (basic)
3. E => ~M (basic) / C. L
4. | ~L (assumption)
5. | M (1, 4 DS)
6. | ~M (2, 3 MP)
7. L (4-6 ~E)
Notice that there are a number of ways in which this proof could have been done: there are often many valid ways to complete a proof.
Warnings
An important warning applies when using negation elimination or negation introduction. We have to be careful when dealing with sentences with modal operators, words like “can”, “may”, “might”, “must”, “would”, “could”, “should”, and “ought”, as well as sentences with propositional attitudes, like “knows that”, “believes that”, “hopes that”, “doubts that”, and so on.
To see why, consider that “John does not believe karma is real” and “John believes karma is not real” do not mean the same thing: John might fail to have any beliefs about karma. Again, “Mary is not hoping to win the lottery” can be true without “Mary is hoping to not win the lottery” being true; perhaps Mary isn’t playing the lottery, but that doesn’t mean she actively hopes not to win it.
Similarly, “You mustn’t enter this building” can be false, without meaning that “You must enter this building” is true; it is neither the case that you must enter or that you must not enter, and this is not a contradiction. Again, “Barry cannot swim” and “Barry can not swim” don’t mean quite the same thing: perhaps Barry can swim, which means “Barry cannot swim” is false, but it is also true that Barry is capable of living outside of the water (he is not a fish), so “Barry can not swim” is also true. And finally, “It is not the case that you shouldn’t break up with your girlfriend” does not mean “It is the case that you should break up with your girlfriend”.
A more advanced logic course than ours would study how the logic of these terms work, and how to know when the negation applies to the whole sentence, and when it applies only to the proposition embedded within the modal operator or propositional attitude. For our purposes, it is enough to keep in mind that we must take care when applying the rules of ~I and ~E, as well as DN, to these kinds of sentences.
Complete the following to practice using negation elimination. Remember that /C. indicates the conclusion you are supposed to prove. Remember that negation elimination requires assuming the conclusion is false, by assuming the negation of the conclusion.
Submodule 10.3 Quiz
Licenses and Attributions
Key Sources:
- Watson, Jeffrey (2019). Introduction to Logic. Licensed under: (CC BY-SA).
Next Page: 10.4 Applications of Conditional and Indirect Proof