Groupoids

We recall the notion of groupoid:
a category in which each arrow is invertible.

This is common generalization of the notions of equivalence relation
(a groupoid which is “thin”, i.e., has at most one arrow between any two objects) and
group (a groupoid with only one object).

An important source of groupoids is:
Each group action has an associated groupoid.
If $X$ is a set acted on by a group $G$, with action \[\begin{array}{c} X \times G & \to & X\\ \langle x, g \rangle &\mapsto & xg , \end{array}\] then associated groupoid has objects the elements of $X$,
and arrows the set $X \times G$, with source and targets of each arrow as follows: $$ x \xrightarrow{\textstyle \langle x,g\rangle} xg .$$ When the source, $x$ in this case, is displayed, the arrow can be denoted simply as: $$ x \xrightarrow{\textstyle g} xg .$$

---

Examples

Important examples are in combinatorics, algebra, and geometry.

In combinatorics, consider the group $S_3$
with its canonical action on $[3]$.
Of course $S_3$ is in fact the automorphism group of $[3]$,
so its six elements are normally viewed in the category of sets as loops on $[3]$,
so $S_3$ may be viewed as a subcategory of $\Set$ with one object $[3]$ and six arrows.

The groupoid associated to the action $[3]\times S_3 \to S_3$, in contrast,
has three objects, namely the elements $0,1,2$ of $[3]$,
and 18 arrows, one for each $\langle i,\sigma\rangle \in [3]\times S_3$,
with $\langle i,\sigma\rangle$ now being viewed an an arrow $$\langle i,\sigma\rangle : i \to i\sigma .$$ Thus, for example $0\in [3]$ has six arrows out of it: \[\begin{array}{} 1\\ \llap{(0,1),\,(0,1,2)}\Bigg\uparrow\\ \llap{\iota,\,(1,2) \circlearrowright\;}0 & \xrightarrow[\textstyle (0,2),\,(0,2,1)]{} & 2 ,\\ \end{array}\] and similarly for $1$ and $2$.

---

In algebra, consider the subgroup $2\Z$ of $\Z$ acting on $\Z$ through addition.
A portion of the associated groupoid may be illustrated as follows: $\def\overtwo{\buildrel 2 \over \rightarrow}$ \[\begin{array}{c} & \dots & \overtwo & -2 & \overtwo & 0 & \overtwo & 2 & \overtwo & 4 & \overtwo & 6 & \overtwo & \dots\\ \dots & \overtwo & -3 & \overtwo & -1 & \overtwo & 1 & \overtwo & 3 & \overtwo & 5 & \overtwo & \dots \end{array}\] Note that the groupoid consists of two connected components.
In fact, these components may be viewed in several ways, as

cosets	of the subgroup $2\Z$,
orbits	of a (sub)group action,
equivalence classes	of the induced equivalence relation, or
connected componentsmmm	of a graph (the underlying graph of the groupoid).

---

In geometry, consider a vector space $V$ acting on itself via addition,
\[\begin{array}{c} V\times V &\to &V\\ \langle x,v \rangle & \mapsto & x+v \end{array}\] If we apply the recipe above for defining the groupoid associated to this action,
we get precisely the picture normally drawn in elementary courses on vectors: \[ x \buildrel v \over \longrightarrow x+v .\] Of course, normally this picture is drawn with $x+v$ placed higher on the page,
with the arrow at an angle to the “$x$-axis”.
Sometimes $x$ will be called a “based vector” and $v$ a “free vector”.
But the idea is the same as in the groupoid case:
$v$ is an actor, taking $x$ to $x+v$.

Double groupoids and the twelvefold way

Fact: The $2^4 = 16$ functions from $\source{[4]=\{0,1,2,3\}}$ to $\target{\{a,b\}}$,

• when quotiented by the permutation group of the source, $S_4$,
  divide into five equivalence classes;
• when quotiented by the permutation group of the target, $S_{\{a,b\}}$,
  divide into eight equivalence classes;
• when quotiented by both,
  divide into three equivalence classes.

Challenge: Find a way to visualize those classes and the relations between them.

Solution: Apply the following construction of a double groupoid to $\homst {[4]} \Set {\{a,b\}}$. (The result.)

---

The general construction

Let $\source X$ and $\target Y$ be arbitrary sets in the category of sets, $\Set$.
Let $\boxed{\source{S_X}}$ and $\boxed{\target{S_Y}}$ be their respective groups of permutations.
Form a double groupoid as follows.

• Its 0-cells are all the functions from $\source X$ to $\target Y$,
  namely, the elements of the function set $\boxed{\homst X \Set Y}$.
