# Extended Transitivity

Jump to navigation
Jump to search

## Theorem

Let $S$ be a set.

Let $\mathcal R$ be a transitive relation on $S$.

Let $\mathcal R^=$ be the reflexive closure of $\mathcal R$.

Let $a, b, c \in S$.

Then:

\((1):\quad\) | \(\displaystyle \left({ a \mathrel{\mathcal R} b }\right) \land \left({ b \mathrel{\mathcal R} c }\right)\) | \(\implies\) | \(\displaystyle a \mathrel{\mathcal R} c\) | ||||||||||

\((2):\quad\) | \(\displaystyle \left({ a \mathrel{\mathcal R} b }\right) \land \left({ b \mathrel{\mathcal R^=} c }\right)\) | \(\implies\) | \(\displaystyle a \mathrel{\mathcal R} c\) | ||||||||||

\((3):\quad\) | \(\displaystyle \left({ a \mathrel{\mathcal R^=} b }\right) \land \left({ b \mathrel{\mathcal R} c }\right)\) | \(\implies\) | \(\displaystyle a \mathrel{\mathcal R} c\) | ||||||||||

\((4):\quad\) | \(\displaystyle \left({ a \mathrel{\mathcal R^=} b }\right) \land \left({ b \mathrel{\mathcal R^=} c }\right)\) | \(\implies\) | \(\displaystyle a \mathrel{\mathcal R^=} c\) |

## Proof

$(1)$ follows from the definition of a transitive relation.

$(4)$ follows from Reflexive Closure of Transitive Relation is Transitive.

Suppose that:

- $\left({ a \mathrel{\mathcal R} b }\right) \land \left({ a \mathrel{\mathcal R^=} c }\right)$

By the definition of reflexive closure:

- $b \mathrel{\mathcal R} c$ or $b = c$

If $b=c$, then since a $\mathrel{\mathcal R} b$:

- $a \mathrel{\mathcal R} c$

If $a \mathrel{\mathcal R} c$ then by transitivity of $\mathcal R$:

- $a \mathrel{\mathcal R} c$

Thus $(2)$ holds.

A similar arguments proves that $(3)$ holds as well.

$\blacksquare$