Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading an introductory book on mathematical proofs and I don't seem to understand the mechanics of proof by contradiction. Consider the following example.

$\textbf{Theorem:}$ If $P \rightarrow Q$ and $R \rightarrow \neg Q$, then $P \rightarrow \neg R$.

$\textbf{Proof:}$ (by contradiction) Assume $P$, then it follows that $Q$. Now, assume $R$, then it follows that $\neg Q$. Contradiction, we have $Q$ and $\neg Q$ at the same time. Hence, $\neg R$. Therefore, if $P \rightarrow Q$ and $R \rightarrow \neg Q$, then $P \rightarrow \neg R$, as desired.

What I don't understand in this proof, is that why having arrived at contradiction, we decide that our assumption that $R$ is necessarily false? It also could have been that our first assumption, namely, $P$, was false. Or both of them could be false.

So my question is: in general, when proving by contradiction, how do we know which assumption exactly is false? And how do we know that exactly one assumption must be wrong in order to proceed with the proof?

share|improve this question
3  
You're right; from $P\to Q$ and $R\to \lnot Q$ we can also conclude that $R\to\lnot P$. What $P\to \lnot R$ says is that if we knew that $P$ was true we would have to conclude that $R$ was false. And as you point out, if we knew that $R$ was true we would know that $P$ was false; this is $R \to \lnot P$. –  MJD Sep 2 at 16:25
    
Rest assured: you are not alone. Whole branches of mathematics exist that reject proofs by contradiction as nonsensical! –  reinierpost Sep 2 at 21:16
4  
@reinierpost: "Whole branches of mathematics exist that reject proofs by contradiction as nonsensical!" Interesting! Could you give any examples? –  crypton480 Sep 2 at 22:59
1  
Personally, I think the main problem here is simply the phrasing of the proof. I would have said "suppose $P$," i.e., suppose that we know that $P$ is true in some context. Then, we assume $R$. Thus, when we arrive that the contradiction, we'd know that, in a context where $P$ is true, the assumption of $R$ is incorrect. Conversely, supposing $R$ and assuming $P$, we would see that in a context where $R$ is true, $P$ must be false. Thus (as in J Marco's answer) you're really proving a disjunction rather than an implication. –  Kyle Strand Sep 3 at 15:35
1  
Hm, it looks like I need to study this some more ... –  reinierpost Sep 4 at 8:57

10 Answers 10

up vote 13 down vote accepted

In a proof with multiple assumptions you have to choose one of them to be "blamed" for the contradiction.

Think to your example in terms of assumptions; you start with a couple of them (they can be two Lemmas already proved, or two hypotheses) :

$P→Q$ and $R→¬Q$.

Then we proceed "formally" as follows (I'll use the Natural Deduction proof system; for a good explanation of the rules to be used, see : Ian Chiswell & Wilfrid Hodges, Mathematical Logic (2007), Ch.2 : Informal natural deduction, page 5-on) :

1) $P$ --- assumed

2) $Q$ --- from 1) and $P→Q$ by $\rightarrow$-elim (modus ponens)

3) $R$ --- assumed

4) $\lnot Q$ --- from 3) and $R→¬Q$ by $\rightarrow$-elim (modus ponens)

5) $\bot$ --- from 2) and 4) by $\lnot$-elim [i.e. using the rule : "from $\varphi$ and $\lnot \varphi$, infer $\bot$]

6) $\lnot R$ --- from 3) and 5) by $\lnot$-intro [i.e. using the rule : "if from $\varphi$ we have derived $\bot$, then infer $\lnot \varphi$], "discharging" temporary assumption 3)

7) $P \rightarrow \lnot R$ --- from 1) and 6) by $\rightarrow$-intro, "discharging" temporary assumption 1).

Thus we have proved :

$P→Q, R→¬Q \vdash P \rightarrow \lnot R$.


As per the above answer, we can apply contraposition : $\varphi \rightarrow \lnot \psi \vdash \psi \rightarrow \lnot \varphi$ to conclude also :

$P→Q, R→¬Q \vdash R \rightarrow \lnot P$.

