Dominique Bourn's "From Groups to Categorial Algebra"

DRAFT. ONLY BEING "PUBLISHED" SO I CAN SEE WHAT IT LOOKS LIKE WHEN PROCESSED BY MATHJAX.

This book actually covers a lot of ground.

I want to focus on a small, but significant, part of that.

Let us consider three topics:

equivalence relation 

equivalence class (or, in group theory, coset)

normal subgroup.

To what extent can these concepts be generalized beyond the theory of groups, and how may they be generalized?

Consider the important and ubiquitous concept of "equivalence relation"

https://en.wikipedia.org/wiki/Equivalence_relation

This is normally defined as a relation, say $R$, on a set, say $X$, which is reflexive, symmetric, and transitive.

These are in turn defined by the effect of $R$ on elements of $X$.

E.g., saying that $R$ is symmetric means that,

writing the relation $R$ as $\sim $, 

for all $x,y\in X$, $x\sim y \implies y\sim x$.

Now, Bourn's strategy is to translate these conditions into category theory, 

so they may be applied to a wide variety of categories, 

beyond merely the category of sets.

As background, Bourn notes that a relation in $\Set$ is a special case of a graph in $\Set$, 

which can be described as a parallel pair of arrows $A \rightrightarrows N$ from the set of arrows IN the graph to the set of nodes in the graph.

A relation is the special case of a graph where the parallel pair is jointly monomorphic, that is, for any two nodes $N1=x$ and $N2=y$, there is at most one arrow from $N1=x$ to $N2=y$.

These two definitions, that 

a graph is a partial pair of arrows and 

a relation is a jointly monomorphic parallel pair of arrows,

may easily be interpreted in an arbitrary category, not just the category of sets.

The reflectivity condition may easily be interpreted in both $\Set$ and in an arbitrary category, for both graphs and relations, as a joint section for the parallel pair.

-----

Next, Bourn gives a single condition on (the reflexive relation $R$) which is logically equivalent to (the conjunction of the symmetry and transitive conditions on $R$).

But that single condition, 

on the relation $R$ (on $X$), 

is a very special case of a much more widely applicable condition, 

so let me put it in that broader context.

If $a,b\in X$ are related by the relation $R$, 

it is conventional to indicate that by writing $a\sim b$.

I am going to write that as a labeled arrow $a \xrightarrow {\textstyle r} b$, 

labelling the specific relation with a letter.

Likewise writing $a\sim c$ as 

$a \xrightarrow {\textstyle s} c$.

Now let us start with the situation 

\[ \begin{array} {} && b \\ & \llap{r} \nearrow \\ a & \xrightarrow [\textstyle s] {} & c \\ \end{array} \]

I.e., $a$ is related to both $b$ and $c$ by relations labelled respectively $r$ and $s$.

Given that situation, there is a condition, which Bourn calls the "horn-filler condition" but which might equally well be called the "extension condition".

The "extension condition" is that, in that situation, 

there exists an arrow (a relation) $r\backslash s : b\to c$.

Thus the extension condition means that we have three arrows, i.e. relations, as shown here:

\[ \begin{array} {} && b \\ & \llap{r} \nearrow & \downarrow \rlap{\exists r\backslash s} \\ a & \xrightarrow [\textstyle s] {} & c \\ \end{array} \]

Now let us see how the horn-filler or extension condition, for a reflexive relation, implies both the symmetry and transitivity conditions.

We combine both into a single diagram:

\[ \begin{array} {} && b \rlap{ \xrightarrow[\kern7.5em]{\textstyle s} } &&&& c \\  & \llap r \nearrow && \searrow \rlap{ r^{-1} } \\ a \rlap{ \xrightarrow[\textstyle 1_a]{\kern9em} } &&&& a \\ \end{array} \]

Note that here we apply the horn-filler, or extension, condition twice, 

first to get $r\inv$, and thus the symmetry condition, and 

second, using $r\inv$, to get a relation $rs$ (not shown) from $a$ to $c$, 

which gives the transitivity condition.

Bourn thus having triumphantly shown how both the symmetry and transitivity conditions follow from a single condition, 

the horn-filler or extension condition, 

his next task is to show how that condition may be translated into category theory.

He does that using the categorical notion of pullback.

In particular, the collection of "horns" (which may be described more categorically as "spans")

