Implication Properties

Theorems

The conditional operator has the following counter-intuitive properties:

• $q \vdash p \implies q$

If something is true, then anything implies it.

• $\neg p \vdash p \implies q$

If something is false, then it implies anything.

These results can be formalized alternatively as part of the following set:

• $\top \dashv \vdash p \implies \top$, or just $\vdash p \implies \top$
• $p \dashv \vdash \top \implies p$

• $\top \dashv \vdash \bot \implies p$, or just $\vdash \bot \implies p$
• $\neg p \dashv \vdash p \implies \bot$

Alternative rendition

These can alternatively be rendered as:

• $\vdash q \implies \left({p \implies q}\right)$

• $\vdash \neg p \implies \left({p \implies q}\right)$

They can be seen to be logically equivalent to the forms above by application of the Rule of Implication and Modus Ponendo Ponens.

Proofs

Proof by Natural deduction

These are proved by the Tableau method.

$q \vdash p \implies q$:

Line		Pool	Formula	Rule	Depends upon
1		1	$q$	P	(None)
2		1	$\neg p \lor q$	$\lor \mathcal I_2$	1
3		1	$p \implies q$	Rule of Material Implication	1

$\blacksquare$

$\neg p \vdash p \implies q$:

Line		Pool	Formula	Rule	Depends upon
1		1	$\neg p$	P	(None)
2		1	$\neg p \lor q$	$\lor \mathcal I_1$	1
3		1	$p \implies q$	Rule of Material Implication	1

$\blacksquare$

---

Proof by Truth Table

We apply the Method of Truth Tables to the propositions.

• $q \vdash p \implies q$ and $\neg p \vdash p \implies q$:

As can be seen for all models by inspection, where the truth value in the relevant column on the LHS is $T$, that under the one on the RHS is also $T$:

$\begin{array}{|c||ccc|} \hline q & p & \implies & q \\ \hline F & F & T & F \\ T & F & T & T \\ F & T & F & F \\ T & T & T & T \\ \hline \end{array}$

$\blacksquare$

$\begin{array}{|cc||ccc|} \hline \neg & p & p & \implies & q \\ \hline T & F & F & T & F \\ T & F & F & T & T \\ F & F & T & F & F \\ F & F & T & T & T \\ \hline \end{array}$

$\blacksquare$

• $\top \dashv \vdash p \implies \top$ and $p \dashv \vdash \top \implies p$:

As can be seen by inspection, the truth values in the appropriate columns match for all models:

$\begin{array}{|c|ccc||c|ccc|} \hline \top & p & \implies & \top & p & \top & \implies & p \\ \hline T & F & T & T & F & T & F & F \\ T & T & T & T & T & T & T & T \\ \hline \end{array}$

$\blacksquare$

• $\top \dashv \vdash \bot \implies p$ and $\neg p \dashv \vdash p \implies \bot$:

As can be seen by inspection, the truth values in the appropriate columns match for all models:

$\begin{array}{|c|ccc||cc|ccc|} \hline \top & \bot & \implies & p & \neg & p & p & \implies & \bot\\ \hline T & F & T & F & T & F & F & T & F \\ T & F & T & T & F & T & T & F & F \\ \hline \end{array}$

$\blacksquare$

Comment

These counter-intuitive results have caused debate and puzzlement among philosophers for millennia.

In particular, the result $\neg p \vdash p \implies q$ is known as a vacuous truth. It is exemplified by the (rhetorical) argument:

"If England win the Ashes this year, then I'm a monkey's uncle."

(Alert viewers will note that in 2009 my sister's daughter was indeed a simian. The trend continued into 2011.)

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{I}: \S 5$: Theorem $\text{T2}, \ \text{T18}$
• Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.1$: Exercise $1.5: 2 \ \text {(b)}$