2
$\begingroup$

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):

  1. 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.

$\endgroup$
4
  • $\begingroup$ I think you can assume -R because you can assume everything you want. Are there any rules limiting what is allowed to assume? Never heard of any... $\endgroup$ – NeitherNor Feb 28 at 19:23
  • $\begingroup$ Can you please explain where you sense a circularity? This is not clear from your post. $\endgroup$ – Bram28 Feb 28 at 19:26
  • $\begingroup$ @Bram28 I am doing my best. I would appreciate any explanation as to why proof by contradiction is indeed a valid proof, in particular, why $\neg R$ can be used as an assumption when $R$ is what we want to prove. $\endgroup$ – Alejandro Ruiz Feb 28 at 19:54
  • 1
    $\begingroup$ @AlejandroRuiz You can assume whatever you want. Assuming $\neg R$ doesn't mean that you say $\neg R$ is true. Rather, you say: Let's see what would be the case if $\neg R$ would be the case. And if it turns out that a contradiction would be the case (which is impossible) if $\neg R$ is the case, then that tells you that $\neg R$ can in fact not be the case ... and hence $R$ is the case. $\endgroup$ – Bram28 Mar 1 at 0:34
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Circular reasoning is when you assume what you want to prove, not when you assume what you want to refute and derive a contradiction. The difference is crucial.

If we allow circular reasoning as I've defined it, we can "prove" anything as concisely as "$p$, therefore $p$". In particular, we can just as easily "prove" $p$ is true this way as prove it's false.

By contrast, a proof by contradiction can only succeed if what we assume turns out to imply a contradiction, at which point the proof is able to finish. You can quickly derive a contradiction by assuming $\sqrt{2}$ is rational. If you ever manage to derive one by assuming it isn't, let us know, because you'll have found an unknown inconsistency in whatever standard mathematical axioms you've started from.

$\endgroup$
2
$\begingroup$

It might help to reframe the concept of how the proof works: Instead of assuming ¬R, you consider the hypothetical possibility of ¬R.

You work out the consequences of what would be true if R is false. You prove that this hypothetical situation includes a contradiction, and therefore cannot be real.

After considering that hypothetical, you know that it is impossible for R to be false. In symbolic terms, you know that ¬(¬R) is true. This is equivalent to simply R being true, so you have proven R.

$\endgroup$
0
$\begingroup$

$(P \wedge Q) \rightarrow R$ is equivalent to $\neg R \rightarrow \neg(P \wedge Q)$

Yes, and the "proof by contradiction" is just proving $\neg R \rightarrow \neg(P \wedge Q)$ instead of $(P \wedge Q) \rightarrow R$.

$\endgroup$
0
$\begingroup$

Proof by contradiction is really casework.

Case 1: The formal system is inconsistent. In this case, every statement is true (and also false, but we don't care about that). In particular, the statement we want to prove is true. Done!

Case 2: The formal system is consistent. So if we have a statement A that implies a contradiction, then statement A must be false, otherwise we would be in Case 1, but we are in Case 2. In your example, this means that "(P and Q) and (not R)" must be false, because it implies a contradiction. But "(P and Q) implies R" is literally defined as "[(P and Q) and (not R)] is false". So we just showed "(P and Q) implies R", which is what we wanted. Done!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.