- Introduction to the bimodule of sets, functions, and permutations
- Quotients: the “twelvefold way”; the twelvefold way diagram
- An example: $\homst {[4]} \Set {\{a,b\}}$
- Division (quotient) as (tensor product) with (the terminal bimodule)
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$ |
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).
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}{*}$).
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 )} }$ .
| $\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}$ |
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”
| $ \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} $ |
| $ \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} $ |
| $ \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$,
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.
| $\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\}}$
| $ \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.
| $\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 }.
| $$\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).
For further information, see the post “The fiber product at work (in elementary combinatorics)”.
References
EC, Stanley, Richard P., Enumerative Combinatorics I, 1986/2011W, 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
No comments:
Post a Comment