is precisely the kernel pair of $d_0 : R \to X$, 

which is the pullback (of $\Delta_X$) in the pullback diagram

\[ \begin{array} {} \boxed{ KP(d_0:R\to X) } = \{<r:a\to b, s:c\to d> : a=c \} & \xrightarrow{} & X & \ni & x\\ \downarrow && \downarrow \rlap{ \Delta_X } && \downarrow \\ R\times R & \xrightarrow [\textstyle d_0\times d_0] {} & X\times X & \ni & <x,x> \\ <r:a\to b, s:c\to d> & \mapsto & <a,c> \\ \end{array} \]

Thus $KP(d_0:R\to X) = \{<r:a\to b, s:a\to c> \}$, the set of all spans, or horns, in $R$.

OTOH, the collection of horns/spans satisfying the extension condition also is a pullback!

Namely the pullback (of $R\to X\times X$) in the diagram 

(where $KP(d_0:R\to X)$ is abbreviated to $KP(d_0)$, or even just $KP$)

\[ \begin{array} {} &&&& R \\ &&&& \downarrow \\ KP(d_0) & \rightarrowtail & R\times R & \xrightarrow [d_1\times d_1] {} & X\times X \\ && \Vert & \Vert & \Vert \\ && \nabla R & \xrightarrow [\nabla d_1] {} & \nabla X \\<r:a\to b, s:a\to c> & \mapsto & <r,s> & \mapsto & <b,c> \\ \end{array} \]

That is,

$({(d_1\times d_1)} | KP : KP\to X\times X)\inv (R) = \{<r:a\to b, s:a\to c> : b \mathrel{ {\sim_R} } c \}$

Bourn in fact considers a larger set, not merely a subset of the horns:

\[ \begin{array} {} <r:a\to b, s:c\to d, \rho: b\to d > && \rho: b\to d \\ \boxed{ {d_1}\inv R } & \xrightarrow {} & R \\ \downarrow&& \downarrow \\  R\times R & \xrightarrow [d_1\times d_1] {} & X\times X \\  \Vert & \Vert & \Vert \\ \nabla R & \xrightarrow [\nabla d_1] {} & \nabla X \\<r:a\to b, s:c\to d>  & \mapsto & <b,d> \\ \end{array} \]

That is,

${(d_1\times d_1)}\inv (R) = \{ <r:a\to b, s:c\to d> : b \mathrel{ {\sim_R} } d \}$

Then the condition that every horn/span has an extension becomes 

\[ \boxed{ KP(d_0) \subseteq {d_1}\inv R } \]

-----

We can combine the various pieces of the above into one quite useful large diagram.

\[ \begin{array} {} &&&& <r:a\to b, s:c\to d, \rho: b\to d > && \rho: b\to d \\ && \big\{ <r:a\to b, s:a\to c, \rho: b\to c> \big\} & \rightarrowtail & \boxed{ {d_1}\inv R } & \xrightarrow {} & R \\ && \downarrow && \downarrow&& \downarrow \\ <r:a\to b, s:a\to c> & \in & \boxed{ KP(d_0) } & \rightarrowtail & R\times R & \xrightarrow [d_1\times d_1] {} & X\times X \\ &&&& \Vert & \Vert & \Vert \\ &&&& \nabla R & \xrightarrow [\nabla d_1] {} & \nabla X \\ &&&& <r:a\to b, s:c\to d>  & \mapsto & <b,d> \\ && \downarrow && \downarrow \rlap{d_0\times d_0} \\ a & \in & X & \xrightarrow [\Delta_X] {} & X\times X \\ &&&& <a,c> \\ \end{array} \]

------------------------------

Suppose $\boxed{ R \rightarrowtail G\times G }$ is an internal relation in the category of groups.

Then relations have inverses, and we can multiply them.

So, writing the relation as $\sim$, 

if $g\sim h$ then, taking the inverse of the relation, also $g\inv \sim h\inv$.

And if as well $a\sim b$, then, multiplying the relations, $ga \sim hb$.

If further $R$, or $\sim$, is a reflexive relation, i.e. $(\forall g\in G) (g\sim g)$, 

then, somewhat surprisingly, $\sim$ is in fact an internal equivalence relation!

Let's see why that is so.

