2.4: Proof by Contradiction

How often have I said to you that when you have eliminated the impossible,
whatever remains, however improbable, must be the truth?

Sherlock Holmes, fictional British detective
in The Sign of the Four

The usual way to prove that an assertion is false is to show that it cannot be true. We do this by considering what would happen if it were indeed true. That is, we assume, for the sake of argument, that the assertion is true. If, by using logic, we can show that this assumption leads to a contradiction, then we can conclude that the hypothesis was wrong: the assertion we are interested in must be false. This is known as proof by contradiction.

Proofs by contradiction are used quite commonly in everyday life. Here is a contrived example:

Example \(\PageIndex{1}\)

Suppose someone has stolen a bracelet from Ms. Haslot’s parlour. Could the butler have done it? Inspector Thinkright might say: “Let us suppose that Jeeves, the butler, took the bracelet. We know he was in the kitchen until 8pm, so the theft must have taken place at a later time. However, Jeeves is highly allergic to Fifi, and that dog was in the parlour from 7:30pm until the theft was discovered at midnight, so Jeeves must have sneezed continuously while he was in the parlour. But the security guard absolutely refutes this: he states unequivocally that there were precisely 2 coughs, and no sneezes at all, coming from the parlour last evening. Thus, Jeeves could not have taken the bracelet; we eliminate him as a suspect.”

They also arise in mathematics:

Example \(\PageIndex{2}\)

Here is an argument in English that shows there is no greatest (i.e., largest) natural number:

Suppose there is some greatest natural number. Call it \(n\).

Then \(n + 1\) is also a natural number. And, obviously, \(n+1 > n\).

So there is a natural number (namely, \(n + 1\)) that is greater than \(n\).

This contradicts the fact that \(n\) is the greatest natural number.

So our hypothesis leads to consequences that are impossible.

Conclusion: Our hypothesis cannot be true: there is no greatest natural number.

The “Proof by Contradiction” rule allows us to turn an explanation of this type into an official proof. If we assume that a particular assertion is true and show that this leads to something impossible (namely, a contradiction), then we have proven that our assumption is wrong; the assumption must be false, so its negation must be true:

A: Alberta is big.

B: BC is big.

#	Assertion	Justification	English Version of Assertion
m	A	assumption (for contradiction)	Suppose that Alberta is big.
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
n	B & \(\lnot\) B	Whatever Reason	Then BC is big and BC is not big.
	\(\lnot\)A	proof by contradiction (lines m-n)	Alberta must not be big.

For this rule to apply, the last line of the subproof must be an explicit contradiction of the form \(B \& \lnot B\): some assertion and its negation. We write “(will lead to a contradiction)” or “(for contradiction)” as a note to ourselves and the reader. It is an explanation of why we started the subproof, and is not formally part of the proof.

Other Terminology

Proof by Contradiction allows us to put \(\lnot\) onto an assertion, so some logicians call it \(\neg\)-introduction, but we use the terminology of mathematicians, who always refer to it as “Proof by Contradiction.” (And the \(\neg\)-elimination rule is the fact that \(\lnot\lnot A\) is logically equivalent to \(A\), which is one of the rules of negation in .)

Exercise \(\PageIndex{3}\)

Provide a justification (rule and line numbers) for each line of these proofs.

1. #	Assertion	Justification
   1	\(\lnot\)C\(\Rightarrow\)B \(\lor\)C
   2	A & \(\lnot\) B
   3	\(\lnot\)C
   4	B \(\lor\)C
   5	B
   6	\(\lnot\)B
   7	B & \(\lnot\)B
   8	\(\lnot\lnot\)C
   9	C
   10	(A & \(\lnot\) B) \(\Rightarrow\) C

2. #	Assertion	Justification
   1	(A \(\lor\)B)\(\Rightarrow \lnot\)B
   2	B
   3	A \(\lor\) B
   4	\(\lnot\)B
   5	B & \(\lnot\) B
   6	\(\lnot\) B

3. #	Assertion	Justification
   1	P\(\Rightarrow\)Q
   2	Q\(\Rightarrow\)R
   3	R\(\Rightarrow \lnot\) P
   4	P
   5	Q
   6	R
   7	\(\lnot\)P
   8	P & \(\lnot\)P
   9	\(\lnot\)P

4. #	Assertion	Justification
   1	(P \(\lor \lnot\) Q) \(\Rightarrow \lnot\) R
   2	Q\(\Rightarrow\) R
   3	R
   4	Q
   5	P
   6	P \(\lor \lnot\) Q
   7	\(\lnot\) R
   8	R & \(\lnot\) R
   9	\(\lnot\) Q
   10	P \(\lor \lnot \) Q
   11	\(\lnot\) R
   12	R & \(\lnot\) R
   13	\(\lnot\) R

5. #	Assertion	Justification
   1	Z \(\Rightarrow\) (C & \(\lnot\) N)
   2	\(\lnot\) Z \(\Rightarrow\) (N & \(\lnot\) C)
   3	\(\lnot\)(N\(\lor\)C)
   4	N
   5	N\(\lor\)C
   6	(N\(\lor\)C) & \(\lnot\)(N\(\lor\)C)
   7	\(\lnot\)N
   8	C
   9	N\(\lor\)C
   10	(N\(\lor\)C) & \(\lnot\)(N\(\lor\)C)
   11	\(\lnot\)C
   12	Z
   13	C & \(\lnot\)N
   14	C
   15	C & \(\lnot\)C
   16	\(\lnot\)Z
   17	N & \(\lnot\)C
   18	N
   19	N & \(\lnot\) N
   20	\(\lnot\lnot\)(N \(\lor\) C)
   21	N \(\lor\) C

Exercise \(\PageIndex{4}\)

Give a two-column proof of each of these deductions.

1. \(Q\Rightarrow(Q\&\lnot Q)\), \(\therefore \lnot Q\)
2. \(J\Rightarrow\lnot J\), \(\therefore \lnot J\)
3. \(U \Rightarrow X\), \(V \Rightarrow \lnot X\), \(\therefore \lnot (U \& V)\)
4. \((M \lor N) \Rightarrow \lnot T\), \(\lnot T \Rightarrow \lnot M\), \(\therefore \lnot M\)
5. Hypotheses:

If Alice is here, then Bob is here.
If Bob is here, then Carol is here.
If Carol is here, then Bob is not here.

Conclusion: Alice is not here.