Hypothetical syllogism

In classical logic, hypothetical syllogism is a valid argument form which is a syllogism having a conditional statement for one or both of its premises.

An example in English:

If I do not wake up, then I cannot go to work.

If I cannot go to work, then I will not get paid.

Therefore, if I do not wake up, then I will not get paid.

The term originated with Theophrastus.[1]

Propositional logic

In propositional logic, hypothetical syllogism is the name of a valid rule of inference (often abbreviated HS and sometimes also called the chain argument, chain rule, or the principle of transitivity of implication). Hypothetical syllogism is one of the rules in classical logic that is not always accepted in certain systems of non-classical logic. The rule may be stated:

${\displaystyle {\frac {P\to Q,Q\to R}{\therefore P\to R}}}$

where the rule is that whenever instances of "${\displaystyle P\to Q}$", and "${\displaystyle Q\to R}$" appear on lines of a proof, "${\displaystyle P\to R}$" can be placed on a subsequent line.

Hypothetical syllogism is closely related and similar to disjunctive syllogism, in that it is also type of syllogism, and also the name of a rule of inference.

Formal notation

The hypothetical syllogism inference rule may be written in sequent notation, which amounts to a specialization of the cut rule:

${\displaystyle {\frac {P\vdash Q\quad Q\vdash R}{P\vdash R}}}$

where ${\displaystyle \vdash }$ is a metalogical symbol and ${\displaystyle A\vdash B}$ meaning that ${\displaystyle B}$ is a syntactic consequence of ${\displaystyle A}$ in some logical system;

and expressed as a truth-functional tautology or theorem of propositional logic:

${\displaystyle ((P\to Q)\land (Q\to R))\to (P\to R)}$

where ${\displaystyle P}$, ${\displaystyle Q}$, and ${\displaystyle R}$ are propositions expressed in some formal system.

Proof

Step	Proposition	Derivation
1	${\displaystyle (P\to Q)\land (Q\to R)}$	Given
2	${\displaystyle (\neg P\lor Q)\land (\neg Q\lor R)}$	Material implication
3	${\displaystyle ((\neg P\lor Q)\land \neg Q)\lor ((\neg P\lor Q)\land R)}$	Distributivity
4	${\displaystyle ((\neg P\lor Q)\land \neg Q)\lor R}$	Conjunction elimination (3)
5	${\displaystyle ((\neg P\land \neg Q)\lor (Q\land \neg Q))\lor R}$	Distributivity
6	${\displaystyle \neg (Q\land \neg Q)}$	Law of noncontradiction
7	${\displaystyle (\neg P\land \neg Q)\lor R}$	Disjunctive syllogism (5,6)
8	${\displaystyle \neg P\lor R}$	Conjunction elimination (7)
9	${\displaystyle P\to R}$	Material implication

Alternative forms

An alternative form of hypothetical syllogism, more useful for classical propositional calculus systems with implication and negation (i.e. without the conjunction symbol), is the following:

(HS1) ${\displaystyle (Q\to R)\to ((P\to Q)\to (P\to R))}$

Yet another form is:

(HS2) ${\displaystyle (P\to Q)\to ((Q\to R)\to (P\to R))}$

Proof

An example of the proofs of these theorems in such systems is given below. We use two of the three axioms used in one of the popular systems described by Jan Łukasiewicz. The proofs relies on two out of the three axioms of this system:

(A1) ${\displaystyle \phi \to \left(\psi \to \phi \right)}$

(A2) ${\displaystyle \left(\phi \to \left(\psi \rightarrow \xi \right)\right)\to \left(\left(\phi \to \psi \right)\to \left(\phi \to \xi \right)\right)}$

The proof of the (HS1) is as follows:

(1) ${\displaystyle ((p\to (q\to r))\to ((p\to q)\to (p\to r)))\to ((q\to r)\to ((p\to (q\to r))\to ((p\to q)\to (p\to r))))}$       (instance of (A1))

(2) ${\displaystyle (p\to (q\to r))\to ((p\to q)\to (p\to r))}$       (instance of (A2))

(3) ${\displaystyle (q\to r)\to ((p\to (q\to r))\to ((p\to q)\to (p\to r)))}$       (from (1) and (2) by modus ponens)

(4) ${\displaystyle ((q\to r)\to ((p\to (q\to r))\to ((p\to q)\to (p\to r))))\to (((q\to r)\to (p\to (q\to r)))\to ((q\to r)\to ((p\to q)\to (p\to r))))}$       (instance of (A2))

(5) ${\displaystyle ((q\to r)\to (p\to (q\to r)))\to ((q\to r)\to ((p\to q)\to (p\to r)))}$       (from (3) and (4) by modus ponens)

(6) ${\displaystyle (q\to r)\to (p\to (q\to r))}$       (instance of (A1))

(7) ${\displaystyle (q\to r)\to ((p\to q)\to (p\to r))}$ (from (5) and (6) by modus ponens)

The proof of the (HS2) is given here.

As a metatheorem

Whenever we have two theorems of the form ${\displaystyle T_{1}=(Q\to R)}$ and ${\displaystyle T_{2}=(P\to Q)}$, we can prove ${\displaystyle (P\to R)}$ by the following steps:

(1) ${\displaystyle (Q\to R)\to ((P\to Q)\to (P\to R)))}$       (instance of the theorem proved above)

(2) ${\displaystyle Q\to R}$       (instance of (T1))

(3) ${\displaystyle (P\to Q)\to (P\to R)}$       (from (1) and (2) by modus ponens)

(4) ${\displaystyle P\to Q}$       (instance of (T2))

(5) ${\displaystyle P\to R}$       (from (3) and (4) by modus ponens)

See also

• Modus ponens
• Modus tollens
• Affirming the consequent
• Denying the antecedent
• Transitive relation

References

1. "History of Logic: Theophrastus of Eresus" in Encyclopædia Britannica Online.

External links

• Philosophy Index: Hypothetical Syllogism