# What is “the least equivalence relation $E \subset Y \times Y$ which contains all pairs $\langle fx, gx \rangle$ for $x \in X$”?

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?

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$.
• Here $n=0$ has to be allowed to get reflexivity for the elements that are neither in the image of $f$ nor of $g$. – Daniel Schepler Dec 29 '17 at 23:36