• There is a vertical 1-cell for each $\boxed{\langle \source\sigma, f \rangle \in \symsX \times \homst X \Set Y = V}$.
• There is a horizontal 1-cell for each $\boxed{\langle f, \target\tau \rangle \in \homst X \Set Y \times \symtY = H}$.
• $\begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau}} & f\target\tau\\ \source{\llap{\text{s-}\sigma} \Big\downarrow} & \langle \source\sigma, f, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}}\\ \source\sigma f & \target{\xrightarrow[\displaystyle \text{t-}\tau]{}} & \source\sigma f \target\tau \end{array}$
  The sources and targets of the 1-cells are as shown in the square for 2-cells.
• There is a 2-cell for each triple $\boxed{\langle \source\sigma, f, \target\tau \rangle \in \source{S_X} \times \homst X \Set Y \times \target{S_Y}}$,
  having (horizontal and vertical source and target) as in (the square at right):
• Vertical and horizontal composition of 1-cells is obvious,
  while vertical and horizontal composition of 2-cells is by pasting.
• Vertical and horizontal associativity and identity are obvious.
• $\begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau}} & f\target\tau & \target{\xrightarrow{\displaystyle \text{t-}\tau'}} & f\target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma} \Big\downarrow} & \langle \source\sigma, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}} & \langle \source\sigma, \target{\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}}\\ \source\sigma f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau}}} & \source\sigma f \target\tau & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau'}}} & \source\sigma f \target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma'} \Big\downarrow} & \langle \source{\sigma'}, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma'}} & \langle \source{\sigma'}, \target{\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma'}}\\ \source{\sigma'\sigma} f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau}}} & \source{\sigma'\sigma} f \target\tau & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau'}}} & \source{\sigma'\sigma} f \target{\tau\tau'}\\ \end{array} = \qquad \begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau\tau'}} & f\target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma\sigma'} \Big\downarrow} & \langle \source{\sigma\sigma'}, \target{\tau\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma\sigma'}}\\ \source{\sigma'\sigma} f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau\tau'}}} & \source{\sigma'\sigma} f \target{\tau\tau'}\\ \end{array}$
  Finally,
  the compatibility of horizontal with vertical composition
  is shown by the square at right, of four compatible squares.
  Whether
  you first horizontally compose the top and bottom halves,
  then vertically compose the result,
  or first vertically compose the right and left halves,
  then horizontally compose the result,
  you get the same resulting square as shown.

There are then four groupoids:

• A discrete one, consisting only of the 0-cells (one for each function).
• The source groupoid, consisting of the 0-cells and the $\text{s}$-labeled 1-cells,
  specifying how permutations of the source act on functions.
• The target groupoid, consisting of the 0-cells and the $\text{t}$-labeled 1-cells,
  specifying how permutations of the target act on functions.
• The source-target double groupoid, consisting of all the 0-cells, 1-cells, and 2-cells.
  The 2-cells specify how simultaneous permutations of the source and target
  act on functions.

The discrete one is a subgroupoid of all the other groupoids;
the source and target groupoids are subgroupoids of the source-target double groupoid.

The connected components of these four groupoids
are the four parts of the “twelvefold way” for arbitrary functions.
The other eight parts of the “twelvefold way”
are the connected components of
the groupoids defined for surjective and injective functions.

The permutation groups act on surjective and injective functions
just as they act on arbitrary functions,
and we can repeat the above construction on those classes of functions.

---

The specific case of $\homst {[4]} \Set {\{a,b\}}$

Apply the above construction to $\homst {[4]} \Set {\{a,b\}}$.

(The connected components of the double groupoid) are in (the three cells of the figure below).
The component labeled $\{4,0\}$ contains two functions,
the component labeled $\{3,1\}$ contains eight functions,
the component labeled $\{2,2\}$ contains six functions
(each appearing twice in the graphic, connected by $=$ signs,
due to the fact that, for (this component of (the source-target groupoid)),
(target-permutations) remain in (the same connected component of (the source groupoid))).
Note that in (this source-target component) prefixes have been added to the permutations,
so that (in the event that there is overlap between the elements of the source and target)
it can be determined unambiguously whether (a given permutation) is (of the source or target).

[The connected components of the groupoid using (permutations of the source)] are (the columns).
There are five such components (columns), with column headers
$$\langle 4, 0 \rangle, \quad \langle 0, 4 \rangle, \quad \langle 3, 1 \rangle, \quad \langle 1, 3 \rangle,\quad \hbox{and}\quad \langle 2, 2 \rangle .$$

