7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user247327 Jan 23 at 16:28
  • $\begingroup$ 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 $\endgroup$ – Molly Jan 23 at 16:32
  • $\begingroup$ 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. $\endgroup$ – aschepler Jan 24 at 4:55
14
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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