Terminology and notation

Here is a brief statement of some of the terminology and notation we will be using in this post.<\p>

The terminology used in category theory may seem a little unusual.
In the table below are some of the terms used in category theory for certain types of arrow,
shown above the horizontal line in each cell of the table;
below that line is the term normally used
when speaking of functions in the category of sets.

Categorical terminology for arrows		Invertible? ($\longleftrightarrow$)
		Not necessarily	Yes
Loop? $\bigl(\circlearrowright\bigr)$	Not necessarily	arrow, morphism, map function	isomorphism bijection
	Yes	endomorphism endofunction, loop, self-map	automorphism permutation

---

Notes:

1. “Permutation” sometimes connotes that the underlying set is finite.
2. “Bijection” is a synonym for the older term “one-to-one correspondence.”
3. “Arrow” is the most abstract of the terms.

---

Terminology

Graph

We use the definition fairly standard in category theory,
that “graph” means directed graph,
which is simply a parallel pair of arrows in a category: $\mathop\rightrightarrows\limits^{d_0}_{d_1}$.
The object which is the source of the arrows is considered the object of edges;
the object which is the target of the arrows is considered the object of vertices.
The arrows $d_0,d_1$ determine respectively the source and target of the edges.
If the context makes it clear that the ambient category is the category of sets, $\Set$,
then this resembles the graph theorists definition of directed graph.
But see the nlab article for the many meanings of the term.

---

Notation

Order for arrow composition

In most (I think all, but a slip-up is possible) instances in this blog,
when writing the composition of arrows in text,
I write the composition in diagrammatic, left-to-right order.
Thus the composite of $X \xrightarrow f Y$ with $Y \xrightarrow g Z$ would be written $X \xrightarrow {fg} Z$.

Links to detailed bibliographies for

Max Kelly

https://en.wikipedia.org/w/index.php?title=Max_Kelly&oldid=975556001

Ross Street

https://en.wikipedia.org/w/index.php?title=Ross_Street&oldid=975565027

---

Some highlights (in my opinion) of this blog:
Basic examples of Kan extension in logic and set theory
Relations between limits in categories
The bimodule of sets, functions and permutations
Double groupoids and the twelvefold way
The identities-are-free (Yoneda) lemma
Yoneda structures 1
The category structures on 2
Relations between the categories Set and 2

The use of size in this blog

In this blog we talk about, mainly, three different sizes of things,
small, large and very large.
Thus
$\Set$ is the large category of small sets and functions.
$\CAT$ is the very large 2-category of large categories (and functors and natural tranformations between them).
Thus, using $`\in'$ to mean $``$is an object of$"$, we have, if $X$ is a small set,
$$X \in \Set \in \CAT.$$

$\Newextarrow{\xLongrightarrow}{3,2}{0x21D2}$

The reason for worrying about this is to try to avoid logical problems that can occur if size is ignored.
If one uses the tools of set theory without care, logical inconsistencies can occur.
For example, consider how the unrestrained use of set theoretical constructions
can lead to a contradiction
(this example returns to the normal set-theoretical meaning of $`\in'$):

1. Let $U$ (for “universe”) be the set of all sets.
2. Let $X = \{u\in U \mid u \notin u \}$.
3. Assume $X \in U$.
4. Ask the question: Is $X \in X$?
   $X \in X \xLongrightarrow{\text{defn $X$}} X \notin X$.
   $X \notin X \xLongrightarrow{\text{defn $X$}} X \in X$.
   Thus in either case we have a contradiction.

So, to avoid contradiction,
we must disallow at least one part of the reasoning in the above example.

Is the problem that we are allowing $X$ to be both a subset and an element of $U$?
No, that is generally allowable.
For example, consider the set $\bigl\{1,\{1\}\bigr\}$.
Here $\{1\}$ is both a subset (containing the first element)
and an element (the second element) of the same set.
(By the way, this situation occurs consistently in the definition of ordinal numbers,
e.g. $2 = \bigl\{\emptyset,\{\emptyset\}\bigr\}$.)

To, hopefully, avoid such problems,
in this blog we employ the hierarchy sketched above.
Then we would modify the above example to make $U$ be the set of all small sets.
We could still define $X$ as above, but it would not necessarily be in $U$,
making steps 3 and 4 invalid.

Technical note:
The term ‘small’ is relative to a chosen “Grothendieck universive”.
Also see the dichotomy small/large in Mac Lane's CWM.
We accept the “Axiom of Universes”, and use it to go a step further, to “very large” sets,
to allow for the comparison of large categories and 2-categories.

Categories

For the definition, see Wikipedia.

Here, at this time, we just want to give a small diagram that shows some of the relations between the categories of categories, monoids, (directed) graphs, and sets.
$$\begin{array}{cccccc} \Mon& \subset & \Cat\\ \downarrow && \downarrow\\ \Set & \subset & \Graph\\ \end{array}$$ Here the vertical arrows take, respectively, a monoid to its underlying set and a category to its underlying graph (i.e., they forget the composition and the specification of the identities).
The top inclusion takes a monoid into a category with just one object and that monoid as its set of arrows.
The bottom inclusion takes a set into the graph with only one vertex and that set as its set of edges.

Both vertical (downward) arrows have left adjoints going up, taking respectively a set to the free monoid on that set and a graph to the free category on that graph.

---

Following is work in progress!
Here are two diagrams, one for ordinals and the other for internal categories:

$\begin{array}{} &&&& \{1\} \\ &&& \swarrow && \searrow \\ && \{0,1\} &&&& \{1,2\} \\ & \nearrow && \searrow && \swarrow && \nwarrow \\ &&&& \{0,1,2\} \\ &&&& \uparrow \\ \{0\} && \rightarrow && \{0,2\} && \leftarrow && \{2\} \\ \end{array}$

$\begin{array}{} &&&& \catC_0 \\ &&& \nearrow && \nwarrow \\ && \catC_1 &&&& \catC_1 \\ & \swarrow && \nwarrow && \nearrow && \searrow \\ &&&& \catC_2 \\ &&&& \downarrow \\ \catC_0 && \leftarrow && \catC_1 && \rightarrow && \catC_0 \\ \end{array}$

Opposite categories and contravariance

Motivation: Consider the situation, in an arbitrary category, $$\leftcat{X' \buildrel u \over \to X} \buildrel f \over \to \rightcat{Y \buildrel v \over \to Y'}$$ Often we want to consider $\leftcat u$ and $\rightcat v$ as operators operating on $f$.
But then consider the slightly more complex situation $$\leftcat{X'' \buildrel u' \over \to X' \buildrel u \over \to X} \buildrel f \over \to \rightcat{Y \buildrel v \over \to Y' \buildrel v' \over \to Y''}$$ Comparing letting first $\leftcat u$ and $\rightcat v$ operate on f, then their primed relatives,
to first composing the operators, then letting the composed operators operate on f,
we have $$\leftcat{u'}(\leftcat u f \rightcat v)\rightcat{v'} = \leftcat{(u'u)} f \rightcat{(vv')}$$

Groups

The notion of group is presumed.
The smallest group is one consisting of one element only, which, by definition of group, must be the identity element of the group. Any such group is called “trivial”. All such groups are isomorphic, but not identical. Here are several isomorphic, but not identical, such groups: $$\begin{array}{ll} &\text{underlying set} &\text{group operation}\\[1ex] &\{0 \in \Z\} &\text{addition}\\ &\{1 \in \Z\} &\text{multiplication}\\ &\{ 1_X : X \to X \} &\text{function composition, for any set } X\\ \end{array}$$ Like the groups with one element, all groups with two elements are isomorphic.
If we denote the identity element by $e$ and the non-identity element by $t$,
such a group must have the multiplication table $$\begin{array}{ccc} &&e&t\\[1ex] e&&e&t\\ t&&t&e\\ \end{array}$$ So the non-identity element is of order 2.

(Page down to see the remainder of this post.)

However, as with groups of order 1, the isomorphic groups of order 2 may have different underlying sets, and different group operations.
Here are some significant, and frequently encountered, examples: $$\begin{array}{cccccc} \text{name} & \text{underlying set} & \text{identity} & \text{non-identity} & \text{group operation} & \text{comment}\\[2ex] {\bf Z}_2 & \{0,1\} & 0 & 1 & \text{addition modulo 2} & \text{the integers modulo 2}\\ {\bf O}_1 & \{+1,-1\} & +1 & -1 & \text{multiplication} & \text{the one-dimensional orthogonal group}\\ S_2 & \text{bijections of }\{1,2\} \text{ with itself}& \text{identity function} & (1,2) & \text{function composition} & \text{symmetric group on two elements}\\ \end{array}$$

---

To illustrate our notation (the cycle notation for permutations),
here are the elements of the symmetric group, or group of permutations, $S_3 = S_{[3]}$
of symmetries, or permutations, or autobijections, of $[3] \equiv \{0,1,2\}$.
Its $3!=6$ elements are denoted as follows:

• $\iota \equiv e \equiv (0)(1)(2)$, the identity function on $[3]$.
  When this function is considered in the context of all function,
  the usual notation for it is $1_{[3]}$.
  But when the context is only the group $S_3$,
  $\iota$ or $e$ are almost invariably used.
  
  Then the three 2-cycles:
  
• $(0,1)(2)$.
  It is common to omit the fixed points when writing permutations in cycle notation,
  so this becomes just $(0,1)$.
• $(0,2)(1) \equiv (0,2)$
• $(1,2)(0) \equiv (1,2)$.
  
  Then the two 3-cycles:
  
• $(0,1,2)$
• $(2,1,0)$

Group actions

If ($G$ is a group) and ($\rightcat X$ is a set), (a (right) group action) is
(a function $\boxed{{\rightcat X} \times G \to \rightcat X}$) which is associative and unital,
meaning that $x(gh) = (xg)h$ and $xe = x$,
where $x\in \rightcat X$, $g,h\in G$ and $e$ is the unit (identity) element of $G$.
For (a left group action), just replace ${\rightcat X} \times G$ with $G \times {\rightcat X}$,
and change the equations to $(gh)x = g(hx)$ and $ex = x$.

---

For some important examples of group actions, see the post on
The bimodule of sets, functions and permutations.

<hr/>

For (given $G,\rightcat X$) in (a cartesian closed category), there are two other, equivalent, ways of (giving the structure) and (formulating the axioms), given as follows:

 

