# How do I prove the transitivity of a set of implications?

If I have a set of implications, how can I prove the transitivity? In other words: I know the transitivity law, but I need to show on paper for an assignment whether the argument is valid or not.

\begin{align} P&\to Q\\ Q&\to R \\ \therefore P&\to R \end{align}

I recall something to do with assuming P and/or Q, since $P\to Q$ will always be true if P is false anyhow, and the same with $Q\to R$... but I don't know how to do it on paper.

-

$$(1) P\rightarrow Q\tag{Hypothesis}$$ $$(2) Q\rightarrow R\tag{Hypothesis}$$ $$\quad\quad\underline{(3)\; P\quad }\tag{Assumption}$$ $$\quad \quad\quad |(4) Q \tag{1 and 3: Modus Ponens}$$ $$\quad\quad\quad |(5) R \tag{2 and 4: Modus Ponens}$$ $$(6) P \rightarrow R \tag{3 - 5: if P, then R}$$

$$\therefore ((P\rightarrow Q)\land (Q\rightarrow R))\rightarrow (P\to R)$$
(Note: step 6 is sometimes justified by "conditional introduction": together with what you are given or have established, if by assuming P, you can derive R, then you have shown $P \rightarrow R$).

Note: when I first learned propositional logic, once it was established (proven), we referred to the following "syllogism": $$P\to Q\\ \underline{Q\to R}\\ \therefore P\to R\quad$$ by citing it as the "Hypothetical Syllogism", for justification in future proofs.

-

Since the logic you are using is not quantified, and there are only three variables, you can prove the argument valid with an eight row truth table covering all of the possible truth values of the three variables:

P  Q  R    Premise:  P -> Q    Premise:  Q -> R:    Conclusion:  P -> R
------------------------------------------------------------------------
0  0  0                 1                   1               1
0  0  1                 1                   1               1
0  1  0                 1                   0               1
0  1  1                 1                   1               1
1  0  0                 0                   1               0
1  0  1                 0                   1               1
1  1  0                 1                   0               0
1  1  1                 1                   1               1


Now an argument is valid if the conclusion is true whenever all the premises are true. This means that in all the rows where both premises have a 1, we check whether the conclusion has a 1. By golly, this is the case. Therefore the argument is valid!

If we found a zero, that would be a counterexample which destroys the argument: a situation where the premises are all true, yet the conclusion is false.

In my table, the P -> Q column and its siblings are simply derived from the truth table for the conditional. P -> Q is only false when P is true, and Q is false, and true for the other three possible values of the variables.

-

I'm not sure about what notations you might use nor if you're using a natural deductive system, but this is the idea behind what you asked:

Suppose $P\to Q\\ Q\to R\\$ are true.

We want to prove that $P\to R$ is true.

To do this suppose $P$ is true.

Because $P\to Q$ is true it follows that $Q$ is true. Now because $Q$ is true, from $Q\to R$ being true follows that $R$ is true.

We assumed $P$ was true and we deduced that $R$ is also true, therefore $P\to R$ as we wanted.

-
Is this just a form of proof by cases? I guess it's one half of it anyhow - knowing that if we assume $\neg P$, the implication will be true no matter what - it's only relevant if we show that it's true if P is true? –  agent154 Jan 17 '13 at 18:28
No, it's not a proof by cases. What you mentioned is one way to do it: you always have $\neg P \vee P$, so you do it by cases the way you mentioned. However if you wanna prove a conditional statement, i.e., a statement of the form $A\to B$, it suffices to assume $A$ is true and then somehow deduce that $B$ is true. –  Git Gud Jan 17 '13 at 18:32
I just realized - I could convert the implications to clausal form using the rule $(\neg P\vee Q)\wedge (\neg Q\vee R)\Rightarrow (\neg P\vee R)$ and then use the resolution rule to resolve out $(\neg Q\vee Q)$ to get $\neg P\vee R$... That works as well. –  agent154 Jan 17 '13 at 18:38
Yes, that works too. –  Git Gud Jan 17 '13 at 18:39

The answer for $6$ is indeed, true but if you had to show it with a truth table would be as follows

$$\begin{array}{cccccccc}P & Q & R & P\!\rightarrow\! Q & Q\!\rightarrow\! R & P\!\rightarrow\! R & (P\!\rightarrow\! Q)\!\wedge\!(Q\!\rightarrow\! R) & [(P\!\rightarrow\! Q)\!\wedge\!(Q\!\rightarrow\! R)]\!\rightarrow\! (P\!\rightarrow\! R)\\ T & T & T & T & T & T & T & T\\ T & T & F & T & F & F & F & T\\ T & F & T & F & T & T & F & T\\ T & F & F & F & T & F & F & T\\ F & T & T & T & T & T & T & T\\ F & T & F & T & F & T & F & T\\ F & F & T & T & T & T & T & T\\ F & F & F & T & T & T & T & T\end{array}$$

As you notice above the column $(P\!\rightarrow\! Q)\!\wedge\!(Q\!\rightarrow\! R)$ is the same as the column of $(P\!\rightarrow\! R).$ So with both the hypotheses $(P\!\rightarrow\! R)$ and $(Q\!\rightarrow\! R)$ we can conclude that $(P\!\rightarrow\! R).$

-