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

Style	Class	Font	Theorem Environments
Style 1	`book`	Alegreya Sans	`tcbthm`
Style 2	`book`	Alegreya Sans	`amsthm`
Style 3	`book`	Arno*	`amsthm`
Style 4	`book`	Computer Modern	`amsthm`

The equivalence closure^[1] of $\mathord {\sim }_{R}$ is the relation $\smash {\mathord {\sim }^{\mathrm{eq}}_{R}}$^[2] satisfying the following universal property:^[3]

Given another equivalence relation $\mathord {\sim }_{S}$ on $A$ such that $R\subset S$, there exists an inclusion $\smash {\mathord {\sim }^{\mathrm{eq}}_{R}}\subset \mathord {\sim }_{S}$.

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}}\\ & = \webleft\{ \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} \webright\} .\end{align*}

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

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

which are both clear.

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

Adjointness. We have an adjunction
witnessed by a bijection of sets
\[ \mathbf{Rel}^{\text{eq}}\webleft (R^{\mathrm{eq}},S\webright ) \cong \mathbf{Rel}\webleft (R,S\webright ), \]

natural in $R\in \text{Obj}\webleft (\mathbf{Rel}^{\text{eq}}\webleft (A,B\webright )\webright )$ and $S\in \text{Obj}\webleft (\mathbf{Rel}\webleft (A,B\webright )\webright )$.
The Equivalence Closure of an Equivalence Relation. If $R$ is an equivalence relation, then $R^{\mathrm{eq}}=R$.
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 7.4.2.1.1.

Item 2: The Equivalence Closure of an Equivalence Relation

Clear.

Item 3: Idempotency

This follows from Item 2.

Footnotes

[1] Further Terminology: Also called the equivalence relation associated to $\mathord {\sim }_{R}$.

[2] Further Notation: Also written $R^{\text{eq}}$.

[3] Slogan: The equivalence closure of $R$ is the smallest equivalence relation containing $R$.

The Clowder Project

7.4.2 The Equivalence Closure of a Relation

Footnotes