Diagonal Relation is Transitive

From ProofWiki
Jump to: navigation, search

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$