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

\(\ds \forall x \in S: \, \) \(\ds x\) \(=\) \(\ds x\) Definition of Equals
\(\ds \leadsto \ \ \) \(\ds \tuple {x, x}\) \(\in\) \(\ds \Delta_S\) Definition of Diagonal Relation

So $\Delta_S$ is reflexive.

$\Box$


Symmetric

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

So $\Delta_S$ is symmetric.

$\Box$


Transitive

\(\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$


Examples

Equality of Integers is Equivalence

Let $\Z$ denote the set of integers.

Let $\RR$ denote the relation on $\Z$ defined as:

$\forall x, y \in \Z: x \mathrel \RR y \iff x = y$

Then $\RR$ is an equivalence relation such that the equivalence classes are singletons.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Diagonal_Relation_is_Equivalence&oldid=614495"