Hypothetical Syllogism
Contents |
Theorem
- $p \implies q, q \implies r \vdash p \implies r$
Its abbreviation in a tableau proof is $\textrm{HS}$.
It is otherwise known as the transitivity law.
Alternative Renditions
These can alternatively be rendered as:
- $\vdash \left({\left({p \implies q}\right) \land \left({q \implies r}\right)}\right) \implies \left({p \implies r}\right)$
- $\vdash \left({p \implies q}\right) \implies \left({\left({q \implies r}\right) \implies \left({p \implies r}\right)}\right)$
- $\vdash \left({q \implies r}\right) \implies \left({\left({p \implies q}\right) \implies \left({p \implies r}\right)}\right)$
They can be seen to be logically equivalent to the forms above by application of the Extended Rule of Implication.
Some sources refer to these theorems as the principles of syllogism.
Proof
Proof by Natural Deduction
By the tableau method:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $p \implies q$ | P | (None) | ||
| 2 | 2 | $q \implies r$ | P | (None) | ||
| 3 | 3 | $p$ | A | (None) | Assume $p$ ... | |
| 4 | 3, 1 | $q$ | $\implies \mathcal E$ | 3, 1 | ... and derive $q$ ... | |
| 5 | 3, 2 | $r$ | $\implies \mathcal E$ | 4, 2 | ... and thence derive $r$. | |
| 6 | 1, 2 | $p \implies r$ | $\implies \mathcal I$ | 3, 5 | The assumption of $p$ has been discharged, so the proof rests just on 1 and 2. |
$\blacksquare$
Proof of Alternative Renditions
Let us use substitution instances as follows:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \phi\) | \(\text{ for }\) | \(\displaystyle p \implies q\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \psi\) | \(\text{ for }\) | \(\displaystyle q \implies r\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \chi\) | \(\text{ for }\) | \(\displaystyle p \implies r\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) |
First we show that:
- $\left({\left({p \implies q}\right) \land \left({q \implies r}\right)}\right) \implies \left({p \implies r}\right)$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\phi$ | P | (None) | ||
| 2 | 2 | $\psi$ | P | (None) | ||
| 3 | 1, 2 | $\phi \land \psi$ | $\land \mathcal I$ | 1, 2 | ||
| 4 | 1, 2 | $\chi$ | $\textrm{HS}$ | 1, 2 | From above ... | |
| 5 | $\left({\phi \land \psi}\right) \implies \chi$ | $\implies \mathcal I$ | 3, 4 | The assumptions of $\phi$ and $\psi$ have been discharged |
Using substitution instances leads us back to:
- $\left({\left({p \implies q}\right) \land \left({q \implies r}\right)}\right) \implies \left({p \implies r}\right)$
$\blacksquare$
From there, we have two more things to show:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | $\left({\phi \land \psi}\right) \implies \chi$ | P | (None) | A theorem rests on no assumptions | ||
| 2 | $\phi \implies \left({\psi \implies \chi}\right)$ | Rule of Exportation | 1 |
Using substitution instances leads us back to:
- $\vdash \left({p \implies q}\right) \implies \left({\left({q \implies r}\right) \implies \left({p \implies r}\right)}\right)$
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\psi \land \phi$ | P | (None) | ||
| 2 | 1 | $\phi \land \psi$ | Rule of Commutation | 1 | ||
| 3 | 1 | $\chi$ | $\textrm{HS}$ | 2 | See the result above | |
| 4 | $\left({\psi \land \phi}\right) \implies \chi$ | $\implies \mathcal I$ | 1, 3 | Assumption discharged | ||
| 2 | $\psi \implies \left({\phi \implies \chi}\right)$ | Rule of Exportation | 4 |
Using substitution instances leads us back to:
- $\vdash \left({q \implies r}\right) \implies \left({\left({p \implies q}\right) \implies \left({p \implies r}\right)}\right)$
$\blacksquare$
Proof by Truth Table
We apply the Method of Truth Tables to the propositions in turn.
As can be seen for all models by inspection, where the truth values under the main connectives on the LHS is $T$, that under the one on the RHS is also $T$:
$\begin{array}{|ccccccc||ccc|} \hline
(p & \implies & q) & \land & (q & \implies & r) & p & \implies & r \\
\hline
F & T & F & T & F & T & F & F & T & F \\
F & T & F & T & F & T & T & F & T & T \\
F & T & T & F & T & F & F & F & T & F \\
F & T & T & T & T & T & T & F & T & T \\
T & F & F & F & F & T & F & T & F & F \\
T & F & F & F & F & T & T & T & T & T \\
T & T & T & F & T & F & F & T & F & F \\
T & T & T & T & T & T & T & T & T & T \\
\hline
\end{array}$
Hence the result.
$\blacksquare$
Sources
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{I}: \S 5$: Theorems $\text{T4}, \ \text{T5}$
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 3$: Theorem $\text{T26}$
- E.J. Lemmon: Beginning Logic (1965): $\S 1.2$: Exercise $1 \ \text{(i)}$
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.13$
