0

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?

IgnorantCuriosity
  • 1,423
  • Note that $P\implies Q$ is logically equivalent to $\neg P \vee Q$. In the case of $\neg R\implies C$ this is logically equivalent to $\neg(\neg R)\vee C$, or equivalently worded, $R\vee C$. Since $C$ is false, that implies that $R$ must be true if the implication was true. – JMoravitz Aug 14 '16 at 01:54

1 Answers1

1

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.

Noah Schweber
  • 245,398