Subsection 10.5.2 (00VF): The Equivalence Closure of a Relation

The equivalence closure¹ of $\mathord {\sim }_{R}$ is the relation $\smash {\mathord {\sim }^{\mathrm{eq}}_{R}}$² satisfying the following universal property:³

(★)

¹Further Terminology: Also called the equivalence relation associated to $\mathord {\sim }_{R}$.
²Further Notation: Also written $R^{\operatorname {\mathrm{eq}}}$.
³Slogan: The equivalence closure of $R$ is the smallest equivalence relation containing $R$.

Concretely, $\smash {\mathord {\sim }^{\mathrm{eq}}_{R}}$ is the equivalence relation on $A$ defined by

\begin{align*} R^{\mathrm{eq}} & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft (\webleft (R^{\mathrm{refl}}\webright )^{\mathrm{symm}}\webright )^{\mathrm{trans}}\\ & = \webleft (\webleft (R^{\mathrm{symm}}\webright )^{\mathrm{trans}}\webright )^{\mathrm{refl}}\\ & = \left\{ \webleft (a,b\webright )\in A\times B\ \middle |\ \begin{aligned} & \text{there exists $\webleft (x_{1},\ldots ,x_{n}\webright )\in R^{\times n}$ satisfying at}\\[-2.5pt]& \text{least one of the following conditions:}\\[7.5pt]& \mspace {25mu}\rlap {\text{1.}}\mspace {22.5mu}\text{The following conditions are satisfied:}\\[7.5pt]& \mspace {50mu}\rlap {\text{(a)}}\mspace {30mu}\text{We have $a\sim _{R}x_{1}$ or $x_{1}\sim _{R}a$;}\\ & \mspace {50mu}\rlap {\text{(b)}}\mspace {30mu}\text{We have $x_{i}\sim _{R}x_{i+1}$ or $x_{i+1}\sim _{R}x_{i}$}\\[-2.5pt]& \mspace {81.25mu}\text{for each $1\leq i\leq n-1$;}\\ & \mspace {50mu}\rlap {\text{(c)}}\mspace {30mu}\text{We have $b\sim _{R}x_{n}$ or $x_{n}\sim _{R}b$;}\\[7.5pt]& \mspace {25mu}\rlap {\text{2.}}\mspace {22.5mu}\text{We have $a=b$.}\end{aligned} \right\} .\end{align*}

From the universal properties of the reflexive, symmetric, and transitive closures of a relation (Definition 10.2.2.1.1, Definition 10.3.2.1.1, and Definition 10.4.2.1.1), we see that it suffices to prove that:

1.
The symmetric closure of a reflexive relation is still reflexive.
2.
The transitive closure of a symmetric relation is still symmetric.

which are both clear.

Let $R$ be a relation on $A$.

1.
Adjointness. We have an adjunction
witnessed by a bijection of sets

\[ \mathbf{Rel}^{\operatorname {\mathrm{eq}}}\webleft (R^{\mathrm{eq}},S\webright ) \cong \mathbf{Rel}\webleft (R,S\webright ), \]

natural in $R\in \operatorname {\mathrm{Obj}}\webleft (\mathbf{Rel}^{\operatorname {\mathrm{eq}}}\webleft (A,B\webright )\webright )$ and $S\in \operatorname {\mathrm{Obj}}\webleft (\mathbf{Rel}\webleft (A,B\webright )\webright )$.
2.
The Equivalence Closure of an Equivalence Relation. If $R$ is an equivalence relation, then $R^{\mathrm{eq}}=R$.
3.
Idempotency. We have

\[ \webleft (R^{\mathrm{eq}}\webright )^{\mathrm{eq}} = R^{\mathrm{eq}}. \]

Item 1: Adjointness

This is a rephrasing of the universal property of the equivalence closure of a relation, stated in Definition 10.5.2.1.1.

Item 2: The Equivalence Closure of an Equivalence Relation

Clear.

Item 3: Idempotency

This follows from Item 2.

The Clowder Project

10.5.2 The Equivalence Closure of a Relation