Definition 10.6.2.1.1 (02B3): Quotients of Sets by Equivalence Relations

10.6.2 Quotients of Sets by Equivalence Relations

Let $A$ be a set and let $R$ be a relation on $A$.

Definition 10.6.2.1.1 ▶ Quotients of Sets by Equivalence Relations

The quotient of $X$ by $R$ is the set $X/\mathord {\sim }_{R}$ defined by

\[ X/\mathord {\sim }_{R}\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ [a]\in \mathcal{P}(X)\ \middle |\ a\in X\right\} . \]

Remark 10.6.2.1.2 ▶ Why Use “Equivalence” Relations for Quotient Sets

The reason we define quotient sets for equivalence relations only is that each of the properties of being an equivalence relation—reflexivity, symmetry, and transitivity—ensures that the equivalences classes $[a]$ of $X$ under $R$ are well-behaved:

•
Reflexivity. If $R$ is reflexive, then, for each $a\in X$, we have $a\in [a]$.
•
Symmetry. The equivalence class $[a]$ of an element $a$ of $X$ is defined by

\[ [a]\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ x\in X\ \middle |\ x\sim _{R}a\right\} , \]

but we could equally well define

\[ [a]'\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ x\in X\ \middle |\ a\sim _{R}x\right\} \]

instead. This is not a problem when $R$ is symmetric, as we then have $[a]=[a]'$.¹
•
Transitivity. If $R$ is transitive, then $[a]$ and $[b]$ are disjoint iff $a\nsim _{R}b$, and equal otherwise.

¹When categorifying equivalence relations, one finds that $[a]$ and $[a]'$ correspond to presheaves and copresheaves; see , .

Proposition 10.6.2.1.3 ▶ Properties of Quotient Sets

Let $f\colon X\to Y$ be a function and let $R$ be a relation on $X$.

1.
As a Coequaliser. We have an isomorphism of sets

\[ X/\mathord {\sim }^{\mathrm{eq}}_{R}\cong \operatorname {\mathrm{CoEq}}(R\hookrightarrow X\times X\stackrel{\stackrel{\operatorname {\mathrm{\mathrm{pr}}}_{1}}{\rightarrow }}{\stackrel{\rightarrow }{\scriptsize \operatorname {\mathrm{\mathrm{pr}}}_{2}}}X), \]

where $\mathord {\sim }^{\mathrm{eq}}_{R}$ is the equivalence relation generated by $\mathord {\sim }_{R}$.
2.
As a Pushout. We have an isomorphism of sets¹
where $\mathord {\sim }^{\mathrm{eq}}_{R}$ is the equivalence relation generated by $\mathord {\sim }_{R}$.
3.
The First Isomorphism Theorem for Sets. We have an isomorphism of sets^2,3

\[ X/\mathord {\sim }_{\mathrm{Ker}(f)} \cong \mathrm{Im}(f). \]
4.
Descending Functions to Quotient Sets, I. Let $R$ be an equivalence relation on $X$. The following conditions are equivalent:
1. (a)
  There exists a map
  
  \[ \overline{f}\colon X/\mathord {\sim }_{R}\to Y \]
  
  making the diagram
  commute.
2. (b)
  We have $R\subset \mathrm{Ker}(f)$.
3. (c)
  For each $x,y\in X$, if $x\sim _{R}y$, then $f(x)=f(y)$.
5.
Descending Functions to Quotient Sets, II. Let $R$ be an equivalence relation on $X$. If the conditions of Item 4 hold, then $\overline{f}$ is the unique map making the diagram
commute.
6.
Descending Functions to Quotient Sets, III. Let $R$ be an equivalence relation on $X$. We have a bijection

\[ \operatorname {\mathrm{Hom}}_{\mathsf{Sets}}(X/\mathord {\sim }_{R},Y)\cong \operatorname {\mathrm{Hom}}^{R}_{\mathsf{Sets}}(X,Y), \]

natural in $X,Y\in \operatorname {\mathrm{Obj}}(\mathsf{Sets})$, given by the assignment $f\mapsto \overline{f}$ of Item 4 and Item 5, where $\operatorname {\mathrm{Hom}}^{R}_{\mathsf{Sets}}(X,Y)$ is the set defined by

\[ \operatorname {\mathrm{Hom}}^{R}_{\mathsf{Sets}}(X,Y)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ f\in \operatorname {\mathrm{Hom}}_{\mathsf{Sets}}(X,Y)\ \middle |\ \begin{aligned} & \text{for each $x,y\in X$,}\\ & \text{if $x\sim _{R}y$, then}\\ & \text{$f(x)=f(y)$}\end{aligned} \right\} . \]
7.
Descending Functions to Quotient Sets, IV. Let $R$ be an equivalence relation on $X$. If the conditions of Item 4 hold, then the following conditions are equivalent:
1. (a)
  The map $\overline{f}$ is an injection.