In the previous proof, we have chosen the assumptiom $R$ to be "blamed" for the contradiction. We can as well choose $P$.

If you rewrite it introducing $\lnot P$ in step 6) above, you will end exactly with : $R \rightarrow \lnot P$.


Comment

In order to "have a feeling" with the above application of logical rules, modify the above proof using a single assumption $P \land R$.

Due to the fact that :

$P \land R \vdash P$ and $P \land R \vdash R$ [by : $\land$-elim]

we can repeat the same steps until 5) : $\bot$.

In this case, we have only one assumption to be "blamed" : $P \land R$ and we conclude with :

$\lnot (P \land R)$.

This means that, in the presence of the two Lemmas or hypotheses : $P \rightarrow Q$ and $R \rightarrow \lnot Q$, we cannot "jointly assert" $P$ and $R$.

Thus, one of them must be "removed". Which one ? it's up to us ...

share|improve this answer

To answer It also could have been that our first assumption, namely, P, was false. Or both of them could be false: yes, it could, but if you assume P, then R must be false, what you write $P\rightarrow\neg R$. You could have concluded $R\rightarrow \neg P$, of course (and it's the contraposition), by assuming $R$ instead of $P$.

Notice that both of these implications are true, even if $P$ and $R$ are false. You do not know which is false, because none is false a priori. You assume one is true, and you conclude something about the other.


When you do that in practice, it's usually not a problem. Example, let's prove $\sqrt{2}$ is irrational, by contradiction.

So, we assume $\sqrt{2}$ is rational, and we will be led to something that is certainly wrong, hence the assumption is wrong.

Since $\sqrt{2}$ is assumed to be rational, we have $\sqrt{2}=\frac pq$ for some integers $p$, $q$ that have no common factor (otherwise, factor them out).

Hence $p^2=2q^2$, so $2$ divides $p$, and $p=2p'$, and you rewrite your equality $4p'\,^2=2q^2$, or $q^2=2p'\,^2$. But then $2$ divides also $q$. It's not possible, since $p$ and $q$ have no common factor.

Hence something must be wrong. What? The only thing we have assumed, that $\sqrt{2}$ is a rational number.

share|improve this answer

Note that you don`t want to prove or contradict $P$ or $R$ themselves. What you want to prove is the implication $P\rightarrow\neg R$. So you pick the assumption of this implication, in this case $P$, and use it for further argumentation.
Now you can start your argumentation with another assumption like $R$ or with anything else. Important difference: now you can look for contradictions.

share|improve this answer

In proving $A\rightarrow B$ by contradiction, you assume $\neg(A\rightarrow B)$. The negation of $A\rightarrow B$ is $A\wedge \neg B$ (the one false case of an implication).

In your case this means you get to assume $P\rightarrow Q$, $R\rightarrow \neg Q$, and $\neg(P\rightarrow \neg R)$. However $\neg(P\rightarrow \neg R)$ is equivalent to $P\wedge R$. So you get $P$, $R$, $P\rightarrow Q$ and $R\rightarrow\neg Q$.

From that you should be able to get your contradiction. (There are other ways of proving this problems as well.)

share|improve this answer

Let me give a brief and less formal explanation than the other answers.

If you start with a set of assumptions {A1, A2, ... An} and derive a contradiction, it proves that the set of assumptions is internally inconsistent (or as @J-Marcos phrased it, "jointly incompatible") -- i.e. they can't all be true.

So you can pick any one of the assumptions, let's say Ai, and conclude that on the basis of the other assumptions, Ai must be false.

share|improve this answer

Proofs by contradiction prove that your assumptions are jointly incompatible. In this case, from $P\to Q$ and $R\to\neg Q$ you may conclude that $P\uparrow R$, where $\uparrow$ denotes NAND. Note that $P\uparrow R$ is true iff $P$ and $R$ cannot be simultaneously true. Negation is a particular case of NAND, when a sentence is 'self-incompatible' (i.e., $S\equiv(S\uparrow S)$). When reasoning by contradiction, you have in general no reason to conclude that a single one of your assumptions is false (in other words, to conclude that its negation is true), unless you have reasons to maintain the truth of all the other assumptions (which appears not to be the case in the statement of your Theorem, where no reason is given for one to prefer $P$ over $R$).

Of course, $P\uparrow R$ is equivalent to $P\to\neg R$ and to $R\to\neg P$ (and to $\neg P\lor\neg R$), but I feel this facile observation does not tell the full story. Because many people seem not to be comfortable with a disjunctive conclusion such as $\neg P\lor\neg R$, they seem to prefer restating this as an implication.

share|improve this answer

Great question. The answer is that, at that point in the proof, you're still assuming that $P$ is true. With the assumptions stated more prominently, the proof goes like this:

We are given that $P \to Q$ and that $R \to \neg Q$. Now we begin imagining that $P$ is true. Since $P$ is true and $P \to Q$, we know that $Q$ is true. Now we begin imagining that $R$ is true. Since $R$ is true and $R \to \neg Q$, we know that $\neg Q$ is true as well. So, $Q$ and $\neg Q$ are both true, which is a contradiction. Now we stop imagining that $R$ is true. Since assuming that $R$ is true leads to a contradiction, $R$ must be false. Now we stop imagining that $P$ is true. Since assuming that $P$ is true leads to the conclusion that $R$ is false, $P \to \neg R$.

Sure, either $P$ or $R$ could be false, and the other one true. Why do we say that $R$ is false instead of allowing the possibility that $P$ is false? Because we haven't yet stopped imagining that $P$ is true.

share|improve this answer

So my question is: in general, when proving by contradiction, how do we know which assumption exactly is false? And how do we know that exactly one assumption must be wrong in order to proceed with the proof?

If you look at a proof as an ordered (numbered) sequence of statements, the assumption that is negated by a contradiction is always the last assumption previously introduced that has yet to be discharged.

share|improve this answer

So my question is: in general, when proving by contradiction, how do we know which assumption exactly is false? And how do we know that exactly one assumption must be wrong in order to proceed with the proof?

If you make more than one assumption and get a contradiction, you cannot without further argument know which assumption(s) is(are) false.

However IMHO the point (which I cannot see clearly stated in any previous answers) is that if you set up the problem carefully you need only make one assumption: namely, assume that the result as a whole is false. In this case, assume that

If $P\to Q$ and $R\to\neg Q$, then $P\to\neg R$

is false. By standard propositional logic equivalences, this means that

$P\to Q$ and $R\to\neg Q$ are both true, and $P\to\neg R$ is false,

that is,

$P\to Q$ and $R\to\neg Q$ are both true, and $P$ is true and $R$ is true.

From this you easily deduce that $Q$ is true and therefore $R$ is false; but $R$ is also true, which is a contradiction.

Therefore, the theorem as a whole cannot be false and must be true.

share|improve this answer
    
You are incorrect. The assumption to be negated is always clear. See my answer. –  Dan Christensen Sep 3 at 15:06
    
@DanChristensen You are incorrect. As you said in your answer, you have to number and order the assumptions. This is the kind of further argument that I was referring to. –  David Sep 4 at 0:07
    
Really? I would think that every formal proof would consist of an ordered list of numbered statements. Otherwise, you would have to have hundreds of arrows flying all over from one page (or screen) to another in any proof of substantial length. –  Dan Christensen Sep 4 at 3:57
    
There are proofs other than formal ones! A proper formal proof will not contain any words at all, so this is clearly not what the OP is talking about. –  David Sep 4 at 4:58
    
A proper formal proof can and should have comments throughout -- like the comments in the source code for a computer program. In any case, in any well written informal proof, it should be obvious which was the last assumption introduced. –  Dan Christensen Sep 4 at 14:29

We are trying to prove that given $P \rightarrow Q$ and $R \rightarrow \neg Q$, we get $P \rightarrow \neg R$

The proof you describe derives a contradiction by assuming $P$ and $R$, so at least one of the assumptions have to be false.

You wonder why we have to select $R$ as the false assumption. We do not have to do so, but it does not matter. If $\neg P$ then $P\rightarrow \neg R$ is vacously true.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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