I am very aware of the several posts that are in this forum, but to be honest I am not quite satisfied with the provided answers. Also, I can tell that the best post is the following:
Proof by Contradiction, Circular Reasoning?
I would love to continue the discussion in that post, however my reputation level does not allow me to add any comments, and I still have some questions. Therefore, I want to continue discussing more about proof by contradiction and circular reasoning.
Suppose we wish to prove $(P \wedge Q) \rightarrow R$. We assume P and Q. Proof by contradiction begins by assuming $\neg R$, and from these two assumptions, a "contradiction" is derived, and sometimes that contradiction is that $\neg P$ or $\neg Q$ (our initial valid assumptions). Therefore, since there is a contradiction with our assumptions, we conclude that it cannot happen that $\neg R$, so it must be the case that $R$.
This proof strategy bothers me, because I have the feeling that there is some kind of circular (or invalid) reasoning going on there i.e. $(P \wedge Q) \rightarrow R$ is equivalent to $\neg R \rightarrow \neg(P \wedge Q)$, so if we already know that the consequent is false, in order for the statement to be true, $\neg R$ has to be false, so R is true, but R is part of the consequent part of the conditional statement (isn't doing this like assuming there is a biconditional i.e. because R is true, then $P \wedge Q$ is true?). I probably don't know how to explain it better, but how/why can we say that this is indeed a proof? Hence, my main question is why it is valid to assume $\neg R$ if our conclusion involves R? I have one explanation that kind of makes sense to me (still a little iffy though):
- In more simple terms, where we want to prove that $P \rightarrow Q$, we are trying to do the following: $[(P \wedge \neg Q) \rightarrow Contradiction] \rightarrow (P \rightarrow Q)$ if we can prove that $(P \wedge \neg Q)$ leads to a Contradiction, then we are indeed proving that $P \rightarrow Q$, which was our original goal. Given that this is a tautology, whenever we follow this proof strategy structure, we are always proving $P \rightarrow Q$. However, saying that this is a tautology kind of bothers me for some reason.
I would sincerely appreciate your insights, and if there is anything you would improve in my post, please feel free to do so. I'm starting my formal journey in the proof realm (currently reading How To Prove It), and I have always heard that proofs by contradiction were the easiest strategy. However, I have learned that this strategy seems to be difficult at the beginning for all those who are trying to learn proof strategies.
Best Answer
There is nothing circular about the method of proof by contradiction, but the method does assume a principle called the law of the excluded middle (LEM) that is not accepted by mathematicians and logicians who adopt the position of intuitionism rather than classical logic. LEM asserts that for any proposition $A$, $A \lor \lnot A$ is true.
In classical logic, if you are trying to prove some proposition $R$, then as you "know" that $R \lor \lnot R$ is true, it is valid to assume that $\lnot R$ is true (otherwise, for $R \lor \lnot R$ to be true, we must have that $R$ is true already). Intuitionistic logic does not consider this line of reasoning to be valid, unless we can prove for this specific $R$ that $R \lor \lnot R$ is true. For an intuitionist, LEM does not apply to a proposition like the abc conjecture that has neither been proved nor disproved.