The connected components of the groupoid using (permutations of the target) are connected by (arrows labeled $\target(a,b)$):
five horizontal arrows in the first two cells and
three of the vertical arrows in the third cell,
thus (eight components) of (the target groupoid).
(Because (target permutations) stabilize (this connected component of (the source groupoid)).)

$\{4,0\}$	$\{3,1\}$	$\{2,2\}$
\[\begin{array}{c} \source{\langle 4, 0 \rangle} & \target{\xrightarrow{\text{t-}(a,b)}} & \source{\langle 0, 4 \rangle} \\[8ex] \hline \boxed{\displaystyle { \source{0,1,2,3 \mid {}} \brack \target{aaaa} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{{} \mid 0,1,2,3} \brack \target{bbbb} }\\ \end{array}\]	\[\begin{array}{c} \source{\langle 3, 1 \rangle} & \target{\xrightarrow{\text{t-}(a,b)}} & \source{\langle 1, 3 \rangle} \\[8ex] \hline \boxed{\displaystyle { \source{0,1,2 \mid 3} \brack \target{aaab} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{3 \mid 0,1,2} \brack \target{bbba} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,1,3 \mid 2} \brack \target{aaba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{2 \mid 0,1,3} \brack \target{bbab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,2,3 \mid 1} \brack \target{abaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1 \mid 0,2,3} \brack \target{babb} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{1,2,3 \mid 0} \brack \target{baaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0 \mid 1,2,3} \brack \target{abbb} }\\ \end{array}\]	\[\begin{array}{c} & \source{\langle 2, 2 \rangle} &\\[8ex] \hline \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & = & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)}\Big\uparrow} && \target{\Big\uparrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & = & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ \source{\llap{\scriptstyle \text{s-}(1,2)}\Big\uparrow}\\ \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & = & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)^2}\Big\downarrow\rlap{\scriptstyle \text{s-}(0,2)(1,3)}} && \target{\Big\downarrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & = & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & = & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)^2}\Big\downarrow\rlap{\scriptstyle \text{s-}(0,2)(1,3)}} && \target{\Big\downarrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & = & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} }\\ \end{array}\]

Answering the challenge posed at the beginning, we see that
{the $\target2^{\source4}=16$ functions from $\source{[4]}$ to $\target{\{a,b\}}$} decompose unambiguously into
(the three connected components) of (the source-target groupoid) associated with (the unordered weak $\target 2$-partitions of $\source 4$) $$\{4,0\}, \{3,1\}, \{2,2\} .$$ Each of these three components may be decomposed either into
components of (the source groupoid) or (the target groupoid).
For example,
the eight elements of the $\{3,1\}$ component of the source-target groupoid
can be divided either into

• two ((four-element components) of (the source groupoid)) associated with the two $\{3,1\}$-multisets $a^3b^1$ and $a^1b^3$, or
• four ((two-element components) of (the target groupoid)) associated with the four $\{3,1\}$-partitions of $\{0,1,2,3\}$ $$0,1,2\mid 3,\quad 0,1,3\mid 2,\quad 0,2,3\mid 1, \quad 1,2,3\mid 0 .$$

---

$\{2,2\}$

$\{2,2\}$

\[\begin{array}{c} & \source{\langle 2, 2 \rangle} & \\[8ex] \hline \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\uparrow} && \source{\Big\uparrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ \source{\llap{\scriptstyle\text{s-}(1,2)}\Big\uparrow} && \source{\Big\uparrow\rlap{\scriptstyle\text{s-}(1,2)}}\\ \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} }\\ \end{array}\]

\[\begin{array}{c} && \source{\langle 2, 2 \rangle} && \\[8ex] \hline && \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & = & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\uparrow} && \target{\Big\uparrow\rlap{\scriptstyle\text{t-}(a,b)}}\\ && \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & = & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ && \source{\llap{\scriptstyle\text{s-}(1,2)}\Big\uparrow}\\ && \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & = & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & = & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } && \target{\Bigg\downarrow\rlap{\scriptstyle\text{t-}(a,b)}}\\ && \source{\llap{\scriptstyle(\text{s-}0,1,2,3)}\Big\downarrow}\\ \target{\llap{\scriptstyle\text{t-}(a,b)}\Bigg\downarrow} && \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & = & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & = & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \end{array}\]

The table at right shows
two ways to depict the $\{2,2\}$-component
with the source and target 1-cells orthogonal to each other,
so that
permutations of the source are shown vertically and
permutations of the target are shown horizontally.
To make this possible, each function appears twice.

