Diagonal Relation is Equivalence

From ProofWiki
Jump to navigation Jump to search

Theorem

The diagonal relation $\Delta_S$ on a set $S$ is always an equivalence in $S$.


Proof

Checking in turn each of the criteria for equivalence:


Reflexive

\(\, \displaystyle \forall x \in S: \, \) \(\displaystyle \tuple {x, x}\) \(\in\) \(\displaystyle \Delta_S\) Definition of Diagonal Relation

So $\Delta_S$ is reflexive.

$\Box$


Symmetric

\(\, \displaystyle \forall x, y \in S: \, \) \(\displaystyle \tuple {x, y}\) \(\in\) \(\displaystyle \Delta_S\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle y\) Definition of Diagonal Relation
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(=\) \(\displaystyle x\) Equality is Symmetric
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {y, x}\) \(\in\) \(\displaystyle \Delta_S\) Definition of Diagonal Relation

So $\Delta_S$ is symmetric.

$\Box$


Transitive

\(\, \displaystyle \forall x, y, z \in S: \, \) \(\displaystyle \tuple {x, y}\) \(\in\) \(\displaystyle \Delta_S \land \tuple {y, z} \in \Delta_S\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle y \land y = z\) Definition of Diagonal Relation
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle z\) Equality is Transitive
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {x, z}\) \(\in\) \(\displaystyle \Delta_S\) Definition of Diagonal Relation

So $\Delta_S$ is transitive.

$\blacksquare$


Sources