Diagonal Relation is Transitive
Jump to navigation
Jump to search
Theorem
The diagonal relation $\Delta_S$ on a set $S$ is a transitive relation in $S$.
Proof
\(\ds \forall x, y, z \in S: \, \) | \(\ds \tuple {x, y}\) | \(\in\) | \(\ds \Delta_S \land \tuple {y, z} \in \Delta_S\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds x\) | \(=\) | \(\ds y \land y = z\) | Definition of Diagonal Relation | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds x\) | \(=\) | \(\ds z\) | Equality is Transitive | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {x, z}\) | \(\in\) | \(\ds \Delta_S\) | Definition of Diagonal Relation |
So $\Delta_S$ is transitive.
$\blacksquare$