Writing a proof

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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} $$

Answer 4

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.

Answer 5

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