# Diagonal Relation is Transitive

## Theorem

The diagonal relation $\Delta_S$ on a set $S$ is a transitive relation in $S$.

## Proof

\(\, \displaystyle \forall x, y, z \in S: \, \) | \(\displaystyle \tuple {x, y}\) | \(\in\) | \(\displaystyle \Delta_S \land \tuple {y, z} \in \Delta_S\) | $\quad$ | $\quad$ | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x\) | \(=\) | \(\displaystyle y \land y = z\) | $\quad$ Definition of Diagonal Relation | $\quad$ | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x\) | \(=\) | \(\displaystyle z\) | $\quad$ Equality is Transitive | $\quad$ | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \tuple {x, z}\) | \(\in\) | \(\displaystyle \Delta_S\) | $\quad$ Definition of Diagonal Relation | $\quad$ |

So $\Delta_S$ is transitive.

$\blacksquare$