Reflectivity gives $(\forall a\in G)(a\sim a)$.

Then if also $g\sim h$, multiplication of the relations gives $ga \sim ha$ and $ag\sim ah$.

For symmetry, we have:

\[\begin{array} {} g\sim h \\ h\inv \sim g\inv \\ h\sim g \\ \end{array} \]

For transitivity, we have

\[ \begin{array} {} g\sim h \\ h\inv \sim g\inv \\ h \sim k \\ \hline e = h\inv h \sim g\inv k \\ g \sim k \\ \end{array} \]

Let us also note that finitely complete categories in which every internal reflexive relation is an internal equivalence relation 

(like the category of groups)

are called, by Bourn and others, <b>Mal'tsev categories</b>.

https://ncatlab.org/nlab/show/Malcev+category

-------------------

This information, i.e. structure, may be described as a 2-category, 

with only one 0-cell, 

whose 1-cells are the elements $g$ of the group $G$, 

whose vertical category is the relations $r$ in the equivalence relation $R$, 

whose horizontal composition on 1-cells is the group composition in $G$, and 

whose horizontal composition on 2-cells (i.e., elements of $R$) is the group operation in $R$.

Vertical composition of 2-cells is composition of relations.

To see this, consider the equality of 2-diagrams

\[ \begin{array} {} \xrightarrow [\kern3em] {\textstyle g} && \xrightarrow [\kern3em] {\textstyle a} && \xrightarrow [\kern6em] {\textstyle ga} \\ \llap r \Big\Downarrow && \Big\Downarrow \rlap s  && \Big\Downarrow \rlap {rs} \\ \xrightarrow [\textstyle h] {} && \xrightarrow [\textstyle b] {} & = & \xrightarrow [\textstyle hb] {} \\ \Big\Downarrow && \Big\Downarrow  && \Big\Downarrow \\ \xrightarrow [\textstyle k] {} && \xrightarrow [\textstyle c] {} && \xrightarrow [\textstyle kc] {} \\ \end{array} \]

This may alternatively be depicted as

\[ \begin{array} {} \xrightarrow [\kern3em] {\textstyle g} && \xrightarrow [\kern3em] {\textstyle h} && \xrightarrow [\kern6em] {\textstyle gh} \\ \llap r \Big\Downarrow && \Big\Downarrow \rlap {s} && \Big\Downarrow \rlap {rs} \\ \xrightarrow [\textstyle g'] {} && \xrightarrow [\textstyle h'] {} & = & \xrightarrow [\textstyle g'h'] {} \\  \llap{r'} \Big\Downarrow && \Big\Downarrow \rlap{s'}  && \Big\Downarrow \rlap{r's'} \\ \xrightarrow [\textstyle g''] {} && \xrightarrow [\textstyle h''] {} && \xrightarrow [\textstyle g''h''] {} \\ \end{array} \]

or

\[ \begin{array} {} \xrightarrow [\kern3em] {\textstyle g} && \xrightarrow [\kern3em] {\textstyle g'} && \xrightarrow [\kern6em] {\textstyle gg'} \\ \llap r \Big\Downarrow && \Big\Downarrow \rlap {r'}  && \Big\Downarrow \rlap {rr'} \\ \xrightarrow [\textstyle h] {} && \xrightarrow [\textstyle h'] {} & = & \xrightarrow [\textstyle hh'] {} \\ \llap s \Big\Downarrow &&  \Big\Downarrow \rlap {s'} && \Big\Downarrow \rlap{ss'} \\ \xrightarrow [\textstyle k] {} && \xrightarrow [\textstyle k'] {} && \xrightarrow [\textstyle kk'] {} \\ \end{array} \]

We may diagram this situation as a diagram of sets:

\[ \begin{array} {} \calC_0 & \leftarrow & \calC_h = G \ni g & \to & \calC_0 \\ \uparrow && \uparrow &&  \uparrow \\ \calC_v & \leftarrow & \calC_2 = R \ni r & \to & \calC_v \\ \downarrow && \downarrow && \downarrow \\ \calC_0 & \leftarrow & \calC_h = G \ni h & \to & \calC_0 \\ \end{array} \]

where $\calC_0$ and $\calC_v$ are both trivial, i.e., one-element sets.

A (categorical) diagram for the Chain Rule

