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}\]