2. (b)
  We have $R=\mathrm{Ker}(f)$.
3. (c)
  For each $x,y\in X$, we have $x\sim _{R}y$ iff $f(x)=f(y)$.
8.
Descending Functions to Quotient Sets, V. Let $R$ be an equivalence relation on $X$. If the conditions of Item 4 hold, then the following conditions are equivalent:
1. (a)
  The map $f\colon X\to Y$ is surjective.
2. (b)
  The map $\overline{f}\colon X/\mathord {\sim }_{R}\to Y$ is surjective.
9.
Descending Functions to Quotient Sets, VI. Let $R$ be a relation on $X$ and let $\mathord {\sim }^{\mathrm{eq}}_{R}$ be the equivalence relation associated to $R$. The following conditions are equivalent:
1. (a)
  The map $f$ satisfies the equivalent conditions of Item 4:
  - •
    There exists a map
    
    \[ \overline{f}\colon X/\mathord {\sim }^{\mathrm{eq}}_{R}\to Y \]
    
    making the diagram
    commute.
  - •
    For each $x,y\in X$, if $x\sim ^{\mathrm{eq}}_{R}y$, then $f(x)=f(y)$.
2. (b)
  For each $x,y\in X$, if $x\sim _{R}y$, then $f(x)=f(y)$.

¹Dually, we also have an isomorphism of sets
²Further Terminology: The set $X/\mathord {\sim }_{\mathrm{Ker}(f)}$ is often called the coimage of $f$, and denoted by $\mathrm{CoIm}(f)$.
³In a sense this is a result relating the monad in $\boldsymbol {\mathsf{Rel}}$ induced by $f$ with the comonad in $\boldsymbol {\mathsf{Rel}}$ induced by $f$, as the kernel and image
\begin{gather*} \mathrm{Ker}(f)\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X,\\ \mathrm{Im}(f)\subset Y \end{gather*}
of $f$ are the underlying functors of (respectively) the induced monad and comonad of the adjunction
of Chapter 9: Constructions With Relations, of .

Proof of Proposition 10.6.2.1.3.

Item 1: As a Coequaliser

Omitted.

Item 2: As a Pushout

Omitted.

Item 3: The First Isomorphism Theorem for Sets

Omitted.

Item 4: Descending Functions to Quotient Sets, I

See [Proof Wiki Contributors, Condition For Mapping From Quotient Set To Be Well-Defined — Proof Wiki].

Item 5: Descending Functions to Quotient Sets, II

See [Proof Wiki Contributors, Mapping From Quotient Set When Defined Is Unique — Proof Wiki].

Item 6: Descending Functions to Quotient Sets, III

This follows from Item 5 and Item 6.

Item 7: Descending Functions to Quotient Sets, IV

See [Proof Wiki Contributors, Condition For Mapping From Quotient Set To Be An Injection— Proof Wiki].

Item 8: Descending Functions to Quotient Sets, V

See [Proof Wiki Contributors, Condition For Mapping from Quotient Set To Be A Surjection — Proof Wiki].

Item 9: Descending Functions to Quotient Sets, VI

The implication Item 8a$\implies $Item 8b is clear.

Conversely, suppose that, for each $x,y\in X$, if $x\sim _{R}y$, then $f(x)=f(y)$. Spelling out the definition of the equivalence closure of $R$, we see that the condition $x\sim ^{\mathrm{eq}}_{R}y$ unwinds to the following:

(★)

•
The following conditions are satisfied:
- •
  We have $x\sim _{R}x_{1}$ or $x_{1}\sim _{R}x$;
- •
  We have $x_{i}\sim _{R}x_{i+1}$ or $x_{i+1}\sim _{R}x_{i}$ for each $1\leq i\leq n-1$;
- •
  We have $y\sim _{R}x_{n}$ or $x_{n}\sim _{R}y$;
•
We have $x=y$.

Now, if $x=y$, then $f(x)=f(y)$ trivially; otherwise, we have

\begin{align*} f(x) & = f(x_{1}),\\ f(x_{1}) & = f(x_{2}),\\ & \vdots \\ f(x_{n-1}) & = f(x_{n}),\\ f(x_{n}) & = f(y), \end{align*}

and $f(x)=f(y)$, as we wanted to show.

Statistics Cite

Noticed something off, or have any comments? Feel free to reach out!

•Email
•Discord

You can also use the contact form below: