Equivalence of Definitions of Equivalence Relation
Theorem
Let $\RR$ be a relation on a set $S$.
The following definitions of the concept of Equivalence Relation are equivalent:
Definition 1
Let $\RR$ be:
- $(1): \quad$ reflexive
- $(2): \quad$ symmetric
- $(3): \quad$ transitive
Then $\RR$ is an equivalence relation on $S$.
Definition 2
$\RR$ is an equivalence relation if and only if:
- $\Delta_S \cup \RR^{-1} \cup \RR \circ \RR \subseteq \RR$
where:
- $\Delta_S$ denotes the diagonal relation on $S$
- $\RR^{-1}$ denotes the inverse relation
- $\circ$ denotes composition of relations
Proof
Definition 1 implies Definition 2
Let $\RR$ be an equivalence relation by definition 1.
By definition, $\RR$ is reflexive, symmetric and transitive.
From Relation Contains Diagonal Relation iff Reflexive:
- $\Delta_S \subseteq \RR$
From Relation equals Inverse iff Symmetric:
- $\RR^{-1} = \RR$
and so by definition of set equality:
- $\RR^{-1} \subseteq \RR$
From Relation contains Composite with Self iff Transitive:
- $\RR \circ \RR \subseteq \RR$
From Union is Smallest Superset:
- $\Delta_S \cup \RR^{-1} \cup \RR \circ \RR \subseteq \RR$
Thus $\RR$ is an equivalence relation by definition 2.
$\Box$
Definition 2 implies Definition 1
Let $\RR$ be an equivalence relation by definition 2.
That is:
- $\Delta_S \cup \RR^{-1} \cup \RR \circ \RR \subseteq \RR$
By Union is Smallest Superset:
- $(1): \quad \Delta_S \subseteq \RR$
- $(2): \quad \RR^{-1} \subseteq \RR$
- $(3): \quad \RR \circ \RR \subseteq \RR$
From Relation Contains Diagonal Relation iff Reflexive, $(1)$ gives directly that $\RR$ is reflexive.
From Inverse Relation Equal iff Subset, $(2)$ gives that $\RR^{-1} = \RR$.
So from Relation equals Inverse iff Symmetric $\RR$ is symmetric.
From Relation contains Composite with Self iff Transitive, $(3)$ gives that $\RR$ is transitive.
So $\RR$ has been shown to be reflexive, symmetric and transitive.
Thus $\RR$ is an equivalence relation by definition 1.
$\blacksquare$
Sources
- 1967: George McCarty: Topology: An Introduction with Application to Topological Groups ... (previous) ... (next): Chapter $\text{I}$: Sets and Functions: Problem $\text{AA}$: Relations