The standard proof of the Chain Rule, 

for the derivative $(\blue f \green g)'$ of the composition of two differentiable functions between three vector spaces:

\[ \begin{array} {} && F \\ & \blue{ \llap f \nearrow } && \green{ \searrow \rlap g } \\ \blue E & {} \rlap{ \kern-.5em \xrightarrow [\textstyle \blue f \green g] {\kern6em} } &&& \green G \\  \end{array} \]

 shows a bunch of equations, with some being substituted into others to yield the final desired result.

As an example of this, see the proof of the Chain Rule 

given in Chapter XVII, Section 3 of Serge Lang's well-known <I>Undergraduate Analysis</I>.

(Actually, he only assumes $f$ and $g$ are defined on suitable open sets of $E$ and $F$, but for simplicity we will assume they are globally defined.)

Just giving the equations omits some important information: in which vector space are the equations holding, and in which vector space do the variables live?

Of course the knowledgeable reader can infer that, but it seems to me it would aid the understanding of the proof, and the situation, to make that "typing" information explicit.

That is easy to do with a categorical diagram.

I don't have sophisticated enough diagramming software to let me show you the full diagram in this blog, but I can tell you how to draw it for yourself on a sheet of paper.

Here is the key part, which in the full diagram is inscribed in the $E\to F\to G$ triangle drawn above.

\[ \begin{array} {} &&& F &&& \\ && \llap{\blue{xf}} \Bigg\uparrow & \blue{ \begin{array} {} h \black k \\ \black\Longrightarrow \\ h(xf') \mathrel {\black +} (h\psi_f) \mathrel \cdot |h| \\ \end{array} } & \Bigg\uparrow \rlap{ \blue{ (x+h)f = xf \mathrel{\black+} h \black k = xf + h(xf') + (h\psi_f) \cdot |h| } } \\ & \blue{  \xleftarrow [\kern3em] {\textstyle x+h} } &&&& \xrightarrow [\kern18em] {\textstyle xfg} \\ \blue E & \blue{ \smash{\Bigg\Uparrow} \rlap h } && \rightadj 1 && \smash{ \Bigg\Downarrow } \rlap{ \kern-6em (hk) (xfg') + \big( (hk)\psi_g \big) \cdot |hk| } & G \\ & \blue{ \xleftarrow[\textstyle x] {} } &&&& \xrightarrow [ \textstyle (x+h)fg = (xf+hk)g ] {} \\ \\ \hline \\ {} \rlap{ \blue{ \big(h(xf') \mathrel {\black +}  (h\psi_f) \mathrel \cdot |h|  \big) } (xfg') + \green{ \big( (hk)\psi_g \big) \cdot |hk| } } \\ {} \rlap{ \blue{h(xf')} (xfg') \mathrel {\black +} \blue{ \big((h\psi_f) \mathrel \cdot |h| \big) } (xfg') + \green{ \big( (hk)\psi_g \big) \cdot |hk| } } \\ \end{array} \]

----------

There are several notational conventions at play here.

\[ \begin{array} {l|cccc|cc|cccc} & \text{mult} & \text{appl} & \text{comp} & \text{appl+comp} & \lambda\text{ fn} & \lambda\text{ number} & \rightadj{ \text{the derivative} } \\ \hline \text{Lang} & xy & f(x) & g\circ f & g(f(x)) & \lambda(h) & \lambda h & f(\source{x+h}) \mathrel{\target=} f(\source x) \mathrel{\target+} \big(f'(\source x)= \rightadj D f(\source x)\big)(\source h) \mathrel{\target+} \source{|h|}\psi(\source h) \\ \text{Harbaugh} & x\cdot y & xf & fg & xfg & h\lambda & h\cdot\lambda & \source{(x+h)}f \mathrel{\target=} \source x f \mathrel{\target+} \source h \cdot  \big(\source x (f'=f\rightadj D)\big) \mathrel{\target+} (\source h \psi)\cdot \source{|h|} \\ \text{example} &&&&&&& \source{(x+h)}^2 \mathrel{\target=} \source x ^2 \mathrel{\target+} \source h \cdot ( \source x \cdot \rightadj 2 ) \mathrel{\target+} \source{ \big( h\cdot h = ({h\cdot h \over |h|}) \cdot |h| \big) } \\ \end{array} \]