# Writing a proof

I am stuck at showing how if:

$$P \rightarrow Q$$ then this implies ($$Q \rightarrow R) \rightarrow (P \rightarrow R)$$

I know that if we assume $$P$$ is true then $$Q$$ also must be true. Therefore if $$Q$$ is true then $$R$$ must be true. And because $$Q$$ is true because $$P$$ is true so therefore $$R$$ must also be true.

However it would be appreciated if someone could help me understand this why is the case and what proof technique it is.

• What is "R"? "P=> Q" says nothing about "R"! "P=> Q" does NOT say "if Q is true then R must be true". The conclusion says that "IF Q being true implies that some other statement R is true then P being true also implies that this "R" is true. – user247327 Jan 23 at 16:28
• Well because P is true Q must be true. Then we have Q => R and we know Q is true from previous assumption so therefore R is true. If R is true because of Q and Q is true because of P then R also must be true because of P – Molly Jan 23 at 16:32
• This statement would have different proofs in different logical theories. In the theory you've been studying, do connectives like $\rightarrow$ represent a valuation on mappings of the letters to "true" and "false"? Try a truth table, or maybe a reduction tree. Or are the connectives more abstract, and just symbols that appear in axioms? You'd need a sequence of formulae where each can be proved from previous and/or from the axioms. – aschepler Jan 24 at 4:55

This property is called transitivity of implication.

You pretty much gave a proof in your question, but here's a proof written out in slightly more precise terms.

Suppose $$P \Rightarrow Q$$ is true. To prove $$(Q \Rightarrow R) \Rightarrow (P \Rightarrow R)$$, you need to assume $$Q \Rightarrow R$$ and derive $$P \Rightarrow R$$. So assume that $$Q \Rightarrow R$$ is true. To prove $$P \Rightarrow R$$ is true, you need to assume $$P$$ is true and derive $$R$$. So assume $$P$$ is true. All we have to do now is prove that $$R$$ is true.

At this point, we're assuming that $$P \Rightarrow Q$$, $$Q \Rightarrow R$$ and $$P$$ are all true. So:

• Since $$P$$ and $$P \Rightarrow Q$$ are true, we have that $$Q$$ is true; and
• Since $$Q$$ and $$Q \Rightarrow R$$ are true, we have that $$R$$ is true.

So we're done.

You can also prove this somewhat verbosely with a truth table... (I have named my intermediate steps just because the table was too wide to display nicely.)

$$\begin{array}{|c c c|c|c|c|c|c|} P & Q & R & P \implies Q & Q \implies R & P \implies R & & \\ & & &A&B&C&B \implies C & A \implies (B \implies C) \\ \\ T & T & T & T & T & T & T & T\\ T & T & F & T & F & F & T & T\\ T & F & T & F & T & T & T & T\\ T & F & F & F & T & F & F & T\\ F & T & T & T & T & T & T & T\\ F & T & F & T & F & T & T & T\\ F & F & T & T & T & T & T & T\\ F & F & F & T & T & T & T & T\\ \end{array}$$

It’s a sort of transitivity. $$P\implies Q$$ is true. So if $$Q\implies R$$, then $$P\implies Q\implies R$$. I don’t think there is a name for this. It’s just multiple implications that give a result.

Proving this is simple. Given $$Q\implies R$$, we want to demonstrate $$P\implies R$$. So let’s suppose that $$P$$ is true. So, $$Q$$ is true by $$(P\implies Q)$$ (it’s called the “Modus ponens”). But $$Q$$ is true, so $$R$$ is true. QED.

If you want a conceptual proof, you just need to know how to prove an implication. How do you prove $$A\rightarrow B$$? Assume $$A$$ is true, then show that $$B$$ follows (hoping you have some other information laying around to do this using $$A$$.

• Step 1 To show: $$(P \rightarrow Q) \rightarrow ((Q \rightarrow R) \rightarrow (P \rightarrow R))$$, assume $$(P \rightarrow Q)$$ and show $$(Q \rightarrow R) \rightarrow (P \rightarrow R)$$.

• step 2 To show $$(Q \rightarrow R) \rightarrow (P \rightarrow R)$$, assume $$Q \rightarrow R$$ and then show $$P \rightarrow R$$.

• step 3 To show $$P \rightarrow R$$, assume $$P$$ and then show $$R$$.

At each stage we're assuming something so by this last step we've assumed a whole bunch that can help us to show $$R$$.

Using $$P$$, assumed true from the last step and $$P\rightarrow Q$$ assumed true from step 1, $$Q$$ follows, via modus ponens.

Using this $$Q$$ and $$Q\rightarrow R$$ assumed true from step 2, $$R$$ follows, again via modus ponens.

And we're done. In short, a chain of implications unraveled from left to right.

$$A\Rightarrow B$$ can be written as $$\neg A\vee B.$$ Therefore, $$(Q\Rightarrow R)\Rightarrow(P\Rightarrow R) \\ =\neg(\neg Q\vee R)\vee (\neg P\vee R) \\ = (Q \wedge \neg R)\vee (\neg P\vee R) \\ = (\neg P \vee Q\vee R)\wedge (\neg P \vee R \vee \neg R) \\ = (\neg P \vee Q\vee R) \\ = (\neg P \vee Q)\vee R \\ = (P\Rightarrow Q) \vee R$$