3
$\begingroup$

From Mac Lane's Category Theory:

The coequalizer of two functions $f,g: X \rightarrow Y$ is the projection $p: Y \rightarrow Y/E$ on the quotient set of $Y$ by the least equivalence relation $E \subset Y \times Y$ which contains all pairs $\langle fx, gx \rangle$ for $x \in X.$

I'm having trouble understanding what $$\text{"the least equivalence relation $E \subset Y \times Y$ which contains all pairs $\langle fx, gx \rangle$ for $x \in X$"}$$

means.

If $X$ is a set and $E$ is an equivalence relation on $X$, then $X/E= \{ [x] : x \in X\}$ where $[x]=\{x' \in X: x' E \space x\}$.

How does the above quotation translate into an equivalence class definition?

$\endgroup$
4
$\begingroup$

Here "least" is meant in the sense of the subset relation. So $E$ is the equivalence relation on $Y$ which contains all pairs $\langle fx, gx \rangle$ for $x \in X$, and such that if $E'$ is any equivalence relation on $Y$ with the same property, then $E\subseteq E'$. Or, if you like, $E$ is the intersection of all equivalence relations on $Y$ which contain all pairs $\langle fx, gx \rangle$ for $x \in X$.

Describing this equivalence relation explicitly in general is a bit nasty. Essentially, you take the set of all ordered pairs which can be "generated" from those of the form $\langle fx, gx \rangle$ using reflexivity, symmetry, and transitivity. Explicitly, we have $\langle a,b\rangle\in E$ iff there exists $n\in\mathbb{N}$ and a sequence of elements $c_0,\dots,c_n\in Y$ with $c_0=a$, $c_n=b$, and for each $i<n$, either $\langle c_i,c_{i+1}\rangle$ or $\langle c_{i+1},c_i\rangle$ is of the form $\langle fx,gx\rangle$ for some $x\in X$.

$\endgroup$
  • $\begingroup$ Here $n=0$ has to be allowed to get reflexivity for the elements that are neither in the image of $f$ nor of $g$. $\endgroup$ – Daniel Schepler Dec 29 '17 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.