Let $A$ be a set and let $R$ be a relation on $A$.
The quotient of $X$ by $R$ is the set $X/\mathord {\sim }_{R}$ defined by
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 $\webleft [a\webright ]$ of $X$ under $R$ are well-behaved:
Reflexivity. If $R$ is reflexive, then, for each $a\in X$, we have $a\in \webleft [a\webright ]$.
Symmetry. The equivalence class $\webleft [a\webright ]$ of an element $a$ of $X$ is defined by
but we could equally well define
instead. This is not a problem when $R$ is symmetric, as we then have $\webleft [a\webright ]=\webleft [a\webright ]'$.1
Transitivity. If $R$ is transitive, then $\webleft [a\webright ]$ and $\webleft [b\webright ]$ are disjoint iff $a\nsim _{R}b$, and equal otherwise.
, .
Let $f\colon X\to Y$ be a function and let $R$ be a relation on $X$.
As a Coequaliser. We have an isomorphism of sets
where $\mathord {\sim }^{\mathrm{eq}}_{R}$ is the equivalence relation generated by $\mathord {\sim }_{R}$.
As a Pushout. We have an isomorphism of sets1
The First Isomorphism Theorem for Sets. We have an isomorphism of sets2,3
Descending Functions to Quotient Sets, I. Let $R$ be an equivalence relation on $X$. The following conditions are equivalent:
There exists a map
making the diagram
We have $R\subset \mathrm{Ker}\webleft (f\webright )$.
For each $x,y\in X$, if $x\sim _{R}y$, then $f\webleft (x\webright )=f\webleft (y\webright )$.
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
Descending Functions to Quotient Sets, III. Let $R$ be an equivalence relation on $X$. We have a bijection
natural in $X,Y\in \operatorname {\mathrm{Obj}}\webleft (\mathsf{Sets}\webright )$, given by the assignment $f\mapsto \overline{f}$ of Item 4 and Item 5, where $\operatorname {\mathrm{Hom}}^{R}_{\mathsf{Sets}}\webleft (X,Y\webright )$ is the set defined by
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:
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:
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:
The map $f$ satisfies the equivalent conditions of Item 4:
There exists a map
making the diagram
For each $x,y\in X$, if $x\sim ^{\mathrm{eq}}_{R}y$, then $f\webleft (x\webright )=f\webleft (y\webright )$.
For each $x,y\in X$, if $x\sim _{R}y$, then $f\webleft (x\webright )=f\webleft (y\webright )$.
of .
Conversely, suppose that, for each $x,y\in X$, if $x\sim _{R}y$, then $f\webleft (x\webright )=f\webleft (y\webright )$. 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\webleft (x\webright )=f\webleft (y\webright )$ trivially; otherwise, we have
and $f\webleft (x\webright )=f\webleft (y\webright )$, as we wanted to show.