$$\boxed{  \begin{array} {cccccccccc|clc|cccccccc|l} &&&  {} \rlap{ \kern-2em \text{Structure} }  &&&&&&&  {} \rlap{ \kern8em \text{Description} }   &&& {} \rlap{ \kern1.5em \text{Equational Axioms, aka Constraints} }   &&&&&&&&  {} \rlap{  \kern3em \text{Comment}  }     \\   &&& &&& &&& &&& &&   {} \rlap{ \kern-1em \text{Identity Axiom} } &&&&  {} \rlap{ \kern-1.5em \text{Associativity Axiom} }     \\     \hline  {\rightcat X}_{-} & : & G  &  \to  &  [\rightcat X,\rightcat X]  & : & g & \mapsto & {\rightcat X}_g  &&&  \text{the monoid $[\rightcat X,\rightcat X]$ as a $\textit{representation}$ of $G$}  &&&  {\rightcat X}_e & = & \rightcat{1_X} && {\rightcat X}_g{\rightcat X}_h & = & {\rightcat X}_{gh}   &  \rightcat X \text{ is functorial}    \\      \hline   {\rightcat -} \tensor {-} & : & {\rightcat X} \times G  &  \to  &  \rightcat X  & : & \langle x,g \rangle & \mapsto & x \tensor g = xg &&&  \text{$\rightcat X$ as a $\textit{module}$ over $G$, i.e. as a $G{-}\textit{module}$}  &&&  xe & = & x  && (xg)h & = & x(gh)   &   \text{the action is associative}    \\     &&&&&& [x]g & \mapsto & (x)g = xg  &&& \text{Kelly's notation for actions of "clubs"}  && &(x)e & = & x && \big((x)g\big)h & = & (x)(gh)    \\    \hline   \rightcat{  \widehat{ \black{(-)} }  } & \rightcat : & \rightcat X  &  \rightcat\to  & \rightcat{ [\black G, X] }  & : & x & \rightcat\mapsto & \rightcat{ \hat{\black x} } &&&  \text{the $G{-}\textit{orbits}$ of $\rightcat X$} :  &&& e \rightcat{ \hat{\black x} } & = & x && h \rightcat{  \widehat{ \black{( g \rightcat{ \hat{\black x} } )} }  } & = & (gh) \rightcat{ \hat{\black x} }      \\    &&& &&& &&& &&  \boxed{    \rightcat{   {\hat{\black x}} : {\black G} \to  X : {\black g} \mapsto {\black g} \rightcat{ \hat{\black x} } = {\black x}{\black g} = {\black x} X_{\black g}  }    } & &&& &&&  \rightcat{ \hat{\black x} } {\rightcat X}_h & = & G_h \rightcat{ \hat{\black x} }   &   \text{each orbit $\rightcat{\hat{\black x}}$ is $G$-natural}  \\     &&& &&& &&& &&   \rightcat{ \alpha : {\black G} \to X  : {\black g} \mapsto {\black g}\alpha   } \text{    such that  } (\rightcat\alpha \text{ is }  \mathit{natural}) & & &  && &&  {\rightcat\alpha} {\rightcat X}_h & = & G_h {\rightcat\alpha}    \\    \end{array}  }$$

( The additional line for $[x]g \mapsto (x)g$ under "$\rightcat X$ as a $\textit{module}$") shows (a notation introduced by Kelly in (his papers on clubs) ).

Here of course ($g$ is being viewed as an operator), ($x$ as an operand).

In the event that $G$ has (a distinguished element $e$) 

and (an internal composition operation, here denoted merely by juxtaposition), 

often one is interested in (structures on the pair $\rightcat X,G$) 

which are related to (the internal structure of $G$) by (the equations displayed in the panel at the right).

In the case where ($G$ is a group), this is what is meant by (the phrase "group action").

More generally, (structures satisfying such axioms) are called "algebras".

Precedent for denoting the action operation by $\tensor$ is in Section 3 of Im+Kelly.

<hr />

$$\boxed{    \begin{array} {}  && &&     &&  x, \gamma  &&&&  \gamma  &  \kern1em    \\     &&  &&   &&  X \times_{\calC_0} \calC_1  &  {} \rlap{\kern-1em \xrightarrow[\kern10em]{} }  &&& \calC_1    \\    \gamma  &&  \ast,\gamma   && x,\gamma   & \rightadj{ \nearrow \rlap{ \text{monic} }  } && \rightadj{ \text{p.b.} }  &&  \rightadj{ \nearrow \rlap{ \text{monic} } }     \\     (c\downarrow \calC)_0  &  \cong  &  1 \times (c\downarrow \calC)_0   &  \xrightarrow{\textstyle x \times 1}  &  X_c \times (c\downarrow \calC)_0    &  {} \rlap{\kern-1em \xrightarrow[\kern10em]{} }  &&&  (c\downarrow \calC)_0    \\     &&    &&     &&  \leftcat{ \llap{\text{projection} \mapsto x} \Bigg\downarrow }  \rightcat{ \Bigg\downarrow  \rlap{ \text{action} \mapsto x\gamma = x X_\gamma} }   &&&&  \leftcat{ \llap{s} \Bigg\downarrow }  \rightcat{ \Bigg\downarrow \rlap{t} }    \\     && && && && &  {} \rlap{  \kern-3em \leftcat{ \text{p.b. for } s }  }    \\  &&   \leftcat{ \llap{\text{projection} \mapsto \ast} \Bigg\downarrow }  \phantom{ \rightcat{ \Bigg\downarrow } }   &&    \leftcat{ \llap{\text{projection} \mapsto x} \Bigg\downarrow }  \phantom{ \rightcat{ \Bigg\downarrow } } &&&&   \leftcat{ \llap{s} \Bigg\downarrow }  \phantom{ \rightcat{ \Bigg\downarrow \rlap{t} } }  \\  &&   &&   &&  X  &  {} \rlap{\kern-1em \xrightarrow[\kern10em]{} }  &&& \calC_0    \\   && &&   &  \rightadj{ \nearrow \rlap{ \text{monic} } } &&  \rightadj{ \text{p.b.} }  &&   \llap{\leftcat c}  \rightadj{ \nearrow \rlap{ \text{monic} } }  \\  &&     1  & {} \rlap{ \kern-0.5em \xrightarrow[\textstyle x]{\kern3em} }  &    X_c  &  {} \rlap{\kern-1em \xrightarrow[\kern10em]{} }  &&& 1     \\     &&  \ast  & \mapsto &  x     \\    \end{array}    }$$

Given $x \in \rightcat X$, let $c \in \calC_0$ be its image in $\calC_0$.

Then

(the map $\hat x : (c\downarrow \calC)_0 \to \rightcat X : \gamma \mapsto \gamma \hat x = x\gamma$ via the action of $\calC$ on $\rightcat X$)

is (the <i>orbit</i> of $x$ under the action).

Then the following are equivalent statements:

($\hat x$ is an equivariant map of right $\calC$-sets) 

iff $x(\gamma\gamma') =  (x\gamma)\gamma'$ for all compatible $x,\gamma,\gamma'$ 

iff (the associativity axiom holds for the action).

<hr />

Given $\rightcat{   \boxed{  \alpha : { \black{\hom c \calC -} } \Rightarrow X  }   }$, 

a natural transformation from (the covariant regular representation of $\calC$ at $c$) to (an arbitrary covariant $\calC$-set $\rightcat X$), 

we have, for each $d \in \calC$ and $f \in \hom c \calC d$,

$$\boxed{    \begin{array} {}    1_c  &  &&  \rightcat\mapsto  &&  (1_c)\alpha_c = \boxed{\check\alpha}    \\    c  &&  \hom c \calC c  &  \rightcat{   \xrightarrow[\kern3em]{ \textstyle {\black c} \alpha = \alpha_{\black c} }   }  &  {\rightcat X}_c    \\  \llap{f} \Bigg\downarrow  &&  \llap{\hom c \calC f} \Bigg\downarrow  &  \rightcat{   {\black f} \alpha = \alpha_{\black f}   }  &  \Bigg\downarrow \rlap{{\rightcat X}_f}    \\    d  &&  \hom c \calC d  &  \rightcat{   \xrightarrow[\textstyle {\black d} \alpha =  \alpha_{\black d}]{\kern3em}   }  &  {\rightcat X}_d    \\      (1_c) \hom c \calC f = 1_c f =  f  & &&  \rightcat \mapsto  &&  \begin{array}{}    (1_c) \hom c \calC f {\rightcat\alpha}_d & \xlongequal{\textstyle (1_c){\rightcat\alpha}_f}  &  (1_c) {\rightcat\alpha}_c {\rightcat X}_f    \\ \llap{ \text{defn } \hom c \calC f } \Vert  &&  \Vert \rlap{ \text{defn } \check{\rightcat\alpha} \text{  -- restriction} }  \\    (1_c f) {\rightcat\alpha}_d   &&    {\check{\rightcat\alpha}} {\rightcat X}_f    \\  \llap{ 1_c \text{ is an identity} }  \Vert  &&  \Vert \rlap{ \text{defn } {\hat{()}}_d  \text{  -- extension}  }     \\     f \boxed{{\rightcat\alpha}_d}   && f \boxed{ \big( \hat{ {\check{\rightcat\alpha}} }  {\big)}_d }   & \kern7em   \\   \text{thus:  }  & \boxed{  \boxed{ \rightcat\alpha = \hat{\check{\rightcat\alpha}} }  }    \\  \end{array}     \\     \end{array}   }$$

On the other hand, given $x \in {\rightcat X}_c$,

$$\check{ \hat x }  \xlongequal{\textstyle \text{defn }  \check{()} }   1_c \big(\hat x\big)_c  \xlongequal{\textstyle \text{defn } \big(\hat x\big)_c }  x {\rightcat X}_{1_c} \xlongequal{\textstyle {\rightcat X}  \text{ preserves identities} } x \rightcat{ 1_{X_{\black c}} } = x$$

Thus $\boxed{ \check{ \hat x } = x }$.

Thus finally we have a bijection

$$\boxed{  \leftcat{ (\check{\rightcat\alpha} = x) \in {\rightcat X}_c} \; {  \leftadj{ \xrightarrow[\text{extension}]{\textstyle \hat{()} }} \atop { \rightadj{ \xleftarrow[\textstyle \check{()}]{\text{restriction}} } }  } \; \rightcat{ { \hom {\hom c \calC -} {[\calC, \Set]} {\rightcat X} } \ni (\alpha = \hat {\leftcat x}) }   }$$

almost surely the simplest and most basic example of the "Yoneda bijection".

<hr />

To prepare for generalizations, and to justify calling $\hat x$ an "extension", 

consider the forgetful functor $\boxed{ \rightadj U \mathrel{\rightadj :} \rightcat{G{-}\Set} \mathrel{\rightadj\to} \leftcat\Set \mathrel{\rightadj :} \rightcat X \mathrel{\rightadj\mapsto} \rightcat X \rightadj U \mathrel{\rightadj =} \leftcat X }$, 

 where we have followed the common practice of using the same letter $X$ to denote both a $G$-set, with its action $X \times G \to X$, and its underlying mere set $\leftcat X$, 

and where $\rightcat{G{-}\Set}$ denotes (the category of $G$-sets) (not to be confused with G-spots! :-).

$G$'s multiplication $\boxed{ G \times G \to G }$ makes $G$ a right (and also a left) $G$-set, the (right) (or left) regular representation of $G$.

The identity element $\boxed{e}$ of $G$ may be specified ("named") via an arrow in $\leftcat\Set$, $\boxed{ \leftadj{   e : \leftcat 1 \to G \rightadj U   } }$.

The content of the most basic Yoneda bijection may then be expressed by the statement

$$\boxed{   \leftadj {  e : \leftcat 1 \to G \rightadj U \kern1em \text{ is a universal arrow from $\leftcat 1$ to $\rightadj U$.}  }    }$$

$$\boxed{    \begin{array} {}      &&  \leftadj G    \\      & \leftadj{ \llap{e} \nearrow}  &  \Vert  & \rightcat{    \searrow \rlap{ \exists! \, \hat{\leftcat x} = \alpha \text{     ;    the } \textit{extension} \leftcat{\text{ of } x}}   }    \\     \leftcat 1 &  \leftcat{      {} \rlap{ \kern-1em \xrightarrow[ {}\rlap{\textstyle \kern-3em \forall \, x = \check{\rightcat\alpha} \text{     ;    the } \textit{restriction} \rightcat{\text{ of } \alpha}} ]{\kern8em} }    }  &&& \rightcat X    &  \kern10em  \\    \end{array}    }$$

Here the two arrows originating at the set $\leftcat 1$ are both arrows in $\leftcat\Set$, while the arrow $\rightcat{{\leftadj G} \to X}$ is in $\rightcat{G{-}\Set}$.

What "$\leftadj{   e : {\leftcat 1} \to G {\rightadj U}   } \kern1em \text{ is a universal arrow from $\leftcat 1$ to $\rightadj U$}$" means is:

For every arrow $\leftcat{   1 \xrightarrow[\kern1.5em]{\textstyle x} {\rightcat X}   }$ as at bottom (i.e. for every element $\leftcat{x \in X}$), 

there exists a unique morphism of $G$-sets $G \to \rightcat X$ as at right which makes the triangle commute. 

We denote this unique morphism of $G$-sets, whose existence and uniqueness is guaranteed by the universal property, by $\boxed{ \hat x }$.

$\newcommand\GSet{{\rightcat{G{-}\Set}}}$

A familiar example, for $V$ a vector space over $\R$, and $v \in \rightcat V$ a vector in it:

$$\begin{array} {}      && \R    \\      & \llap{1} \nearrow  &  \Vert  &  \searrow \rlap{ \hat v = \rightcat l \text{     ;    the $\textit{extension}$ of $v$, the parameterized line through $v$}}    \\    \leftcat 1 & {} \rlap{ \kern-1em \xrightarrow[\textstyle v = \check l \rlap{ \text{     ;    the $\textit{restriction}$ of $\rightcat l$}}]{\kern10em} } &&& \rightcat V    \\    \end{array}$$

Here of course "$1$" is being used to denote both a one-element set, say $\leftcat{1=\{\emptyset\}}$, and the real number usually so denoted.

<hr />

Returning to the more general $\rightcat{G{-}\Set}$ context, 

the "bijection between arrows" formulation has a generalization to an adjunction:

Given a group $G$ in $\Set$, there is an adjunction:

$$\boxed{  \leftcat{Y \in \Set} \; {   { \leftadj{ \xrightarrow[\kern6em]{\textstyle (-\times G)} } } \atop { \rightadj{ \xleftarrow[\textstyle U]{\kern6em} } }   } \; \rightcat{G{-}\Set \ni X}  }$$

I.e. the arrows in the box above are functors and we have a natural (in $\leftcat Y$ and $\rightcat X$) bijection of sets

$$\boxed{    \begin{array} {}  \rightcat\alpha  & \rightcat\in  &   \rightcat{  \hom { \leftadj{ ({\leftcat Y} \times G) } } {(G{-}\Set)} X  }    \\  && \red{\wr\Vert}    \\      \leftcat{ x }  &  \leftcat\in  &  \leftcat{ \hom Y \Set {\rightcat X \rightadj U}  } \\    \end{array}  }$$

We can depict the relation between $\leftcat x$ and $\rightcat\alpha$ with:

$$\boxed{    \begin{array} {} && \leftadj{ {\leftcat Y} \times G }     \\ &  \leftadj{   \llap{ \leftcat Y \times e }  \nearrow  }  & \Vert & \rightcat{    \searrow \rlap{ \exists! \, \hat {\leftcat x} = \alpha \text{ ; the $\textit{extension}$ of $\leftcat x$}  }}       \\        \leftcat{ Y \cong Y\times 1 }  &  {} \rlap{ \kern-1em \leftcat{   \xrightarrow[\textstyle \forall \, x = \check{\rightcat\alpha} \rlap{ \text{ ; the $\textit{restriction}$ of $\rightcat\alpha$}}]{\kern11em}   }   } &&& \rightcat X  &  \kern10em    \\ \end{array}    }$$

$\leftadj{ {\leftcat Y} \times G }$ is the free $\rightcat{ G{-}\Set}$ on the set $\leftcat Y$; 

the unit (just a function) is $\leftadj{ \leftcat Y \times e }$.

The counit, a morphism of $\leftadj G$-algebras, at a $\rightcat{ G{-}\Set \; X }$ is just the $\leftadj G$-action $\leftadj{ {\rightcat X \rightadj U} \times G } \mathrel{\rightadj\to} \rightcat X$.

The above relations may be perspicaciously viewed be embedding them in the 2-category $\CAT$ of large 1-categories.

$$\boxed{   \begin{array} {ccccccccc|l}   &&&&  \calC \calP^\ast &&&&  \calC \calP^\ast   &  \text{Yoneda structure operation }   \calP^\ast  \text{ on } \calC    \\     &&&&  \rightcat\Vert  &&&&  \rightcat\Vert    \\   &&&&  [\calC, \Set]  &&&&  [\calC, \Set]     &    \text{discrete opfibrations (dof) on } \calC   \\    &&&&  \rightcat\Vert  &&&&  \rightcat\Vert    \\    &&&&  [\leftadj G \mathbf B, \Set]  &&&&  [\leftadj G \mathbf B, \Set]  &    \text{discrete opfibrations (dof) on } \leftadj G \mathbf B \\      &&&&  \rightcat\Vert  &&&&  \rightcat\Vert    \\     \I  &  {} \rlap{ \kern-1em \rightcat{  \xrightarrow[\kern11em]{\textstyle X}  }  }   &&&  \GSet  & {} \rlap{ \kern-2em \rightcat{ \xrightarrow[\kern11em]{} } }  &&&  \GSet     \\      &  \leftcat{  \llap Y \searrow  }  &  \rightcat{  \raise1ex{ \smash{ \llap{\exists! \alpha} \Bigg\Uparrow } }  }  &  \leftadj{  \nearrow  \rlap{\scriptstyle \kern-3em ({\leftcat -} \times G)}   }  \leftcat{ \raise.3ex{  \smash{ \Bigg\Uparrow \rlap{ \forall x}  }  }  }  &  \leftadj{  \raise0ex{ \smash{ \Bigg\Uparrow \rlap{\scriptstyle \kern-2em \eta = ({\leftcat -} \times e)}  }  }  }  &  \rightadj{  \searrow \rlap{\kern-1em U}  }  &  \rightadj{  \raise1ex{ \smash{ \Bigg\Uparrow \rlap{\scriptstyle \kern-2em  \epsilon = \text{action}}  }  }  }  &  \leftadj{  \nearrow  \rlap{({\leftcat -} \times G)}   }   &&  \red{\text{the adjointness! :-)} }  \\    &&  \leftcat\Set  &  {} \rlap{ \leftcat{ \kern-1em \xrightarrow{\kern13em} } }  &&&  \leftcat\Set   \\    \end{array}    }$$

The two adjunction triangle equalities are, 

first, that for any set $\leftcat Y$, $\leftcat{ y \in Y}$, and $g \in G$, 

$${\leftcat Y} \times {\leftadj G}  \to   {\leftcat Y} \times {\leftadj G}  :  [\leftcat y] \leftadj g  \mathrel{\leftadj\mapsto}  \big[ [\leftcat y] \leftadj e \big]  \leftadj g  \mathrel{\rightadj\mapsto}   [\leftcat y] \leftadj{(e g)} \xlongequal{\text{left identity axiom for group } \leftadj G}  [\leftcat y] \leftadj g \;  ,$$

and second, that for any  $G$-set $\rightcat X$ and $x \in \rightcat X \rightadj U$, 

$${\rightcat X \rightadj U}  \to {\rightcat X \rightadj U}   :   x \mathrel{\leftadj\mapsto}  [x] \leftadj e  \mathrel{\rightadj\mapsto} (x) \leftadj e  =  x  \leftadj e \xlongequal{\text{identity axiom for action of $\leftadj G$ on $X$}} x  \;  .$$

Note that $\hat{\leftcat x}$ equals

$$\begin{array}{}  \leftadj{ {\leftcat Y} \times  G }  &   \xrightarrow[\kern3em]{\leftadj{ \leftcat x \times G }}  &  \leftadj{  {\rightcat X \rightadj U} \times G  }  &  \rightadj{ \xrightarrow[\kern3em]{\rightcat X \rightadj \epsilon}  }  &  \rightcat X    \\   [\leftcat y] \leftadj g  &  \mapsto  &  [\leftcat {yx}] \leftadj g  &  \mapsto  &  (\leftcat {yx}) \leftadj g   \end{array}$$

<hr />

Here are 2-D, 1-D, and 0-D diagrams for the above situation:

$$\boxed{   \begin{array} {rcc}  {} \rlap{   \kern-21em \text{The Element/Orbit Bijection $\boxed{\leftadj\eta \leftrightarrow \rightcat\alpha}$ (i.e., the Yoneda Lemma) for a Representation $\rightcat X$ of a Group  $G$}   }    \\     \hline   \\     \text{viewing $\CAT$ as a double category (trivial vertical 1-cells)}  &&     \boxed{     \begin{array} {}   \leftcat\calI   &   \leftadj{  \xrightarrow [\kern2em] {\textstyle e}  }   &    \leftadj G    &    \rightcat{  \xrightarrow [\kern2em] {\textstyle X}  }    &    \Set    \\   \leftcat{\Big\vert}  &  \llap g \smash{\Bigg\Uparrow} &   \leftadj{\Big\vert}  &  \rightcat{  \smash{\Bigg\Uparrow} \rlap{ \kern-1.9em \boxed{\alpha = \hat\eta} }  }  &  \Big\vert    \\   \leftcat\calI   &   \leftadj{  \xrightarrow [\kern2em] {\textstyle e}  }   &   \llap{\smash{ {\ulcorner g \urcorner} \Bigg\Uparrow }} {\leftadj G} \rlap{\smash{  \leftadj{ \Bigg\Uparrow \boxed{\eta = \check\alpha} }  }}   &    \leftadj{  \xrightarrow [\kern2em] {\textstyle \hom e G {\leftcat -}}  }    &    \Set    \\     \leftcat{\Big\vert}  &&  \leftadj{ \llap{1_e} \Big\Uparrow }  &&  \Big\vert    \\    \leftcat\calI  &  \leftcat{  {} \rlap{ \kern-2em \xrightarrow [\textstyle 1] {\kern12em} }   }   &&&  \Set    \\     \end{array}     }      \\       \text{2-D, in the very large 2-category $\CAT$ of large 1-categories}   &   \kern2em   &     \boxed{ \begin{array} {} &&  \leftadj G  &  \leftadj{ \xlongequal{\kern1em} }  &   \leftadj G  &  \leftadj{ \xlongequal{\kern1em} }  &  \leftadj G    \\    &   \leftadj{ \llap{e} \nearrow}  &  \buildrel \textstyle g \over \Leftarrow  & \leftadj{ \llap{e} \nearrow } \rlap{\smash{  \kern-1em \Bigg\Uparrow \rlap{ \ulcorner g \urcorner } }}    &   \smash{     \leftadj{   \llap{1_e} \Big\Uparrow  \rlap{\smash{ \kern1.5em \Bigg\Uparrow \rlap{ \boxed\eta } }}   }     }  & \leftadj{   \searrow \rlap{ \kern-2.3em \hom e G - }  }  &  \rightcat{   \buildrel \textstyle {} \rlap{ \kern-1.6em \boxed{\alpha = \hat\eta} } \over \Rightarrow   }  &  \rightcat{  \searrow \rlap X  }    \\     \leftcat\calI  &  \leftcat{ \xlongequal{\kern1em} }  &  \leftcat\calI  &  {} \rlap{  \kern-1.5em \leftcat{ \xrightarrow[\textstyle 1]{\kern9.5em} }  }  &&&  \leftcat\Set  &  \leftcat{ \xlongequal{\kern1em} }  &  \leftcat\Set   \\      \end{array}     }      \\   \\          \text{1-D, in the large category $\Set$ of small sets}   &&    \boxed{    \begin{array} {}  &&  X_e    \\   &  \rightcat{  \llap{ {\alpha}_{\black e} } \nearrow  }  &&  \rightcat{  \nwarrow \rlap{ X_{\black g} }  }   \\    \hom e G e  &&  g{\rightcat\alpha}  &&  {\rightcat X}_e   &     \\     &  \llap{ \hom e G g } \nwarrow  &&  \rightcat{  \nearrow \rlap{ \alpha_{\black e} }  }  \\    && \hom e G e    \\    & \llap{ \ulcorner g \urcorner } \nwarrow  &  {\big\uparrow} \rlap{1_e}  &  \leftadj{   \nearrow \rlap{  \boxed{ \eta = \rightcat{\check\alpha} }  }   } \\    &&    1    \\  \end{array}    }    \\    \\      \text{0-D, in the small set ${\rightcat X}_{\leftadj e}$ }  &&  \boxed{   g{  \rightcat{ \alpha_{\black e} }  } = {\leftadj\eta} g =  \rightcat{\check\alpha} g = g \big( \rightcat{ \hat{\check\alpha} } {\big)}_e  }  \\   \end{array}   }$$  

<hr />

$$\boxed{     \begin{array}  {l|c|c}   \text{action}  &  &  \text{equalities in } \N &  \text{bijections in } \Set   \\   \hline  \text{one object}  &  X \times G \to X &  \text{orbit-stabilizer equation} ; \text{class equation}&  \text{orbit-element bijection} \\  \hline \text{several objects}  & X_c \times {\hom c \calC -} \to X_- &    &  \text{Yoneda lemma}   \\  \end{array}     }$$

<hr />

$\leftadj{ \llap{ \text{(quotient map of ($\red{\hat x}$ cokernel))} } \nearrow }$

$$\boxed{  \begin{array} {}  \rightadj{   \boxed{  \text{Stab}_{\black x} = \text{Aut}_{\black x}  }    }  &  \rightadj\rightarrowtail  & G  &  \leftadj{  \displaystyle \mathop\twoheadrightarrow^{\text{quotient}}_{\text{map}}    }   & \leftadj{   \boxed{  {\black G}{/}\rightadj{ \text{Stab} }_{\black x}  }   }   \\   && \wr\Vert  &&  \red{\wr\Vert} \rlap{  \; (  \leftadj{\text{orbit}} \text{-} \rightadj{\text{stabilizer}} \text{ theorem} )  }    \\    \smash{\rightadj{\Bigg\downarrow}}  &   \smash{     \rightadj{ \raise5ex{\kern-4em \lrcorner} \text{p.b.}  }    }    &   1 \times G  &  \leftadj{  \buildrel \textstyle \black{\hat x} \over \twoheadrightarrow  }  &  \leftadj{   \boxed{  [\black x] = \black{xG}  }   }  \rlap{  \kern0em \xrightarrow[\smash{\kern12em}]{\textstyle !}  }  &&  1  & \kern0em   \\     &&  \llap{  {\ulcorner x \urcorner} \times G  } \Bigg\downarrow   &  \llap{ \scriptstyle  \text{defn. } \red{\hat x} \kern-.6em } \smash{   \red{   \buildrel \textstyle \kern1em \boxed{\hat x} \over \searrow   }   } \rlap{ \scriptstyle \kern-.5em \text{image fact.} }    &  \Bigg\downarrow  &  \smash{     \rightadj{ \raise3ex{\kern-2em \lrcorner} \text{p.b.}  }    }  &  \Bigg\downarrow \rlap{ \ulcorner \leftadj{ [\black x] } \urcorner }  \\   \rightadj{  \boxed{   \black{ (\displaystyle \mathop\rightrightarrows^\tensor_{\pi_X}) } \, \text{Equalizer}   }    }    &  \rightadj\rightarrowtail  &  X \times G  & \displaystyle \mathop\rightrightarrows^\tensor_{\pi_X}  & X {} \rlap{ \kern0em \leftadj{\xrightarrow{\kern5em}}   }  && \leftadj{  \boxed{   \black{ (\displaystyle \mathop\rightrightarrows^\tensor_{\pi_X}) } \, \text{Coeq} = \black X {/} \black G = (\black{X//G})\pi_0   }    }  \\  &&&&  x & \leftadj\mapsto & {} \rlap{   \kern-4em  \leftadj{ [\black x] } = xG = G\hat x = \hat x \, {  \leftadj{ \text{Image} }  }   }     \\    &&&&  X {} \rlap{  \rightadj{ \xleftarrow[\textstyle a]{ \kern1em \text{section} \kern1em } }  }    &&    \leftadj{  \boxed{   \black{ (\displaystyle \mathop\rightrightarrows^\tensor_{\pi_X}) } \, \text{Coeq} = \black X {/} \black G = (\black{X//G})\pi_0   }    }   \\ \end{array}  }$$

$$\boxed{ \displaystyle    X  \buildrel \Gsets \over \cong  \leftadj{ \sum_{[\black x] \in {\black X}/{\black G}} }  \leftadj{ [\black x] }  \buildrel \Gsets \over \cong   \leftadj{  \sum_{ [\black x] \in {\black X}/{\black G}}  } {\black G}{/}\rightadj{ \text{Stab} _{a_{\leftadj{[\black x]}}} }    }$$

(E.g., let $G = \langle \{\pm1\}, \times, +1\rangle$. Then, with (the evident action given algebraically by multiplication or geometrically by reflection), 

$$\boxed{  X = \{-2,-1,0,1,2\}  \cong  \{\pm 2\} \leftadj+ \{\pm1\} \leftadj+ \{0\}  =   [2]  \leftadj+ [1] \leftadj+ [0]  \cong   \{\pm1\}/\rightadj{\{+1\}} \leftadj+ \{\pm1\}/\rightadj{\{+1\}} \leftadj+ \{\pm1\}/\rightadj{\{\pm1\}}    }$$   To see a picture of this $\{\pm1\}$-set,  visit https://golem.ph.utexas.edu/category/2021/07/diversity_and_the_mysteries_of.html   )

The last general result yields, via $|\cdot| : \FinSet_0 \to \N$, (the "<a href="https://ncatlab.org/nlab/show/class+equation">class equation</a>",  an equality of natural numbers in $\N$):  $$\boxed{  |X| = \Big|\sum_{[\black x] \in {\black X}/{\black G}} G/{ \rightadj{ \text{Stab} }_{\black x} } \Big|  = \sum_{[\black x] \in {\black X}/{\black G}} |G/{ \rightadj{ \text{Stab} }_{\black x} }|  = \sum_{[\black x] \in {\black X}/{\black G}} |G|/{ \rightadj{ |\text{Stab} }_{\black x} | } }$$  

which is numerically equivalent to the equality of rational numbers in $\Q$:    $$\boxed{   |X|/|G|   \buildrel \text{above} \over =   \sum_{ [\black x] \in {\black X}/{\black G} } 1/{ \rightadj{ | \text{Stab} }_{\black x} | }  \buildrel \text{defns} \over =   \sum_{ [\black x] \in \pi_0({\black X}//{\black G}) } 1/| \Aut{x} |    \buildrel \text{defn.} \over \equiv  \boxed{ |X//G| }     }$$ , this last (the "<a href="https://ncatlab.org/nlab/show/groupoid+cardinality"><i>groupoid cardinality</i></a>" of the <a href="https://ncatlab.org/nlab/show/action+groupoid"><i>action groupoid</i></a> $\boxed{X//G}$ associated with (the action $X_-$)). Note the usage of (the full-up equality $\boxed{X/G = \pi_0(X//G)}$), and that (the groupoid cardinality) can be defined for (any groupoid), not just (action groupoids).

<hr />

<h3>References</h3>

Im+Kelly, A Universal Property of the Convolution Monoidal Structure

https://doi.org/10.1016/0022-4049(86)90005-8

For possible future use: $\rightadj{\text{counit of }} ( \leftadj{\text{cokernel}} \text{-} \rightadj{\text{kernel}} \text{ adjunction} ) \rightadj{\text{ is here monic}} ) }$

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$.

Cartesian closed categories

This is not intended to give an introduction to cartesian closed categories (“cccs”), which are discussed in many places, e.g. Wikipedia, nlab.
Rather, the aim of this document is simply to compare two extremely significant cccs: $\bftwo$ which is basic to Boolean logic, and $\Set$ which is, of course, basic to set theory.
More precisely, we wish to compare the notations which are used to express the ccc operations, and how several of the simple but significant theorems valid in these cccs are expressed.
In fact, both $\bftwo$ and $\Set$ are, as well as being cartesian closed, are also cocomplete.
So the names of the operators relevant to cocompletion are also shown, with their related simple theorems.

Description		ccc				Comment
		$\bftwo$		$\Set$
initial object		$\bot$		$\emptyset$
terminal object		$\top$		$1$
binary cartesian product		$\wedge$		$\times$
internal hom		$\Rightarrow$		$[,]$
formulae involving the binary product		$\bot\wedge\objA = \bot$		$\emptyset\times\objA \cong \emptyset$		absorption
		$\top\wedge\objA = \objA$		$1\times\objA \cong \objA$		identity or unit
formulae involving the internal hom		$\bot\Rightarrow\objA = \top$		$[\emptyset,\objA] \cong 1$
		$\top\Rightarrow\objA = \objA$		$[1,\objA] \cong \objA$
the product of $\functionA:\setX\to \text{ccc}$ (where $\setX\in\Set$)		$\left\{ \begin{array}{}(\forall \eltx\in\setX)\functionA_\eltx\\ \displaystyle\bigwedge_{\eltx\in\setX}\objA_\eltx\\ \end{array} \right\}$		$\displaystyle\prod_{\eltx\in\setX}\functionA_\eltx$
binary coproduct		$\vee$		$+$ or $\coprod$
formulae involving the binary coproduct		$\bot\vee\objA = \objA$		$\emptyset+\objA \cong \objA$		identity or unit
		$\top\vee\objA = \top$		$1+\objA$
the coproduct of $\functionA:\setX\to \text{ccc}$ (where $\setX\in\Set$)		$\left\{\begin{array}{}(\exists\eltx\in\setX)\functionA_\eltx\\ \displaystyle\bigvee_{\eltx\in\setX}\objA_\eltx\\ \end{array} \right\}$		$\displaystyle\sum_{\eltx\in\setX}\functionA_\eltx$

Monoidal closed categories and extraordinary naturality

Consider a monoidal closed category, with objects and the labeled arrows as in any of the three diagrams below
(the only differences between them are (affine transformations, a reflection, a horizontal shear and a rotation) on the diagrams).
The unlabeled arrows should be understood to be either
(unnamed variables) of (the specified source-target type), or, alternatively,
[the hom objects, e.g. $[\objectA\backslash\objectB]$] determined by (the source and target of (the unlabeled arrows)).

$\begin{array}{} \objectA' & {}\rlap{\xrightarrow{\mkern6em}} &&& \objectB && &&&& && \objectA & {}\rlap{\xrightarrow{\mkern6em}} &&& \objectB' &&&& \objectA' & \xrightarrow{\smash{\textstyle \;\arrowf\;}} & \objectA \\ & \llap\arrowf \searrow && \nearrow && \searrow \rlap\arrowh & & \mkern2em & \text{reflection} & \mkern2em & & \llap\arrowf \nearrow && \searrow && \nearrow \rlap\arrowh & & \mkern2em & \text{h.s. and rotation} & \mkern2em & \big\downarrow & \swarrow & \big\downarrow \\ && \objectA & {}\rlap{\xrightarrow{\mkern6em}} &&& \objectB' &&&& \objectA' & {}\rlap{\xrightarrow{\mkern6em}} &&& \objectB && &&&& \objectB & \xrightarrow[\smash{\textstyle \;\arrowh\;}]{} & \objectB' \\ \end{array}$

In such a situation, we have the following commutative cubical diagram:

$\begin{array}{} &&&&& 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & \objectA' &&&& \boxed{ \begin{array}{} \elta'&&\arrowg \\ {\objectA'}&\tensor&[\objectA\backslash\objectB]\\ \end{array} } & {}\rlap{ \mkern-1em\xrightarrow[\mkern14em]{\textstyle {\objectA'} \tensor \boxed{[\arrowf\backslash\objectB]}} } && \boxed{ \begin{array}{} \elta'&&\arrowf\arrowg \\ {\objectA'} & \tensor & [{\objectA'}\backslash\objectB]\\ \end{array} } \\ 2 && \llap\arrowf \searrow &&& & \llap{\arrowf \tensor [\objectA\backslash\objectB]} \searrow & {}\rlap{ \mkern1em\boxed{\boxed{\hom \arrowf \arrowe \objectB = \text{U}}} } && \searrow \rlap{\hom {\objectA'} \arrowe \objectB} \\ 3 &&& \objectA & \mkern2em & && \boxed{ \begin{array}{} \elta'\arrowf&&\arrowg \\ \objectA&\tensor&[\objectA\backslash\objectB]\\ \end{array} } & {} \rlap{ \mkern-4em\xrightarrow[\mkern14em]{\smash{\textstyle \hom \objectA \arrowe \objectB} } } && \boxed{ \begin{array}{} \elta'\arrowf\arrowg \\ \objectB\\ \end{array} } \\ 4 &&&&& \llap{{\objectA'} \tensor [\objectA\backslash\arrowh]} \Bigg\downarrow & {} \rlap{ \mkern1em \boxed{\boxed{{\objectA'} \tensor [\arrowf\backslash\arrowh] = \text{B}}} } && \Bigg\downarrow \rlap{{\objectA'} \tensor \boxed{[{\objectA'}\backslash\arrowh]}} \\ 5 &&&&& & {} \rlap{ \mkern-3.5em \boxed{\boxed{\arrowf \tensor [\objectA\backslash\arrowh] = \text{L}}} } & {} \rlap{ \mkern2em \smash{\boxed{\boxed{\boxed{\hom \arrowf \arrowe \arrowh}}} \mkern7em \boxed{\boxed{\hom {\objectA'} \arrowe \arrowh = \text{R}}}} } \\ 6 &&&&& && \llap{\objectA \tensor \boxed{[\objectA\backslash\arrowh]}} \Bigg\downarrow & \boxed{\boxed{\hom \objectA \arrowe \arrowh = \text{F}}} && \Bigg\downarrow\rlap\arrowh \\ 7 &&&&& \boxed{ \begin{array}{} \elta'&&\arrowg\arrowh \\ {\objectA'}&\tensor&[\objectA\backslash{\objectB'}]\\ \end{array} } & {}\rlap{ \mkern-1em\xrightarrow[\mkern14em]{\textstyle {\objectA'} \tensor \boxed{[\arrowf\backslash{\objectB'}]}} } && \boxed{ \begin{array}{} \elta'&&\arrowf\arrowg\arrowh \\ {\objectA'}&\tensor&[{\objectA'}\backslash{\objectB'}]\\ \end{array} } \\ 8 &&&&& & \llap{\arrowf \tensor [\objectA\backslash{\objectB'}]} \searrow & {}\rlap{ \mkern1em\boxed{\boxed{\hom \arrowf \arrowe {\objectB'} = \text{D}}} } && \searrow \rlap{\hom {\objectA'} \arrowe {\objectB'}} \\ 9 &&&&& && \boxed{ \begin{array}{} \elta'\arrowf&&\arrowg\arrowh \\ \objectA&\tensor&[\objectA\backslash{\objectB'}]\\ \end{array} } & {} \rlap{ \mkern-4em\xrightarrow[\mkern14em]{\smash{\textstyle \hom \objectA \arrowe {\objectB'} } } } && \boxed{ \begin{array}{} \elta'\arrowf\arrowg\arrowh \\ {\objectB'}\\ \end{array} } \\ \end{array}$

The boxes (other than those enclosing the eight vertices of the cube) have the following meanings:
A single box, e.g. $\boxed{[\arrowf\backslash\objectB]}$, denotes an arrow determined by the universal condition on a universal arrow, $\hom {\objectA'} \arrowe \objectB$ in this case.
A double box, e.g. $\boxed{\boxed{\hom \arrowf \arrowe \objectB = \text{U}}}$, denotes a commuting square = commuting face of the cube;
we use “Rubik’s cube” abbreviations to designate the faces of the cube: Up/Down, Left/Right, Front/Back.
The triple box, $\boxed{\boxed{\boxed{\hom \arrowf \arrowe \arrowh}}}$, denotes the total cube determined by $\arrowf$ and $\arrowh$.

The commutative squares (faces of the cube) labeled $\boxed{\boxed{\hom \objectA \arrowe \arrowh = \text{F}}}$ and $\boxed{\boxed{\hom {\objectA'} \arrowe \arrowh = \text{R}}}$
define the covariant arrows $\boxed{[\objectA\backslash\arrowh]}$ and $\boxed{[{\objectA'}\backslash\arrowh]}$, and then witness the ordinary naturality of $\arrowe$ WRT (with respect to) $\arrowh$.
The commutative squares labeled $\boxed{\boxed{\hom \arrowf \arrowe \objectB = \text{U}}}$ and $\boxed{\boxed{\hom \arrowf \arrowe {\objectB'} = \text{D}}}$
define the contravariant arrows $\boxed{[\arrowf\backslash\objectB]}$ and $\boxed{[\arrowf\backslash{\objectB'}]}$, and then witness the extraordinary naturality of $\arrowe$ WRT $\arrowf$.
The commutativity of $\boxed{\boxed{\arrowf \tensor [\objectA\backslash\arrowh] = \text{L}}}$ is simply because $\tensor$ is a bifunctor.
The commutativity of the $[\arrowf\backslash\arrowh]$ square (a $\tensor$-factor of the $\boxed{\boxed{{\objectA'} \tensor [\arrowf\backslash\arrowh] = \text{B}}}$ square)
is determined by the commutativity of the $\text{R}, \text{U}, \text{F}, \text{L}, \text{D}$ faces, plus the uniqueness clause applied to $\hom {\objectA'} \arrowe {\objectB'}$.
The cube itself, labeled $\boxed{\boxed{\boxed{\hom \arrowf \arrowe \arrowh}}}$, witnesses the joint (simultaneous) naturality of $\arrowe$ WRT both $\arrowf$ and $\arrowh$.

This is a variation on a diagram in paragraph 1.3.2 of MVFC.

---

References

MVFC, Max Kelly, “Many-variable functorial calculus”, 1972

---

Draft stuff:

Powers and copowers

Let $\calA$ be a category, enriched in a closed category $\calV$.
($\calV$ closed) means, in particular, that (for all $\objX, \objY \in \calV$ there is an internal hom $\boxed{[\objX,\objY]} \in \calV$, satisfying certain axioms).
($\calA$ enriched in $\calV$) implies that (for all $\objA, \objB \in \calA$ there is a hom object $\boxed{\hom \objA \calA \objB} \in \calV$, satisfying certain axioms).
To say that ($\calA$ admits powers and copowers relative to $\calV$) means precisely that,
(for all $\objX\in\calV$ and $\objA,\objB\in\calA$ there are isomorphisms in $\calV$ as shown below, $\calV$-natural in all their variables).
Shown below the isomorphisms are (the units and counits associated with those natural isomorphisms)
(the identifier $\Eval$ is overloaded, relying on context to disambiguate occurrences of it). $$\begin{array}{cclcc} \hom \objA \calA {\boxed{\scriptstyle \objX\power\objB}} & \buildrel {\textstyle \overline{()}} \over \cong & \big[ \objX, \hom \objA \calA \objB \big] & \buildrel {\textstyle \widetilde{()}} \over \cong & \hom {\boxed{\scriptstyle \objX\copower\objA}} \calA \objB \\ \\ \objA \xrightarrow [ \smash {\textstyle \Eval } ]{} \hom \objA \calA \objB \power \objB && \objX \xrightarrow{\textstyle \pi} \smash { \hom {\objX\power\objB} \calA \objB } \\ && \mkern4mu \Vert \\ && \objX \xrightarrow [ \textstyle \iota ]{} \hom \objA \calA {\objX\copower\objA} && \hom \objA \calA \objB \copower \objA \xrightarrow [ \smash {\textstyle \Eval } ]{} \objB \\ \end{array}$$

---

The following display shows how (an $\objX \xrightarrow{\textstyle \boxed\functionf} \hom \objA \calA \objB$ in $\calV_0$) determines ($\objA \xrightarrow{\textstyle \boxed{\bar\functionf}} \objX\power\objB$ and $\objX\copower\objA \xrightarrow{\textstyle \boxed{\tilde\functionf}} \objB$ in $\calA_0$), and vice versa,
using the units and counits of the isomorphisms (whatever they may be named). $$\begin{array}{} & \calA_0 & & \mkern4em & && \calV_0 && & \mkern4em & & \calA_0 \\ \\ &&&&&& \objX \\ &&&&& {}\rlap{\mkern-.5em \raise4pt\hbox{$\boxed\pi$}} \swarrow && \searrow \rlap{\mkern-1ex \raise4pt\hbox{$\boxed\iota$}} \\ \objX\power\objB && && \hom {\objX\power\objB} \calA \objB && \Bigg\downarrow \rlap{\mkern-13mu\boxed\functionf} && \hom \objA \calA {\objX\copower\objA} &&& & \objX\copower\objA \\ \llap{\functionf\power\objB} \Bigg\uparrow & \nwarrow \rlap{\mkern-1ex \raise4pt\hbox{$\boxed{\bar\functionf}$}} & && & \llap{\hom {\bar\functionf} \calA \functionB} \searrow && \swarrow \rlap{\hom \objA \calA {\tilde\functionf}} & && & {}\rlap{\mkern-.5em \raise4pt\hbox{$\boxed{\tilde\functionf}$}} \swarrow & \Bigg\downarrow \rlap{\functionf\copower\objA} \\ {\hom \objA \calA \objB} \power \objB & \xleftarrow[\textstyle \boxed\Eval]{} & \objA && && \hom \objA \calA \objB && && \objB & \xleftarrow[\textstyle \boxed\Eval]{} & {\hom \objA \calA \objB} \copower \objA \\ \end{array}$$

Double categories

$\def\sh{\source{\text s}\black{\text{-h}}} \def\th{\target{\text t}\black{\text{-h}}} \def\sv{\source{\text s}\black{\text{-v}}} \def\tv{\target{\text t}\black{\text{-v}}}$ $\bbox[navajowhite,24px,border:4px groove red]{\begin{array}{} \cdotp & \source{\xrightarrow{\textstyle\sv}} & \cdotp \\ \llap\sh \source{\big\downarrow} & & \target{\big\downarrow} \rlap\th\\ \cdotp & \target{\xrightarrow[\textstyle\tv]{}} & \cdotp \end{array}}$

Loosely, a "double category" is a collection of abstract "squares",
of the form shown in the box at right.
Going either vertically or horizontally they form a category, with composition and identities.
Further, the compositions are compatible, a condition called the interchange law,
meaning that if four of them form a compatible 2x2 square, then
performing first horizontal, then vertical composition yields the same result as
performing first vertical, then horizontal composition.
That is a "symmetrical" definition of a double category.

There is also an unsymmetrical definition, which is also useful in many situations.
It defines a double category as an (internal) category in the category of categories, $\Cat$.

To best understand it we should briefly review the definition of internal category.
It starts with the notion of a graph in a category,
namely a diagram in that category of the form $$\begin{array}{} X_0 & \mathop\leftleftarrows\limits^{\source s}_{\target t} & X_1\end{array}$$ Here $X_0$ is the "object of objects" and $X_1$ is the "object of arrows" of the category,
and the two arrows provide the source and target for the "arrows" in $X_1$.
A morphism of such graphs is a diagram of the form $$\begin{array}{} X_0 & \mathop\leftleftarrows\limits^{s_X}_{t_X} & X_1\\ \llap{f_0}\big\downarrow && \big\downarrow\rlap{f_1}\\ Y_0 & \mathop\leftleftarrows\limits^{s_Y}_{t_Y} & Y_1\\ \end{array}$$ which serially commutes, meaning that $s_X f_0 = f_1 s_Y$ and $t_X f_0 = f_1 t_Y$.
(If we view a graph $X$ in a category as
a functor $X$ from the abstract graph shape $\leftleftarrows$ to the category,
then this condition amounts to saying
$f$ is a natural transformation from the functor $X$ to the functor $Y$.)
Finally, to make a graph $X$ a category,
there must be defined a composition operation and an identity operation for the graph.
(We skip the details, see CWM, Chapter II, Section 7
or references on the web.)

Let use that definition to define an internal category in the category of internal categories (internal to the category of small sets, $\Set$).
It has an underlying graph of the form (drawn vertically for reasons soon to appear) $$\begin{array}{} C_1\\ \llap\sv\source{\big\downarrow}\target{\big\downarrow}\rlap\tv\\ C_0 \end{array}$$ Since this is a diagram of internal categories,
$C_0$ and $C_1$ are themselves categories internal to $\Set$,
and $\sv$ and $\tv$ are internal functors, thus also graph morphisms, from $C_1$ to $C_0$.
Expanding the definitions, we have a diagram in $\Set$ $$\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{} V & = & (C_1)_0 & \mathop\leftleftarrows\limits^{\source{\textstyle\sh}}_{\target{\textstyle\th}} & (C_1)_1 & = & \{\,\text{squares}\,\}\\ & & \llap\sv\source{\big\downarrow} \target{\big\downarrow}\rlap\tv & & \llap\sv\source{\big\downarrow} \target{\big\downarrow}\rlap\tv \\ \{\,\text{0-cells}\,\} & = & (C_0)_0 & \mathop\leftleftarrows\limits^{\source{\textstyle\sh}}_{\target{\textstyle\th}} & (C_0)_1 & = & H\\ \end{array}}$$ which serially commutes
(i.e., when matching top and bottom, and left and right, arrows are paired;
there are four such pairs, to be depicted momentarily).
The reasons for the $V$ and $H$ will also appear momentarily.

Okay, that diagram gives the internal category representation of this structure.
But now let us redraw that same data in a form which shows how this gives
the source and target operations for squares,
and explicitly shows the four squares (in $\Set$) required to commute to give serial commutativity.
Specifically: $$\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{} \\ &&& H\\[-4ex] &&& \parallel\\[-4ex] & (C_0)_0 & \source{\xleftarrow{\textstyle\sh}} & (C_0)_1 & \target{\xrightarrow{\textstyle\th}} & (C_0)_0\\ & \llap{\textstyle\sv}\source{\big\uparrow} && \llap{\textstyle\sv}\source{\big\uparrow} && \source{\big\uparrow}\rlap{\textstyle\sv}\\ V =\!\!\! & (C_1)_0 & \source{\xleftarrow{\textstyle\sh}} & (C_1)_1 & \target{\xrightarrow{\textstyle\th}} & (C_1)_0 & \!\!\!= V\\ & \llap{\textstyle\tv}\target{\big\downarrow} && \llap{\textstyle\tv}\target{\big\downarrow} && \target{\big\downarrow}\rlap{\textstyle\tv}\\ & (C_0)_0 & \source{\xleftarrow[\textstyle\sh]{}} & (C_0)_1 & \target{\xrightarrow[\textstyle\th]{}} & (C_0)_0\\[-2ex] &&& \Vert\\[-2ex] &&& H\\ \end{array}}$$ So we have:
$(C_1)_1$ = the set of all the squares,
$(C_1)_0$ = the set of all the vertical arrows, which we may call $V$,
$(C_0)_1$ = the set of all the horizontal arrows, which we may call $H$, and
$(C_0)_0$ = the set of all the 0-cells,
and $\sv$, $\tv$, $\sh$, and $\th$ give the source-target operations at all the requisite levels.

---

The sketch for the last display:  

$$\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{} \\ &&& H\\[-4ex] &&& \parallel\\[-4ex] & (0,0) & \source{\xleftarrow{\textstyle (s,0) }} & (1,0) & \target{\xrightarrow{\textstyle (t,0) }} & (0,0) \\ & \llap{\textstyle (0,s) }\source{\big\uparrow} && \llap{\textstyle.(1,s)}\source{\big\uparrow} && \source{\big\uparrow}\rlap{\textstyle (0,s) }\\ V =\!\!\! & (0,1) & \source{\xleftarrow{\textstyle (s,1)}} & (1,1) & \target{\xrightarrow{\textstyle (t,1)}} & (0,1) & \!\!\!= V\\ & \llap{\textstyle (0,t) }\target{\big\downarrow} && \llap{\textstyle (1,t)}\target{\big\downarrow} && \target{\big\downarrow}\rlap{\textstyle (0,t) }\\ & (0,0) & \source{\xleftarrow[\textstyle (s,0) ]{}} & (1,0) & \target{\xrightarrow[\textstyle (t,0) ]{}} & (0,0) \\[-2ex] &&& \Vert\\[-2ex] &&& H\\ \end{array}}$$

<hr />

The sketch folded, i.e.

the endospan replaced by a parallel pair.

$$\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{} V = \!\!\! & (0,1) & \mathop\leftleftarrows\limits^{\textstyle \source {(s,1)}}_{\textstyle \target {(t,1)}} & (1,1)  &  \!\!\!  =  C  \\ & \llap{\textstyle (0,s) } \source{\big\downarrow} \target{\big\downarrow} \rlap{\textstyle (0,t) }  && \llap{\textstyle (1,s)} \source{\big\downarrow} \target{\big\downarrow} \rlap{\textstyle (1,t)} \\ O  = \!\!\! &  (0,0) & \mathop\leftleftarrows\limits^{\textstyle \source {(s,0)}}_{\textstyle \target {(t,0)}} & (1,0) &  \!\!\!  = H  \\ \end{array}}$$

Bifunctors, bimodules, and profunctors

Preliminary draft.

Let $\calV$ be a symmetric monoidal category, and $\calA$, $\calB$, and $\calC$ be categories enriched in $\calV\,$.
We consider bifunctors (functors of two variables) which are (contravariant on the left) and (covariant on the right):
$$\begin{array}{cccl} \calA\op \tensor \calB & \xrightarrow{\textstyle \boxed\functorF} & \calC & & \text{the bifunctor} \\ \objectA,\objectB & \mapsto & \boxed{\hom \objectA \functorF \objectB} & & \text{the bifunctor's action on objects} \\ \hom {\objectA,\objectB} {(\calA\op \tensor \calB)} {\objectAp,\objectBp} \xlongequal[\textstyle \text{defn.} \tensor]{} \hom \objectA {\calA\op} \objectAp \tensor \hom \objectB \calB \objectBp \xlongequal[\textstyle \text{defn.} \op]{} \hom \objectAp \calA \objectA \tensor \hom \objectB \calB \objectBp & \xrightarrow[\textstyle \boxed{\hom {\objectA,\objectB} \functorF {\objectAp,\objectBp}}]{} & \hom {\hom \objectA\functorF\objectB} \calC {\hom \objectAp\functorF\objectBp} & & \text{the bifunctor's action on hom-objects} \\ \end{array}$$ For (the general bifunctor), just (drop the $\op$ from $\calA\op$).

---

The next display is a schematic representation of the last line of the above display,
showing the components of (the bifunctor's action $\boxed{\hom {\objectA,\objectB} \functorF {\objectAp,\objectBp}}$ on hom-objects).
$$\begin{array} {} \objectA & \xrightarrow{\textstyle \hom \objectA \functorF \objectB \in \calC} & \objectB \\ \llap{ \calV \ni \hom \objectA {\calA\op} \objectAp = \hom \objectAp \calA \objectA } \Bigg\uparrow & \llap{\hom {\hom \objectA\functorF\objectB} \calC {\hom \objectAp\functorF\objectBp}} \Bigg\downarrow \rlap{{} \in \calV} & \Bigg\downarrow \rlap{\hom \objectB \calB \objectBp \in \calV} \\ \objectAp & \xrightarrow[\textstyle \hom \objectAp \functorF \objectBp \in \calC]{\mkern10em} & \objectBp \\ \end{array}$$ Note how this display "spreads out", literally diagrams, those components of the one-line notation,
while also showing explicitly some (otherwise implicit) typing information.
Not explicitly shown are (the tensor product, $\tensor$), and (the arrow $\hom {\objectA,\objectB} \functorF {\objectAp,\objectBp}$ itself).
The tensor product is of (what the two outer vertical arrows represent),
while the arrow $\hom {\objectA,\objectB} \functorF {\objectAp,\objectBp}$ itself is from (that tensor product) to (what is represented by the inner vertical arrow).

---

We now consider several important special cases of such contra-co bifunctors.

First, consider the case where (the target category $\calC$) is (the base for enrichment, $\calV$), so the bifunctor is $\boxed{\functorF : \calA\op \tensor \calB \longrightarrow \calV}$.
This particular form of bifunctor, contravariant on the left, covariant on the right, and taking values in $\calV$,
may be (and usually is) called a $\calV$-valued bimodule.

Second, we specialize even more to the case where $\calV$ is not merely symmetric monoidal, but symmetric monoidal closed.
This is actually the case which the nLab article considers.

Third are the cases where $\calV$ is cartesian closed.
We display below the explicit data for $\functorF$ in this situation,
replacing (the tensor product) with (the cartesian product)
and (the $\hom \setX \calV \setY$ notation for $\calV$'s hom) with (the $[\objectX,\objectY]$ notation (often written $\objectY^\objectX$) often used for internal homs). $$\begin{array}{cccl} \calA\op \times \calB & \xrightarrow{\textstyle \boxed\functorF} & \calV & & \text{the bifunctor} \\ \objectA,\objectB & \mapsto & \boxed{\hom \objectA \functorF \objectB} & & \text{the bifunctor's action on objects} \\ \hom {\objectA,\objectB} {(\calA\op \times \calB)} {\objectAp,\objectBp} \xlongequal[\textstyle \text{defn.} \times]{} \hom \objectA {\calA\op} \objectAp \times \hom \objectB \calB \objectBp \xlongequal[\textstyle \text{defn.} \op]{} \hom \objectAp \calA \objectA \times \hom \objectB \calB \objectBp & \xrightarrow[\textstyle \boxed{\hom {\objectA,\objectB} \functorF {\objectAp,\objectBp}}]{} & [\hom \objectA\functorF\objectB , \hom \objectAp\functorF\objectBp] & & \text{the bifunctor's action on hom-objects} \\ \end{array}$$ Then the schematic representation becomes: $$\begin{array} {} \objectA & \xrightarrow{\textstyle \hom \objectA \functorF \objectB \in \calV} & \objectB \\ \llap{ \calV \ni \hom \objectA {\calA\op} \objectAp = \hom \objectAp \calA \objectA } \Bigg\uparrow & \llap{ [\hom \objectA\functorF\objectB , \hom \objectAp\functorF\objectBp] } \Bigg\downarrow \rlap{{} \in \calV} & \Bigg\downarrow \rlap{\hom \objectB \calB \objectBp \in \calV} \\ \objectAp & \xrightarrow[\textstyle \hom \objectAp \functorF \objectBp \in \calV]{\mkern12em} & \objectBp \\ \end{array}$$

In this ($\calV$ cartesian-closed case) we can take (the exponential transpose of $\hom {\objectA,\objectB} \functorF {\objectAp,\objectBp}$), to give (an equivalent form of it): $$\boxed{ \hom \objectAp \calA \objectA \times \hom \objectA\functorF\objectB \times \hom \objectB \calB \objectBp \xrightarrow[\textstyle \boxed{\hom {\objectA,\objectB} \functorF {\objectAp,\objectBp}}]{} \hom \objectAp\functorF\objectBp } \; ,$$ (the customary form) for (the two-sided action map of a bimodule).
Note how we use the same notation, $\hom {\objectA,\objectB} \functorF {\objectAp,\objectBp}\;$, for two different arrows in $\calV$,
which correspond under $\calV\mkern2mu$'s closedness adjunction.

---

Work in progress:

Monoidal, cartesian, and closed categories

	closed?
cartesian?	monoidal $\; \tensor$ $\hom R \Mod R$ for $R$ a noncommutative ring	monoidal closed $\; \tensor, \; [{-},{-}]$ $\AbGrp$
	cartesian $\; \times$ $\Top$	cartesian closed $\; \times, \; [{-},{-}]$ $\Set$

---

References

[CKVW] Carboni, A.; Kelly, G. M.; Verity, D.; Wood, R. J. (1998). "A 2-Categorical Approach To Change Of Base And Geometric Morphisms II". Theory and Applications of Categories. 4 (5): 82–136.
This reference defines and extensively discusses a variation on the above definition,
namely, the case where the target category is $\CAT$, considered as a bicategory, and the actions are not necessarily strict, but are allowed to be pseudo.
Numerous examples of such structures are given, and the general theory is extensively studied.

[CIC] Street, Ross (1980). "Cosmoi of internal categories". Trans. Amer. Math. Soc. 258 (2): 278–318. doi:10.1090/S0002-9947-1980-0558176-3. MR 0558176.
Section 1 of this gives the appropriate form of the Grothendieck construction when $\calC=\calV=\Cat$.
This is a 2-functor $\boxed{ \calG : [\calA\op \times \calB, \Cat] \to \Cat\downarrow (\calB\times\calA) }$ which has a left adjoint $\boxed\calM$ --
see (1.5)-(1.7) of Street's paper for this, and the rest of its Section 1 for the relation of this adjunction to split fibrations.

The bimodule of sets, functions and permutations, and its quotients

1. Introduction to the bimodule of sets, functions, and permutations
2. Quotients: the “twelvefold way”; the twelvefold way diagram
3. An example: $\homst {[4]} \Set {\{a,b\}}$
4. Division (quotient) as (tensor product) with (the terminal bimodule)

This situation is worth careful consideration because, not only is it fundamental to combinatorics,
but also because it is a model for many situations more complex than merely the category of sets $\Set$.

---

1. Introduction to the bimodule of sets, functions, and permutations

Let $\source \setX$ and $\target \setY$ be arbitrary sets in the category of sets $\Set$.
Consider the groups of permutations $\source{\boxed{\symsX}}$ and $\target{\boxed{\symtY}}$ of $\source \setX$ and $\target \setY$ respectively,
and also the set $\boxed{\SetXY}$ of all $|\settY|^{|\setsX|}$ functions from $\source \setX$ to $\target \setY$.
There are two actions:
The group $\symsX$ of permutations of $\setX$ acts on $\SetXY$ by precomposition, while
the group $S_\setY$ of permutations of $\setY$ acts on it by postcomposition: $$\begin{array}{c} {\source{S_\setX}} \times \SetXY & \source\to & \SetXY\\ \langle \ssigma ,f\rangle & \source\mapsto & \ssigma f\end{array} \mkern6em \hbox{and} \mkern6em \begin{array}{c} \SetXY \times \target{S_\setY} & \target\to & \SetXY\\ \langle f,\ttau \rangle & \target\mapsto & f\ttau . \end{array}$$ These actions are each associative and unital.
Also they commute with each other:
mixed pre-post actions are of the form

$\source{\setX \xrightarrow{\sigma} \setX} \xrightarrow{f} \target{\setY \xrightarrow{\tau} \setY}$

which yields

$\smash{\begin{array}{} && \setsX & {} \rlap{\mkern-1em \xrightarrow[\smash{\mkern8em}]{\displaystyle \functionf\ttau}} &&& \settY \\ & \source{ \llap{\symsX\ni\sigma} \nearrow } & \Vert & \searrow \rlap{\mkern-1em\functionf} & \Vert & \target{ \nearrow \rlap{\tau\in\symtY} } \\ \setsX & {}\rlap{\mkern-1em \xrightarrow[\displaystyle \ssigma\functionf]{\mkern8em}} &&& \settY \\ \end{array}}$

yielding

$\setsX \xrightarrow{\displaystyle \ssigma\functionf\ttau} \settY$

where $\source{\sigma\in S_\setX}$, $f\in \SetXY$, and $\target{\tau\in {S_\setY}}$.
Since (function composition is associative), (the two actions commute): $(\ssigma f)\ttau = \ssigma (f\ttau)$, yielding $\ssigma\functionf\ttau$.

So in addition to (the two one-sided, single actions)
there is (a double, simultaneous action from both sides),
which may be represented either
as a triple product, with (the action actors coming from each side simultaneously): $$\begin{array}{c} \source{S_\setX \times {}} \SetXY \target{{} \times S_\setY} & \to & \SetXY\\ \langle \ssigma, f, \ttau \rangle &\mapsto &\ssigma f \ttau\\ \end{array}$$ or as a binary product, with (one factor itself being a product), and with (the joint, combined, again simultaneous, action coming from the right): $$\begin{array}{c} \SetXY \times (\source{S_\setX\op} \times \target{S_\setY}) &\to &\SetXY\\ \bigl\langle f, \langle \ssigma,\ttau \rangle \bigr\rangle &\mapsto & \ssigma f \ttau .\\ \end{array}$$ (Associativity of the two-sided action) is (the vertical left hand equality) in $$\begin{array}{cl} \bigl\langle \source{\sigma'}, \langle \ssigma, f, \ttau \rangle, \target{\sigma'} \bigr\rangle & \xlongequal{\text{action}} \bigl\langle \source{\sigma'}, \ssigma f \ttau , \target{\sigma'} \bigr\rangle \xlongequal{\text{action}} \source{\sigma'}(\ssigma f \ttau) \target{\tau'}\\ \llap{\scriptstyle \text{action assoc }}\Vert\rlap{\text{ ???}}\\ \bigl\langle \source{\sigma'\sigma}, f, \target{\tau\tau'} \bigr\rangle & \xlongequal{\text{action}} \source{(\sigma'\sigma)} f \target{(\tau\tau')} .\end{array}$$ (Equality of the right-hand sides) follows from (the associativity of function composition), and associativity of the action follows.

In the action where (the action actors both come from the right),
the ${}^{\rm op}$ is necessary (to make the action associative),
as shown by the following, where (the desired associativity of the action) is again (the vertical equality on the left).

$\smash{\begin{array}{} \setsX & \xrightarrow[\smash{\mkern3em}]{\displaystyle \functionf} & \settY \\ \source{\llap\ssigma \uparrow} && \target{\downarrow\rlap\ttau} \\ \setsX && \settY \\ \source{\llap{\ssigma'} \uparrow} && \target{\downarrow \rlap{\ttau'}} \\ \setsX && \settY \\ \end{array}}$

$$\begin{array}{cl} \bigl(f\langle\ssigma,\ttau \rangle\bigr)\langle\source{\sigma'},\target{\tau'}\rangle &\xlongequal{\text{action}} (\ssigma f \ttau)\langle\source{\sigma'},\target{\tau'}\rangle \xlongequal[\class{red}{*}]{\text{action}} \source{\sigma'}(\ssigma f \ttau)\target{\tau'}\\ \llap{\scriptstyle \text{action assoc }}\Vert\rlap{\text{ ???}}\\ f \bigl(\langle \ssigma,\ttau \rangle \langle\source{\sigma'},\target{\tau'}\rangle \bigr) & \xlongequal[\class{red}{*}]{\source{\text{composition in $\symsX\op$}}} f \langle \source{\sigma' \sigma}, \target{\tau \tau'} \rangle \xlongequal{\text{action}} \source{(\sigma'\sigma)} f \target{(\tau\tau')} \\ \end{array}$$ (The right-hand sides are again equal) by (the associativity of function composition in the diagram at right);
the desired associativity of (the action with right actors) follows.
Note that (the equalities where $\source{\sigma'}$ skips over $\ssigma$) are marked by (a $\class{red}{*}$).

$\begin{array}{} \functionf & \target{\xrightarrow[\mkern3em]{\displaystyle \ttau}} & \functionf\ttau \\ \llap\ssigma \big\downarrow && \llap\ssigma \big\downarrow \\ \big( \functiong = \ssigma\functionf \big) & \target{\xrightarrow[\displaystyle \ttau]{\mkern3em}} & \big( \functiong\ttau = (\ssigma\functionf)\ttau = \ssigma(\functionf\ttau) \big) \\ \end{array}$

Since the actions commute,
each action respects ((the equivalence relation) determined by (the other action)).
For example, if $f \source{{} \equiv_{S_\setX}} g$, then $\source{(\exists \sigma\in S_\setX)}(g= \ssigma f)$,
so, for all $\tau \in S_\setY$, and using the same $\sigma\in S_\setX$,
we have $g\ttau = (\ssigma f)\ttau = \ssigma(f\ttau)$, so $f\ttau \source{{} \equiv_{S_\setX}} g\ttau$.
The diagram, in the associated double groupoid, at right illustrates the situation.
And similarly if the roles of $\source \setX$ and $\target \setY$ are reversed.

Thus we have action maps $\source{\big(\symsX \backslash} \SetXY\source{\big)} \times \symtY \mathrel{\target{\xrightarrow{\text{action}}}} \source{\big(\symsX \backslash} \SetXY\source{\big)}$ and $\symsX \times \target{\big(} \SetXY \target{{} / \symtY \big)} \mathrel{\source{\xrightarrow{\text{action}}}} \target{\big(} \SetXY \target{{} / \symtY \big)}$,
and may form the two iterated quotients (quotients of quotients): $\boxed{ \source{( S_\setX \backslash } \SetXY \source) \target{/ S_\setY} }$ and $\boxed{ \source{S_\setX \backslash } \target( \SetXY \target{/ S_\setY )} }$ .

The five quotients of $\SetXY$ : two single, two iterated, one double

$\begin{array}{} \SetXY & {} \rlap{ \mkern-.5em\target{\xrightarrow[\mkern18em]{\displaystyle \functiont}} } &&& \mkern1em \SetXY \target{ / S_\setY} \\ &&&& \source{\big\downarrow} \\ \smash{\source{\llap\functions \Bigg\downarrow}} && \searrow \rlap\functionr && \source{S_\setX \backslash } \target( \SetXY \target{/ S_\setY )} \\ &&&& \wr\Vert \\ \source{S_\setX \backslash} \SetXY & {} \rlap{\mkern-.5em\target\longrightarrow} & \mkern1em \source{( S_\setX \backslash } \SetXY \source) \target{/ S_\setY} & \cong & \source{S_\setX \backslash} \SetXY \target{/ S_\setY} \\ \end{array}$

From either the two-sided action, $\langle \ssigma, f, \ttau \rangle \mapsto \ssigma f \ttau ,$
or the action of the product group ${\source{S_\setX}^{\text{op}}} \times {\target{S_\setY}}$, $\bigl\langle f, \langle \ssigma,\ttau \rangle \bigr\rangle \mapsto \ssigma f \ttau,$
on $\SetXY$
we have a third quotient, which we denote by $\boxed{\source{S_\setX \backslash} \SetXY \target{/ S_\setY}}$,
representing the result of dividing out simultaneously by the two actions,
with its quotient map $\SetXY \longrightarrow \source{S_\setX \backslash} \SetXY \target{/ S_\setY}$.
There are canonical bijections between all three quotient sets
which commute with their canonical quotient maps:

The surjections $\homst \setX \Surj \setY$ and injections $\homst \setX \Inj \setY$ form submodules of $\SetXY$,
with analogous diagrams concerning their quotients.

---

2. The “twelvefold way”

The double quotient square for $\SetXY$

$\begin{array}{} \text{\{ ordered weak $\target \setY$-partitions of $\source \setX$ \}} && \text{\{ unordered weak $\target{|\setY|}$-partitions of $\source \setX$ \}} \\ {\wr\Vert} && \wr\Vert \\ \SetXY & {} \rlap{\mkern-7em\xrightarrow[\mkern16em]{\displaystyle \functiont}} & \mkern1.6em \SetXY \target/ \symtY \\ \smash{\source{\llap\functions \Bigg\downarrow}} & \searrow \rlap\functionr & \Bigg\downarrow \\ \symsX \source\backslash \SetXY \mkern2em & {} \rlap{\mkern-7em\xrightarrow{\mkern16em}} & \symsX \source\backslash \SetXY \target/ \symtY \\ \wr\Vert && \wr\Vert \\ \text{\{ ordered weak $\target{\setY}$-partitions of $\source{|\setX|}$ \}} && \text{\{ unordered weak $\target{|\setY|}$-partitions of $\source{|\setX|}$ \}} \\ \wr\Vert \\ \text{\{ weak $\source{|\setX|}$-multisets (values $\ge0$) on $\target \setY$ \}} \\ \end{array}$

The double quotient square for $\homst \setX \Surj \setY$

$\begin{array}{} \text{\{ ordered strong $\target{\setY}$-partitions of $\source \setX$ \}} && \text{\{ unordered strong $\target{|\setY|}$-partitions of $\source \setX$ \}} \\ \wr\Vert && \wr\Vert \\ \homst \setX \Surj \setY & {} \rlap{\mkern-7em\xrightarrow[\mkern16em]{\displaystyle \functiont}} & \mkern1.6em \homst \setX \Surj \setY \target/ \symtY \\ \smash{\source{\llap\functions \Bigg\downarrow}} & \searrow \rlap\functionr & \Bigg\downarrow \\ \symsX \source\backslash \homst \setX \Surj \setY \mkern1.6em & {} \rlap{\mkern-7em\xrightarrow{\mkern16em}} & \symsX \source\backslash \homst \setX \Surj \setY \target/ \symtY \\ \wr\Vert && \wr\Vert \\ \text{\{ ordered strong $\target{\setY}$-partitions of $\source{|\setX|}$ \}} && \text{\{ unordered strong $\target{|\setY|}$-partitions of $\source{|\setX|}$ \}} \\ \wr\Vert \\ \text{\{ strong $\source{|\setX|}$-multisets (values $\ge1$) on $\target \setY$ \}} \\ \end{array}$

The double quotient square for $\homst \setX \Inj \setY$

$\begin{array}{} \text{ \{ injections from $\source \setX$ to $\target \setY$ \}} && \text{$1$ or $\emptyset$ as $\source{|\setX|} \le {}$ or $\gt \target{|\setY|}$} \\ \Vert && \wr\Vert \\ \homst \setX \Inj \setY & {} \rlap{\mkern-10em\xrightarrow[\mkern16em]{\displaystyle \functiont}} & \mkern1.4em \homst \setX \Inj \setY / {\target{S_\setY}} \\ \smash{\source{\llap\functions \Bigg\downarrow}} & {} \rlap{\mkern-4em \searrow\rlap\functionr} & \Bigg\downarrow \\ {\source{S_\setX}} \backslash \homst \setX \Inj \setY \mkern1.6em & {} \rlap{\mkern-10em\xrightarrow{\mkern16em}} & {\source{S_\setX}} \backslash \homst \setX \Inj \setY / {\target{S_\setY}} \\ \wr\Vert && \wr\Vert \\ \text{\{ $\source{|\setX|}$-subsets ($\source{|\setX|}$-multisets with values $0$ or $1$) of $\target \setY$ \}} && \text{$1$ or $\emptyset$ as $\source{|\setX|} \le {}$ or $\gt \target{|\setY|}$ } \\ \end{array}$

Putting this all together, we have the three diagrams at the right for

• $\SetXY$ = all functions from $\source \setX$ to $\target \setY$,
• $\homst \setX \Surj \setY$ = surjections from $\source \setX$ to $\target \setY$, and
• $\homst \setX \Inj \setY$ = injections from $\source \setX$ to $\target \setY$,

showing the source, target, and double quotients
in each of the bimodules of functions, surjections, and injections.
These diagrams underlie
the “twelvefold way” of combinatorics.

Remark:
It is common (e.g., Stanley, EC, §1.9) in combinatorics to call
(the elements of the source set $\setX$) balls, and
(the elements of the target set $\setY$) boxes or urns.
Then (a function $\source\setX \to \target\setY$) is
(an assignment of balls to boxes, ball $\mapsto$ box),
and can be visualized physically,
as actually placing (physical balls) in (physical boxes or urns).

(The kernel-partition (or fibre) form)
used below to describe functions
amounts to showing, for each “box” its contents,
i.e., which “balls” are placed in it;
thus the $\{\elta,\eltb\}$-ordered partition $0,2,3 \mid 1$ means
balls $0,2,3$ go into box $\elta$,
while ball $1$ goes into box $\eltb$;
the word form for this function is $\elta\eltb\elta\elta$.
For pictorial examples, again see EC, §1.9.

---

The twelvefold way

$\bbox[navajowhite,10px,border:4px groove red]{ \begin{array}{} && & {} \mkern5em \rlap{\text{Injections}} &&&& {} \mkern7em \rlap{\text{All functions}} &&&& {} \mkern8em \rlap{\text{Surjections}} \\ && & \settY & & \target{|\setY|} & \mkern4em & \settY & & \target{|\setY|} & \mkern4em & \settY & & \target{|\setY|} \\ \setsX,\settY && & \boxed{\begin{array}{} \cattwo, \setsX, \settY\\ \homst \setX \Inj \setY\\ {\target{|\setY|}}^{\source{\underline{|\setX|}}} \\ \end{array} } && && \boxed{\begin{array}{} \text{weak}, \setsX, \settY\\ \SetXY\\ {\target{|\setY|}}^{\source{|\setX|}} = \displaystyle\target{\sum_{i=0}^{|\setY|}} \source{{|\setX| \brace \target i}}\target{i!}\target{{|\setY| \choose i}}\\ \end{array} } && && \boxed{\begin{array}{} \text{strong}, \setsX, \settY\\ \homst \setX \Surj \setY\\ \displaystyle{\source{|\setX|} \brace \target{|\setY|}}\target{|\setY|!}\\ \end{array} } \\ & \setsX & & & \target\searrow &&& & \target\searrow && {} \rlap{\mkern3em \source{\boxed{\boxed{\text{U = $\setsX$}}}}} & & \target\searrow \\ && \setsX,\target{|\setY|} & \raise2ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \llap{\lower6ex\hbox{$\boxed{\boxed{\text{L} = \cattwo}}\mkern.1em$}} \boxed{\begin{array}{} \cattwo, \setsX, \target{|\setY|} \\ \homst \setX \Inj \setY \target/ \symtY\\ [\source{|\setX|}\leq\target{|\setY|}] \\ \end{array} } && \raise2ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \llap{\lower6ex\hbox{$\boxed{\boxed{\text{C = weak}}} \mkern.2em$}} \boxed{\begin{array}{} \text{weak}, \setsX, \target{|\setY|} \\ \SetXY \target/ \symtY\\ \displaystyle\target{\sum_{i=0}^{|\setY|}} {\source{|\setX|} \brace \target i}\\ \end{array} } \rlap{\mkern.5em \target{\boxed{\boxed{\text{B = $\settY$}}}} } && \raise2ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \llap{\lower6ex\hbox{$\boxed{\boxed{\text{R = strong}}} \mkern.2em$}} \boxed{\begin{array}{} \text{strong}, \setsX, \target{|\setY|} \\ \homst \setX \Surj \setY \target/ \symtY\\ \displaystyle {\source{|\setX|} \brace \target{|\setY|}} \end{array} } \\ \source{|\setX|},\settY && & \boxed{\begin{array}{} \cattwo, \source{|\setX|}, \settY\\ \symsX \source\backslash \homst \setX \Inj \setY\\ \displaystyle {\target{|\setY|} \choose \source{|\setX|}}\\ \end{array} } && \lower3ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \boxed{\begin{array}{} \text{weak}, \source{|\setX|}, \settY\\ \symsX \source\backslash \SetXY\\ \displaystyle \bigg(\mkern-.35em {\target{{|\setY|}} \choose \source{|\setX|}} \mkern-.35em\bigg) = {\source{|\setX|}+\target{|\setY|}-1 \choose \target{|\setY|-1}} \end{array} } && \lower3ex\hbox{$\smash{\source{\Bigg\downarrow}}$} && \llap{\target{\boxed{\boxed{\text{F = } \target{|\setY|}}}} \; } \boxed{\begin{array}{} \text{strong}, \source{|\setX|}, \settY\\ \symsX \source\backslash \homst \setX \Surj \setY\\ \displaystyle \bigg(\mkern-.35em {\target{{|\setY|}} \choose \source{|\setX|} - \target{|\setY|}} \mkern-.35em\bigg) = \displaystyle {\source{|\setX|-1} \choose \target{|\setY|-1}} \end{array} } && \lower3ex\hbox{$\smash{\source{\Bigg\downarrow}}$} \\ & |\setsX| & & & \target\searrow &&& & \target\searrow && {} \rlap{\mkern3em \source{\boxed{\boxed{\text{D = } \source{|\setX|}}}}} & & \target\searrow \\ && \source{|\setX|},\target{|\setY|} & && \boxed{\begin{array}{} \cattwo, \source{|\setX|}, \target{|\setY|} \\ \symsX \source\backslash \homst \setX \Inj \setY \target/ \symtY\\ [\source{|\setX|}\leq\target{|\setY|}]\\ \end{array} } &&& & \boxed{\begin{array}{} \text{weak}, \source{|\setX|}, \target{|\setY|} \\ \symsX \source\backslash \SetXY \target/ \symtY\\ \displaystyle\target{\sum_{i=0}^{|\setY|}} \functionp_{\target i} (\source{|\setX|})\\ \end{array} } &&& & \boxed{\begin{array}{} \text{strong}, \source{|\setX|}, \target{|\setY|} \\ \symsX \source\backslash \homst \setX \Surj \setY \target/ \symtY\\ \functionp_{\target{|\setY|}} (\source{|\setX|})\\ \end{array} } & \\ \end{array} }$

The numerical formulae above are valid when $\setX$ and $\setY$ are finite nonempty sets, so that $\target{|\settY|-1\geq 0}$.
For slight variants which are valid even when $\target{|\settY|} = 0$ (i.e., when $\settY = \emptyset$), see the Wikipedia article.

The $\langle \source{|\setX|}, \settY \rangle$-cases: $\settY$-ordered partitions of the finite positive integer $\source{\numbern=|\setX|}$

Assume $\settY$ is linearly ordered with $\target{|\setY|=\numberk}$, a finite positive integer.

Strong $\numberk$-ordered partitions of $\numbern$, $1\leq\numberk\leq\numbern$.
Write ($\source\numbern$ dots in a row).
There are ($\source{\numbern-1}$ spaces) between (the $\source\numbern$ dots).
Choose $\target{\numberk-1}$ of (those $\source{\numbern-1}$ spaces), and place (a divider “$|$” (a “bar”)) in each of (the chosen $\target{\numberk-1}$ spaces).
The result is that (the $\source\numbern$ dots) are divided into ($\target\numberk$ non-empty groups).
There are ${\source{\numbern-1} \choose \target{\numberk-1}} = {\source{|\setX|-1} \choose \target{|\setY|-1}}$ ways of making (the choices described above).
For each ($\numberk$-ordered strong partition of $\numbern$) there is (a unique such choice) which (delivers the partition).
And note that any choice from the $\source{\numbern-1}$ inter-dot spaces yields a strong partition, thus there are $2^{\source{\numbern-1}}$ strong partitions in all.

Weak $\numberk$-ordered partitions of $\numbern$, arbitrary finite positive $\numberk$.
In this case, write ($\source\numbern+\target\numberk-1$ dots in a row).
Choose $\target{\numberk-1}$ of those dots, and replace (those chosen $\target{\numberk-1}$ dots) with (the divider symbol “$|$” (the “bar”)).
The result is again a division of (the $\source\numbern$ dots) into ($\target\numberk$ groups), but now (some of those groups may be empty).
There are ${\source\numbern+\target{\numberk-1} \choose \target{\numberk-1}} = {\source{|\setX|}+\target{|\setY|}-1 \choose \target{|\setY|-1}}$ ways of making (the choices described), yielding all possible (weak $\target\numberk$-ordered partitions of $\source\numbern$).

---

3. An example: $\homst {[4]} \Set {\{a,b\}}$

The double quotient square for $\homst {(\setX=[4])} \Set {(\setY=\{a,b\})}$

$\begin{array}{} \text{\{ ordered weak $\target{\{\elta,\eltb\}}$-partitions of $\source {[4]}$ \}} && \text{\{ unordered weak $\target 2$-partitions of $\source {[4]}$ \}} \\ \llap{(\#=16)\;} {\wr\Vert} && \wr\Vert \rlap{\;(\#=8)} \\ \mkern.5em \homst {[4]} \Set {\{a,b\}} & {} \rlap{\mkern-6em\xrightarrow{\mkern14em}} & \mkern3em \homst {[4]} \Set {\{a,b\}} / \target{S_{\{a,b\}}} \\ \Bigg\downarrow && \Bigg\downarrow \\ \mkern.5em {\source{S_{[4]}}} \backslash \homst {[4]} \Set {\{a,b\}} \mkern2em & {} \rlap{\mkern-6em\xrightarrow{\mkern14em}} & \mkern1.5em {\source {S_{[4]}}} \source\backslash \homst {[4]} \Set {\{a,b\}} \target/ {\target{S_{\{a,b\}}}} \\ \llap{(\#=5)\;} {\wr\Vert} && \wr\Vert \rlap{\;(\#=3)} \\ \text{\{ ordered weak $\target{\{\elta,\eltb\}}$-partitions of $\source 4$ \}} && \text{\{ unordered weak $\target 2$-partitions of $\source 4$ \}} \\ \Vert && \Vert \\ \source{\{4+0, 3+1, 2+2, 1+3, 0+4 \}} && \source{\{4+0, 3+1, 2+2\}} \\ \wr\Vert \\ \text{\{ weak $\source 4$-multisets on $\target {\{a,b\}}$ \}} \\ \Vert \\ \{\target a^4 \target b^0, \target a^3 \target b^1, \target a^2 \target b^2, \target a^1 \target b^3, \target a^0 \target b^4\} \\ \end{array}$

There is a certain abstractness about
talking about arbitrary sets $\source \setX$ and $\target \setY$.
Let's see what all this means in a case where we can easily
both represent and count
{ the elements of the function sets $\SetXY$ and $\homst \setX \Surj \setY$ }.
In particular,
we take ($\source{\setX = [4] \equiv \{0,1,2,3\}}$) and ($\target{\setY = \{a,b\}}$),
so functions $\functionf : \source{[4]} \to \target{\{\elta,\eltb\}}$
can be represented as
four-letter words in the alphabet $\target{\{\elta,\eltb\}}$, e.g. $\target{\elta\eltb\elta\elta}$;
then $|\SetXY| = \target{|\setY|}^{\source{|\setX|}} = {\target 2}^{\source 4} = 16$
and $|\homst \setX \Surj \setY| = 14$ (all but the two constant functions).
Then (the double quotient square for $\homst {(\setX=[4])} \Set {(\setY=\{a,b\})}$)
becomes the diagram at right.
The contents of the various sets in the diagram
are described in detail below.

The source quotient: ${\source{S_{[4]}}} \backslash \homst {[4]} \Set {\{a,b\}} \cong \catI \tensor_{\source{S_{[4]}}} \homst {[4]} \Set {\{a,b\}}$

$\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{lcccccccc} &&& \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} } \\ && \displaystyle { \source{0,1,2 \mid 3} \brack \target{aaab} } & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & \displaystyle { \source{0 \mid 1,2,3} \brack \target{abbb} }\\ && \displaystyle { \source{0,1,3 \mid 2} \brack \target{aaba} } & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & \displaystyle { \source{1 \mid 0,2,3} \brack \target{babb} }\\ & \displaystyle { \source{0,1,2,3 \mid {}} \brack \target{aaaa} } && \class{red}\bullet && \displaystyle { \source{{} \mid 0,1,2,3} \brack \target{bbbb} }\\ && \displaystyle { \source{0,2,3 \mid 1} \brack \target{abaa} } & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & \displaystyle { \source{2 \mid 0,1,3} \brack \target{bbab} }\\ && \displaystyle { \source{1,2,3 \mid 0} \brack \target{baaa} } & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & \displaystyle { \source{3 \mid 0,1,2} \brack \target{bbba} }\\ &&& \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\[2ex] \hline \source{\text{size of $S_{[4]}$-orbit}} & \source 1 & \source 4 & \source 6 & \source 4 & \source 1\\ \source{\text{size of $S_{[4]}$-stabilizer}} & \source{4!0!} & \source{3!1!} & \source{2!2!} & \source{1!3!} & \source{0!4!}\\ \source{\text{template (set form)}} & \source{\{\cdotp\cdotp\cdotp\cdotp\} \{\}} & \source{\{\cdotp\cdotp\cdotp\} \{\cdotp\}} & \source{\{\cdotp\cdotp\} \{\cdotp\cdotp\}} & \source{\{\cdotp\} \{\cdotp\cdotp\cdotp\}} & \source{\{\} \{\cdotp\cdotp\cdotp\cdotp\}} \\ \source{\text{template (divider form)}} & \source{\cdotp\cdotp\cdotp\cdotp \mid {}} & \source{\cdotp\cdotp\cdotp \mid \cdotp} & \source{\cdotp\cdotp \mid \cdotp\cdotp} & \source{\cdotp \mid \cdotp\cdotp\cdotp} & \source{{} \mid \cdotp\cdotp\cdotp\cdotp} \\ \text{partition (binary form)} & \source{0000}\target1 & \source{000}\target1\source0 & \source{00}\target1\source{00} & \source0\target1\source{000} & \target1\source{0000}\\ \text{ordered weak $\target2$-partitions of }\source4 & \source4 \target+ \source0 & \source3 \target+ \source1 & \source2 \target+ \source2 & \source1 \target+ \source3 & \source0 \target+ \source4\\ \text{weak $\source 4$-multisets on }\target{\{a,b\}} & \target a^{\source 4}\source b^{\target 0} & \target a^{\source 3}\target b^{\source 1} & \target a^{\source 2}\target b^{\source 2} & \target a^{\source 1}\target b^{\source 3} & \target a^{\source 0}\target b^{\source 4}\\[2ex] \target{\text{size of BLOCK $S_{\{a,b\}}$-stabilizer}} & \target 1 & \target 1 & \target 2 & \target 1 & \target 1 \\ \target{\text{size of BLOCK $S_{\{a,b\}}$-orbit}} & \target 2 & \target 2 & \target 1 & \target 2 & \target 2 \\ \end{array}}$

Dividing out by
(permutations of the source $\setX = \source{[4]}$),
$\SetXY \longrightarrow {\source{S_\setX\backslash{}}} \SetXY$,
i.e., indistinguishable source elements or balls,
can be visualized via the figure at right,
which shows all ${\target 2}^{\source 4}=16$ functions
from $\source{[4]=\{0,1,2,3\}}$ to $\target{\{a,b\}}$,
i.e., the elements of $\homst {[4]} \Set {\{a,b\}} = {\target{\{a,b\}}}^{\source{[4]}}$.
It shows each function
first in ordered kernel-partition (or fibre) form
($\target a$ component of the partition (or fibre)
to the left of the divider “$\mid$” (the “bar”),
$\target b$ component on the right),
then on the next line
the representation of the function
as a four letter word in the alphabet $\{a,b\}$.
(The columns) are precisely
{the orbits of $\homst {[4]} \Set {\{a,b\}}$ under
the left (pre-) $\source{S_{[4]}}$-action},
thus are precisely
{the elements of
the left quotient set $\source{S_{[4]} \backslash} \homst {[4]}\Set {\{a,b\}}$}.
Thus the $\symsX$-quotient map
($\SetXY \longrightarrow {\source{S_\setX\backslash{}}} \SetXY$)
takes (each function) into
(its column in the table).
(The bottom rows of the table) show
some information about each column/$\symsX$-orbit,
namely, its size and
the size of the stabilizers of its elements,
and some alternative ways of describing
the column/$\symsX$-orbit, i.e.,
some total invariants of the column/$\symsX$-orbit:
(the ordered weak $\target{\{\elta,\eltb\}}$-partitions of $\source 4$) and (the weak $\source 4$-multisets on $\target{\{a,b\}}$).

For surjections, simply omit the two outer columns.

Now consider (the action of $\symtY = \target{S_{\{a,b\}}}$) on both (the total space $\homst {[4]} \Set {\{a,b\}}$) and (its source quotient ${\source{S_{[4]}\backslash{}}} \homst {[4]} \Set {\{a,b\}}$).
(The columns of the table) have been so ordered that (the $\source{S_{\{a,b\}}}$-action) on (the total space $\homst {[4]} \Set {\{a,b\}}$)
amounts to reflection in (the dot $\class{red}\bullet$ which is at the center of the table).
The key point is that (reflection in the center dot $\class{red}\bullet$) (respects the columns), i.e., it takes (functions\words in the same column) into (functions\words in the same column).
Thus (the central reflection on the 16 points) passes to (a reflection on the five columns), namely, (reflection in (the vertical axis through the center of the table)).
That reflection (swaps the four outer columns), but (fixes the center column).
Thus (the resulting iterated quotient $\source{( S_{[4]} \backslash } \homst {[4]} \Set {\{a,b\}} \source) / \target{S_{\{a,b\}}}$) has three elements ($\symtY$-orbits of $\symsX$-orbits):
{ the pair of outer columns, the pair of next-to-outer columns, and the center column }.

---

The target quotient:
$\target( \homst {[4]} \Set {\{a,b\}} \target{/ S_{\{a,b\}} )} \cong \homst {[4]} \Set {\{a,b\}} \tensor_{\target{S_{\{a,b\}}}} \catI$

$$\begin{array}{cc} \displaystyle { \source{0,1,2,3 \mid {} } \brack \target{aaaa} } \displaystyle { \source{ {} \mid 0,1,2,3} \brack \target{bbbb} } \end{array}$$		$\{\,4+0,0+4\,\}$	$\{\,4,0\,\}$
$$\begin{array}{cc} \displaystyle { \source{0,1,2 \mid 3} \brack \target{aaab} } & \displaystyle { \source{3 \mid 0,1,2} \brack \target{bbba} }\\ \displaystyle { \source{0,1,3 \mid 2} \brack \target{aaba} } & \displaystyle { \source{2 \mid 0,1,3} \brack \target{bbab} }\\ \displaystyle { \source{0,2,3 \mid 1} \brack \target{abaa} } & \displaystyle { \source{1 \mid 0,2,3} \brack \target{babb} }\\ \displaystyle { \source{1,2,3 \mid 0} \brack \target{baaa} } & \displaystyle { \source{0 \mid 1,2,3} \brack \target{abbb} }\\ \end{array}$$		$\{\,3+1,1+3\,\}$	$\{\,3,1\,\}$
$$\begin{array}{cc} \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} } & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \end{array}$$		$\{\,2+2\,\}$	$\{\,2,2\,\}$

For dividing out by (permutations of the target $\target{\setY = \{a,b\}}$),
$\SetXY \mathrel{\target\longrightarrow} \SetXY {\target{{}/S_\setY}}$, i.e., indistinguishable target elements or boxes,
we have a similar figure, at right.
Here (the $\target{S_\setY}$-orbits) are arranged in rows;
thus ((the $\target{S_{\setY}}$-quotient map) onto (the $\target{S_{\setY}}$-orbits)) is now simply (taking the row).

(The source permutation group $\source{S_\setX = S_{[4]}}$) acts, not only on (the elements of $\SetXY$),
but also on (their $\symtY$-orbits): $\symsX \times \target{\big(} \SetXY \target{{} / \symtY \big)} \mathrel{\source\longrightarrow} \target{\big(} \SetXY \target{{} / \symtY \big)}$.
{The orbits of $\SetXY \target/ \symtY$ under that ($\source{\symsX = S_{[4]}}$)-action}
are {the three blocks of rows separated by horizontal rules} —
these are the three elements of the set of $\symsX$-orbits of $\symtY$-orbits, $\source{S_\setX \backslash} \target{\big(} \SetXY \target{{} / S_\setY \big)}$.
They correspond to the three unordered weak $\target 2$-partitions of $\source 4$: $\source{4+0, 3+1, 2+2}$.

The key point again is that
there are bijections between (the iterated quotients) and (the double quotient)
i.e., between {blocks of columns}, {blocks of rows}, and (the orbits of the two-sided action),
rendering commutative the five-quotient diagram $$\begin{array}{} \smash{\SetXY} & {} \rlap{ \mkern-.5em \smash{\target{\xrightarrow[\mkern18em]{\displaystyle \functiont}} } } &&& \mkern1em \SetXY \target{ / S_\setY} \\ &&&& \source{\big\downarrow} \\ \smash{\source{\llap{\functions} \Bigg\downarrow}} && \searrow \rlap{\raise1ex\functionr} && \smash{ \source{S_\setX \backslash } \target( \SetXY \target{/ S_\setY )} } \\ &&&& \wr\Vert \\ \source{S_\setX \backslash} \SetXY & {} \rlap{\mkern-.5em\target\longrightarrow} & \mkern1em \source{( S_\setX \backslash } \SetXY \source) \target{/ S_\setY} & \cong & \source{S_\setX \backslash} \SetXY \target{/ S_\setY} & , \\ \end{array}$$ namely the evident bijections between (the three-element sets) listed on (three rows below).
Note how (the double quotient), in the middle row, flattens (the iterated quotients),
replacing (orbits of orbits) with just (orbits).

$\mkern-3em \begin{array}{cccccccccl} {} \rlap{\mkern19em \text{The quotients as sets of sets (of sets), and some invariants of those sets}} \\ && \Big\{ & \source{\big\{0123\mid{}\big\}}& , & \source{\big\{\mkern.5em 012\mid3 \mkern1em,\mkern1em 013\mid2 \mkern1em,\mkern1em 023\mid1 \mkern1em,\mkern1em 123\mid0\mkern.5em\big\}} & , & \source{\big\{\mkern1em 01\mid23 \mkern1em,\mkern1em 02\mid13 \mkern1em,\mkern1em 03\mid12 \mkern1em\big\}} & \Big\} & \text{unordered parts. of $[4]$} \\ \source{S_\setX \backslash } \target( \SetXY \target{/ S_\setY )}& = & \Big\{ & \big\{ \{\elta^4,\eltb^4\} \big\} & , & \big\{ \{\elta^3\eltb,\eltb^3\elta\}, \{\elta^2\eltb\elta,\eltb^2\elta\eltb\}, \{\elta\eltb\elta^2,\eltb\elta\eltb^2\}, \{\eltb\elta^3,\elta\eltb^3\} \big\} & , & \big\{ \{\elta^2\eltb^2,\eltb^2\elta^2\}, \{\elta\eltb\elta\eltb,\eltb\elta\eltb\elta\}, \{\elta\eltb^2\elta, \eltb\elta^2\eltb\} \big\} & \Big\} & \text{$\symsX$-orbits of $\symtY$-orbits} \\ \source{S_\setX \backslash} \SetXY \target{/ S_\setY} & = & \Big\{ & \big\{ \elta^4,\eltb^4 \big\} & , & \big\{ \elta^3\eltb, \elta^2\eltb\elta, \elta\eltb\elta^2, \eltb\elta^3, \elta\eltb^3, \eltb\elta\eltb^2, \eltb^2\elta\eltb, \eltb^3\elta \big\} & , & \big\{ \elta^2\eltb^2, \elta\eltb\elta\eltb, \elta\eltb^2\elta, \eltb\elta^2\eltb, \eltb\elta\eltb\elta, \eltb^2\elta^2 \big\} & \Big\} & \text{$\source{\symsX\op} \rightadj\times \symtY$-orbits} \\ \source{( S_\setX \backslash } \SetXY \source) \target{/ S_\setY} & = & \Big\{ & \big\{ \{\elta^4\},\{\eltb^4\} \big\} & , & \big\{ \{\elta^3\eltb, \elta^2\eltb\elta, \elta\eltb\elta^2, \eltb\elta^3\}, \{\elta\eltb^3, \eltb\elta\eltb^2, \eltb^2\elta\eltb, \eltb^3\elta\} \big\} & , & \big\{ \{\elta^2\eltb^2, \elta\eltb\elta\eltb, \elta\eltb^2\elta, \eltb\elta^2\eltb, \eltb\elta\eltb\elta, \eltb^2\elta^2\} \big\} & \Big\} & \text{$\symtY$-orbits of $\symsX$-orbits} \\ && \Big\{ & \source{\big\{4+0,0+4\big\}} & , & \source{\big\{\mkern3em 3+1 \mkern3em , \mkern3em 1+3 \mkern3em\big\}} & , & \source{\big\{\mkern4em 2+2 \mkern4em\big\}} & \Big\} & \text{ordered parts. of $4$} \\ && \Big\{ & \source{4+0} & , & \source{3+1} & , & \source{2+2} & \Big\} & \text{unordered parts. of $4$} \\ \end{array}$

For further information, see the post “The fiber product at work (in elementary combinatorics)”.

---

References

EC, Stanley, Richard P., Enumerative Combinatorics I, 1986/2011
W, Wikipedia, “Twelvefold way”
FPAW, “The fiber product at work (in elementary combinatorics)”, 2019
DG12W, “Double groupoids and the twelvefold way”, 2016
PF, “The parts of a function”, 2016
CFP, “Classifying functions by their parts”, 2016
QKA, “The quotient-kernel adjunction”, 2016
KQFC, “Kernels, quotients, and function composition”, 2019