---

The reader may question why it is necessary to label the 1-cells with $\source{\text{s-}}$ and $\target{\text{t-}}$
when the groupoid to which the 1-cell belongs is, in the cases so far considered,
already indicated by the permutation,
and also by color and orientation (horizontal or vertical) of the 1-cell.

As to the color, some readers may be color-blind; also, colors generally don't appear in prints.
As to the permutations being distinguishable, that will not always be the case.

Consider the case where $\source X = \target Y$.
In such a case all the permutations are permutations of the same set,
thus it is necessary to have some way of distinguishing
whether they are intended to act by precomposition or postcomposition.
The $\source{\text{s-}}$ and $\target{\text{t-}}$ prefixes do just that.

$\begin{array}{c} \functionf & = & \displaystyle { \source{0,2 \mid 1,3} \brack \target{0101} } & \target{\xrightarrow{\displaystyle\text{t-}(0,1)}} & \displaystyle { \source{1,3 \mid 0,2} \brack \target{1010} } & = & \functiong\\ && \source{\llap{\text{s-}(0,1,2,3)} \Bigg\downarrow} && \source{\Bigg\downarrow \rlap{\text{s-}(0,1,2,3)}}\\ \functiong & = & \displaystyle { \source{1,3 \mid 0,2} \brack \target{1010} } & \target{\xrightarrow{\displaystyle\text{t-}(0,1)}} & \displaystyle { \source{0,2 \mid 1,3} \brack \target{0101} } & = & \functionf\\ \end{array}$

As to the possibility of using horizontal versus vertical orientation
to distinguish between a permutation acting on the source or target,
consider the double groupoid associated to $\source X = \target Y = \{0,1,2,3\}$,
i.e., $S_{\{0,1,2,3\}}$ acting on both sides of $\homst {\{0,1,2,3\}} \Set {\{0,1,2,3\}}$,
and in that double groupoid, consider the 2-cell at right.
Note that (both of the intermediate 0-cells) are the same, namely (the function $\target 1010$).
Thus (both the top and left 1-cells) have (exactly the same source and target);
we may say that (they are parallel 1-cells) in (the double groupoid),
and depict (the commonality of their sources and targets) through the diagram

$\displaystyle { \source{0,2 \mid 1,3} \brack \target{0101} } \mathrel{ \source{\xrightarrow[\smash{\mkern7em}]{\displaystyle\text{s-}(0,1,2,3)}} \atop \target{\xrightarrow[\displaystyle\text{t-}(0,1)]{\smash{\mkern7em}}} } \displaystyle { \source{1,3 \mid 0,2} \brack \target{1010} } $

where the prefixes are necessary
to specify whether permutations are acting via pre- or post- composition

$\begin{array}{} \source{[4]} & \xrightarrow{\displaystyle 0101} & \target{[4]} \\ \source{\llap{(0,1,2,3)}\Big\downarrow} & \searrow \rlap{\mkern-2em 1010} & \target{\Bigg\downarrow\rlap{(0,1)}} \\ \source{[4]} & \xrightarrow[\displaystyle 0101]{} & \target{[4]} \\ \end{array}$

Note that this situation corresponds to an automorphism of $\functionf = 0101$ in the arrow category of $\Set$:

---

References

“The bimodule of sets, functions and permutations, and its quotients”, 2019

---

The above post was initially created on 2016-06-27.
The construction of the double groupoid is certainly not original,
it is just an adaption of the standard construction of a double category from a mere category,
restricted to functions from a set $X$ to a set $Y$ and permutations of those two sets.

Equivalence relations, partitions, and surjections

[This is a draft!]
In this post, we fix attention on a fixed set $X \in \bf\text{Set}$.
We consider, compare, and count three structures $X$ may possess:

1. Equivalence relations $E \rightrightarrows X$ on $X$;
2. Partitions $\pi \subset \mathcal P (X)$ of $X$;
3. Surjections (i.e., onto functions) $f: X \twoheadrightarrow Y$ out of $X$.

There are two fundamental relationships between those structures:

1. There is canonical bijection between equivalence relations on $X$ and partitions of $X$.
2. There is a coreflexive (pronounced co-reflexive) adjoint equivalence between the category of equivalence relations on $X$ and the category of surjections out of $X$.

The topics to be covered in this post are:

1. Equivalence relations
2. Partitions
3. Quotient sets, equivalence classes, and quotient maps
4. Kernels (sometimes known as “kernel pairs”)
5. Adjoint equivalences

