What is the logical justification for proof by contradiction?

159 Views Asked by At

A book I'm reading states that when constructing a proof by contradiction we create the conditional ¬R ⟹ C, where R is the statement we are trying to prove, and C is the contradiction. To explain why R must be true, it says that C is considered false but the conditional is true, and therefore R must be true as well, since the only way a conditional can be true with a false consequent is if the antecedent (¬R) is false.

It does not explain how or why the conditional is said to be considered "true" though. Shouldn't the truth-value of the conditional be based on the truth-value of the antecedent and consequent, not the other way around? What is the real justification for being able to say that proof by contradiction can prove a statement R to be true?

1

There are 1 best solutions below

0
On

You write:

It does not explain how or why the conditional is said to be considered "true."

Indeed, you have to prove that the conditional $\neg R\rightarrow C$ is true. And if your book doesn't stress this point, it's very badly written!

Once you've proved "$\neg R\rightarrow C$" for some $C$ that you already know is false, you know that $R$ must be true! Why? Well, you can say the following:

"If $R$ were false, then $\neg R$ would be true - so $C$ would be true, by the conditional I've just proved. But I know $C$ isn't true! So $R$ can't be false."


One standard simplification you'll see a lot is to prove instead the conditional $\neg R\rightarrow R$. Why is this enough? Well, certainly we can also prove that "$\neg R\rightarrow \neg R$" is true. So by combining these two conditionals, we've proved $$\neg R\rightarrow (R\mbox{ and }\neg R).$$ Now, no matter what $R$ is, the sentence "$(R\mbox{ and }\neg R)$" is clearly false - no statement can be true and false at the same time.

So even though this approach might look a bit different, it's really the same underlying idea.