Having hard time understanding proofs by contradiction.

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


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.


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.


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