[Everything below the horizontal line is just experimenting with formatting.]

---

Equivalence relations

A brief review of equivalence relations. The standard definition of equivalence relations is that it is a relation which is reflexive, transitive, and symmetric.
Our definition of an equivalence relation is logically equivalent: that it is a thin groupoid, called by some a setoid.
A groupoid is just a category in which each arrow is invertible. Being a category gives the reflexive and transitive parts of the traditional definition, being “thin” (meaning that there is at most one arrow between any two objects) makes it a relation, and being each arrow being invertible makes the relation symmetric.

Partitions

A brief review of partitions. A partition $\pi$ of a set $X$ is a family of non-empty subsets of $X$ which are (pair-wise) disjoint and such that their union is all of $X$. Thus each element $x\in X$ is a member of one and only one of the non-empty subsets which comprise $\pi$.
So we have a canonical surjection $X \twoheadrightarrow \pi$ : $x\in X \mapsto$ the member of $\pi$ which contains $x$. It is a surjection because each member of $\pi$ is non-empty.

Quotient sets, equivalence classes, and quotient maps

A brief review of quotient sets, equivalence classes, and quotient maps. Given an equivalence relation $E$ on $X$, we define the equivalence class $[x]$ of $x\in X$ to be its orbit or connected component under the groupoid (!). That is equivalent to the customary definition.

For a simple example, we consider the set $X = \{1,2,3 \}$. $\{1,2,3 \}$ has five partitions, each of which is the quotient object in a short exact sequence. The exact sequences corresponding to three of the five partitions are: \[\begin{array}{cccccccl} E \ \text{as function} \ X\times X \to \{0,1\} & E \subseteq X\times X & \rightrightarrows & X & \twoheadrightarrow & X/E & \text{Partition type} & \text{comment} \\ \left ( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1\\ \end{array}\right ) & \{1,2,3\}\times\{1,2,3\} & \rightrightarrows & \{1,2,3\} & \twoheadrightarrow & \bigl\{\{1,2,3\}\bigr\} & 3 & \text{the coarsest, chaotic, case}\\ \left ( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1\\ \end{array}\right ) & \{(1,1),(1,2),(2,1),(2,2),(3,3)\} & \rightrightarrows & \{1,2,3\} & \twoheadrightarrow & \bigl\{\{1,2\},\{3\}\bigr\} & 2+1 & \\ \left ( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\\ \end{array}\right ) & \{(1,1), (2,2), (3,3)\} & \rightrightarrows & \{1,2,3\} & \twoheadrightarrow & \bigl\{\{1\},\{2\},\{3\}\bigr\} & 1+1+1 & \text{the finest, discrete, case}\\ \end{array} \] The other two partitions are also of type $2+1$; the difference is that the block of the partition consisting of only one element contains respectively 1 and 2.

Consider the following diagram ("ker" is kernel): \[ \begin{array}{ccccc} \text{ker(}f\text{)} & \rightrightarrows & X & \overset{\text{class map}}{\twoheadrightarrow} & X/\text{ker(}f\text{)}\\ \Vert && \Vert && \downarrow \\ \text{ker(}f\text{)} & \rightrightarrows & X & \underset{f}{\twoheadrightarrow} & Y\\ \end{array} \] Here the surjection $f$ is at lower right;
the partition is $X/\text{ker(}f\text{)}$ at top right;
the equivalence relation is $\text{ker(}f\text{)}$ on the left.
An important adjoint equivalence (in combinatorics and elsewhere; $X \in \bf\text{Set}$) is \begin{equation} \mathrel{\mathcal{Equiv-relns}(X) \substack{\xrightarrow{X/-} \\\xleftarrow[\text{kernel}]{}} X\downarrow\mathcal{Surj}} \end{equation}

---

\[\begin{array}{ccccc} \mathcal{Equiv-relns}(X) & \xrightarrow[\cong]{X/-} & \mathcal{Part}(X)\\ \text{kernel}\nwarrow &&\swarrow\text{form the class map} \\ &X\downarrow\mathcal{Surj}&\\ \end{array}\]

---

\[\begin{array}{ccccc} \mathcal{Equiv-relns}(X) & \xrightarrow[\cong]{X/-} & \mathcal{Part}(X) & \xrightarrow{\text{form the class map}} & X\downarrow\mathcal{Surj}\\ \Vert & = && \Rightarrow & \Vert \\ \mathcal{Equiv-relns}(X) && \xleftarrow[\text{kernel}]{} && X\downarrow\mathcal{Surj}\\ \end{array}\]