Last night, I came across a simple propositional logic problem concerned with
the validity of the statement:

\[
\bigl((A \implies B) \land (B \implies C)\bigr) \iff (A \implies C).
\]

At first, I thought it is valid. But on drawing the truth table, I was
surprised to see that it isn't valid.

\(A\) | \(B\) | \(C\) |
\(A \implies B\) | \(B \implies C\) | \(A \implies C\) |
\((A \implies B) \land (B \implies C)\) |
\(\bigl((A \implies B) \land (B \implies C)\bigr)\) \(\iff\) \((A \implies C)\) |

T | T | T |
T | T | T |
T |
T |

T | T | F |
T | F | F |
F |
T |

T | F | T |
F | T | T |
F |
F |

T | F | F |
F | T | F |
F |
T |

F | T | T |
T | T | T |
T |
T |

F | T | F |
T | F | T |
F |
F |

F | F | T |
T | T | T |
T |
T |

F | F | F |
T | T | T |
T |
T |

My intuition had failed. The truth table shows that there are two cases in
which the statement is false.

### Case 1: \((A \implies C) \land (B \implies C) \land \lnot(A \implies B)\)

In this case, \(A\) implies \(C\) and \(B\) implies \(C\), but \(A\)
does not imply \(B\). This corresponds to the third row in the truth
table. It makes sense. Two things can imply a third thing but they need
not imply each other. For example, rain may imply wet soil and snow may
imply wet soil as well, but rain need not imply snow. Here is another
example that demonstrates this.

The following two statements are true for any integer \(x\).

\[
4 \mid x \implies 2 \mid x. \\
6 \mid x \implies 2 \mid x.
\]

But the following statement is false when \(x \equiv 4 \pmod{12}\) or
\(x \equiv 8 \pmod{12}\).

\[
4 \mid x \implies 6 \mid x.
\]

In other words, if an integer is a multiple of \(4\) as well as a multiple
of \(6\), then it is also a multiple of \(2\). But this is not equivalent to
claiming that if an integer is a multiple of \(4\), then it is also a multiple
of \(6\). Such a claim is not correct as we can confirm for
\(x \in \{4, 8, 16, 20, 28, 32, \dots\}\).

### Case 2: \((A \implies B) \land (A \implies C) \land \lnot(B \implies C)\)

In this case, \(A\) implies \(B\) as well as \(C\) but \(B\) does not
imply \(C\). This corresponds to the sixth row in the truth table. It
makes sense as well. One thing can imply two other things but those two
things need not imply each other. For example, rain may imply wet soil
and flooded rivers but wet soil need not imply flooded rivers. The soil
could be wet due to irrigation sprinklers. Once again, here is a
mathematical example to demonstrate this.

The following two statements are true for any integer x.

\[
6 \mid x \implies 2 \mid x. \\
6 \mid x \implies 3 \mid x.
\]

But the following statement is false when \(x\) is an odd multiple of
\(3\).

\[
2 \mid x \implies 3 \mid x.
\]

In other words, if an integer is a multiple of 6, then it is a multiple
of 2 as well as 3. But this is not equivalent to claiming that if an
integer is a multiple of 2, then it is also a multiple of 3. Such a
claim is clearly false as we can confirm for \(x \in \{3, 9, 15, 21, \dots\}\).

### Encoding intuition correctly

My intuition incorrectly concluded that the \(\bigl((A \implies B) \land
(B \implies C)\bigr) \iff (A \implies C)\) is valid because I was not
translating the given statement correctly in my mind. I was thinking
that if \(A\) implies \(B\) and \(B\) implies \(C\), of course \(A\)
must also imply \(C\). This is true but this is not what the given
statement represents. The given statement means something more than
this. In addition to what I thought, it also means that if \(A\) does
not imply \(B\) or \(B\) does not imply \(C\), then \(A\) does not imply
\(C\) as well. This however doesn't happen. The truth table shows that
even though \(A\) does not imply \(B\) or \(B\) does not imply \(C\), it
is possible that \(A\) implies \(C\).

As far as my intuition is concerned, the following would be the right way to
represent what I was thinking.

\[
\bigl((A \implies B) \land (B \implies C)\bigr) \implies (A \implies C).
\]

Indeed, this statement is valid as can be seen from the truth table below.

\(A\) | \(B\) | \(C\) |
\(A \implies B\) | \(B \implies C\) | \(A \implies C\) |
\((A \implies B) \land (B \implies C)\) |
\(\bigl((A \implies B) \land (B \implies C)\bigr)\) \(\implies\) \((A \implies C)\) |

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 |