Fact: The $2^4 = 16$ functions from $\source{[4]=\{0,1,2,3\}}$ to $\target{\{a,b\}}$,
- when quotiented by the permutation group of the source, $S_4$,
divide into five equivalence classes; - when quotiented by the permutation group of the target, $S_{\{a,b\}}$,
divide into eight equivalence classes; - when quotiented by both,
divide into three equivalence classes.
Challenge: Find a way to visualize those classes and the relations between them.
Solution: Apply the following construction of a double groupoid to $\homst {[4]} \Set {\{a,b\}}$. (The result.)
The general construction
Let $\source X$ and $\target Y$ be arbitrary sets in the category of sets, $\Set$.
Let $\boxed{\source{S_X}}$ and $\boxed{\target{S_Y}}$ be their respective groups of permutations.
Form a double groupoid as follows.
- Its 0-cells are all the functions from $\source X$ to $\target Y$,
namely, the elements of the function set $\boxed{\homst X \Set Y}$. - There is a vertical 1-cell for each $\boxed{\langle \source\sigma, f \rangle \in \symsX \times \homst X \Set Y = V}$.
- There is a horizontal 1-cell for each $\boxed{\langle f, \target\tau \rangle \in \homst X \Set Y \times \symtY = H}$.
-
$\begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau}} & f\target\tau\\ \source{\llap{\text{s-}\sigma} \Big\downarrow} & \langle \source\sigma, f, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}}\\ \source\sigma f & \target{\xrightarrow[\displaystyle \text{t-}\tau]{}} & \source\sigma f \target\tau \end{array}$The sources and targets of the 1-cells are as shown in the square for 2-cells.
- There is a 2-cell for each triple $\boxed{\langle \source\sigma, f, \target\tau \rangle \in \source{S_X} \times \homst X \Set Y \times \target{S_Y}}$,
having (horizontal and vertical source and target) as in (the square at right): - Vertical and horizontal composition of 1-cells is obvious,
while vertical and horizontal composition of 2-cells is by pasting. - Vertical and horizontal associativity and identity are obvious.
-
$\begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau}} & f\target\tau & \target{\xrightarrow{\displaystyle \text{t-}\tau'}} & f\target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma} \Big\downarrow} & \langle \source\sigma, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}} & \langle \source\sigma, \target{\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma}}\\ \source\sigma f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau}}} & \source\sigma f \target\tau & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau'}}} & \source\sigma f \target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma'} \Big\downarrow} & \langle \source{\sigma'}, \target\tau \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma'}} & \langle \source{\sigma'}, \target{\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma'}}\\ \source{\sigma'\sigma} f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau}}} & \source{\sigma'\sigma} f \target\tau & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau'}}} & \source{\sigma'\sigma} f \target{\tau\tau'}\\ \end{array} = \qquad \begin{array}{c} f & \target{\xrightarrow{\displaystyle \text{t-}\tau\tau'}} & f\target{\tau\tau'}\\ \source{\llap{\text{s-}\sigma\sigma'} \Big\downarrow} & \langle \source{\sigma\sigma'}, \target{\tau\tau'} \rangle & \source{\Big\downarrow \rlap{\text{s-}\sigma\sigma'}}\\ \source{\sigma'\sigma} f & \target{\xrightarrow{\smash{\displaystyle \text{t-}\tau\tau'}}} & \source{\sigma'\sigma} f \target{\tau\tau'}\\ \end{array}$Finally,
the compatibility of horizontal with vertical composition
is shown by the square at right, of four compatible squares.
Whether
you first horizontally compose the top and bottom halves,
then vertically compose the result,
or first vertically compose the right and left halves,
then horizontally compose the result,
you get the same resulting square as shown.
There are then four groupoids:
- A discrete one, consisting only of the 0-cells (one for each function).
- The source groupoid, consisting of the 0-cells and the $\text{s}$-labeled 1-cells,
specifying how permutations of the source act on functions. - The target groupoid, consisting of the 0-cells and the $\text{t}$-labeled 1-cells,
specifying how permutations of the target act on functions. - The source-target double groupoid, consisting of all the 0-cells, 1-cells, and 2-cells.
The 2-cells specify how simultaneous permutations of the source and target
act on functions.
the source and target groupoids are subgroupoids of the source-target double groupoid.
are the four parts of the “twelvefold way” for arbitrary functions.
The other eight parts of the “twelvefold way”
are the connected components of
the groupoids defined for surjective and injective functions.
The permutation groups act on surjective and injective functions
just as they act on arbitrary functions,
and we can repeat the above construction on those classes of functions.
The specific case of $\homst {[4]} \Set {\{a,b\}}$
Apply the above construction to $\homst {[4]} \Set {\{a,b\}}$.
(The connected components of the double groupoid) are in (the three cells of the figure below).
The component labeled $\{4,0\}$ contains two functions,
the component labeled $\{3,1\}$ contains eight functions,
the component labeled $\{2,2\}$ contains six functions
(each appearing twice in the graphic, connected by $=$ signs,
due to the fact that, for (this component of (the source-target groupoid)),
(target-permutations) remain in (the same connected component of (the source groupoid))).
Note that in (this source-target component) prefixes have been added to the permutations,
so that (in the event that there is overlap between the elements of the source and target)
it can be determined unambiguously whether (a given permutation) is (of the source or target).
[The connected components of the groupoid using (permutations of the source)] are (the columns).
There are five such components (columns), with column headers
$$\langle 4, 0 \rangle, \quad \langle 0, 4 \rangle, \quad \langle 3, 1 \rangle, \quad \langle 1, 3 \rangle,\quad \hbox{and}\quad \langle 2, 2 \rangle .$$
The connected components of the groupoid using (permutations of the target) are connected by (arrows labeled $\target(a,b)$):
five horizontal arrows in the first two cells and
three of the vertical arrows in the third cell,
thus (eight components) of (the target groupoid).
(Because (target permutations) stabilize (this connected component of (the source groupoid)).)
| $\{4,0\}$ | $\{3,1\}$ | $\{2,2\}$ |
|---|---|---|
| \[\begin{array}{c} \source{\langle 4, 0 \rangle} & \target{\xrightarrow{\text{t-}(a,b)}} & \source{\langle 0, 4 \rangle} \\[8ex] \hline \boxed{\displaystyle { \source{0,1,2,3 \mid {}} \brack \target{aaaa} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{{} \mid 0,1,2,3} \brack \target{bbbb} }\\ \end{array}\] | \[\begin{array}{c} \source{\langle 3, 1 \rangle} & \target{\xrightarrow{\text{t-}(a,b)}} & \source{\langle 1, 3 \rangle} \\[8ex] \hline \boxed{\displaystyle { \source{0,1,2 \mid 3} \brack \target{aaab} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{3 \mid 0,1,2} \brack \target{bbba} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,1,3 \mid 2} \brack \target{aaba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{2 \mid 0,1,3} \brack \target{bbab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,2,3 \mid 1} \brack \target{abaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1 \mid 0,2,3} \brack \target{babb} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{1,2,3 \mid 0} \brack \target{baaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0 \mid 1,2,3} \brack \target{abbb} }\\ \end{array}\] | \[\begin{array}{c} & \source{\langle 2, 2 \rangle} &\\[8ex] \hline \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & = & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)}\Big\uparrow} && \target{\Big\uparrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & = & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ \source{\llap{\scriptstyle \text{s-}(1,2)}\Big\uparrow}\\ \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & = & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)^2}\Big\downarrow\rlap{\scriptstyle \text{s-}(0,2)(1,3)}} && \target{\Big\downarrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & = & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & = & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \source{\llap{\scriptstyle \text{s-}(0,1,2,3)^2}\Big\downarrow\rlap{\scriptstyle \text{s-}(0,2)(1,3)}} && \target{\Big\downarrow\rlap{\scriptstyle \text{t-}(a,b)}}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & = & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} }\\ \end{array}\] |
Answering the challenge posed at the beginning, we see that
{the $\target2^{\source4}=16$ functions from $\source{[4]}$ to $\target{\{a,b\}}$} decompose unambiguously into
(the three connected components) of (the source-target groupoid) associated with (the unordered weak $\target 2$-partitions of $\source 4$)
$$\{4,0\}, \{3,1\}, \{2,2\} .$$
Each of these three components may be decomposed either into
components of (the source groupoid) or (the target groupoid).
For example,
the eight elements of the $\{3,1\}$ component of the source-target groupoid
can be divided either into
- two ((four-element components) of (the source groupoid)) associated with the two $\{3,1\}$-multisets $a^3b^1$ and $a^1b^3$, or
- four ((two-element components) of (the target groupoid)) associated with the four $\{3,1\}$-partitions of $\{0,1,2,3\}$ $$0,1,2\mid 3,\quad 0,1,3\mid 2,\quad 0,2,3\mid 1, \quad 1,2,3\mid 0 .$$
| $\{2,2\}$ | $\{2,2\}$ |
|---|---|
| \[\begin{array}{c} & \source{\langle 2, 2 \rangle} & \\[8ex] \hline \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\uparrow} && \source{\Big\uparrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ \source{\llap{\scriptstyle\text{s-}(1,2)}\Big\uparrow} && \source{\Big\uparrow\rlap{\scriptstyle\text{s-}(1,2)}}\\ \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow} && \source{\Big\downarrow\rlap{\scriptstyle\text{s-}(0,1,2,3)}}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & \target{\xrightarrow{\text{t-}(a,b)}} & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} }\\ \end{array}\] | \[\begin{array}{c} && \source{\langle 2, 2 \rangle} && \\[8ex] \hline && \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} } & = & \displaystyle { \source{1,3 \mid 0,2} \brack \target{baba} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\uparrow} && \target{\Big\uparrow\rlap{\scriptstyle\text{t-}(a,b)}}\\ && \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} } & = & \displaystyle { \source{0,2 \mid 1,3} \brack \target{abab} }\\ && \source{\llap{\scriptstyle\text{s-}(1,2)}\Big\uparrow}\\ && \boxed{\displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }} & = & \displaystyle { \source{0,1 \mid 2,3} \brack \target{aabb} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } & = & \displaystyle { \source{0,3 \mid 1,2} \brack \target{abba} } && \target{\Bigg\downarrow\rlap{\scriptstyle\text{t-}(a,b)}}\\ && \source{\llap{\scriptstyle(\text{s-}0,1,2,3)}\Big\downarrow}\\ \target{\llap{\scriptstyle\text{t-}(a,b)}\Bigg\downarrow} && \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} } & = & \displaystyle { \source{2,3 \mid 0,1} \brack \target{bbaa} }\\ && \source{\llap{\scriptstyle\text{s-}(0,1,2,3)}\Big\downarrow}\\ \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} } & = & \displaystyle { \source{1,2 \mid 0,3} \brack \target{baab} }\\ \end{array}\] |
The table at right shows
two ways to depict the $\{2,2\}$-component
with the source and target 1-cells orthogonal to each other,
so that
permutations of the source are shown vertically and
permutations of the target are shown horizontally.
To make this possible, each function appears twice.
The reader may question why it is necessary to label the 1-cells with $\source{\text{s-}}$ and $\target{\text{t-}}$
when the groupoid to which the 1-cell belongs is, in the cases so far considered,
already indicated by the permutation,
and also by color and orientation (horizontal or vertical) of the 1-cell.
As to the color, some readers may be color-blind; also, colors generally don't appear in prints.
As to the permutations being distinguishable, that will not always be the case.
Consider the case where $\source X = \target Y$.
In such a case all the permutations are permutations of the same set,
thus it is necessary to have some way of distinguishing
whether they are intended to act by precomposition or postcomposition.
The $\source{\text{s-}}$ and $\target{\text{t-}}$ prefixes do just that.
to distinguish between a permutation acting on the source or target,
consider the double groupoid associated to $\source X = \target Y = \{0,1,2,3\}$,
i.e., $S_{\{0,1,2,3\}}$ acting on both sides of $\homst {\{0,1,2,3\}} \Set {\{0,1,2,3\}}$,
and in that double groupoid, consider the 2-cell at right.
Note that (both of the intermediate 0-cells) are the same, namely (the function $\target 1010$).
Thus (both the top and left 1-cells) have (exactly the same source and target);
we may say that (they are parallel 1-cells) in (the double groupoid),
and depict (the commonality of their sources and targets) through the diagram
to specify whether permutations are acting via pre- or post- composition
References
“The bimodule of sets, functions and permutations, and its quotients”, 2019The above post was initially created on 2016-06-27.
The construction of the double groupoid is certainly not original,
it is just an adaption of the standard construction of a double category from a mere category,
restricted to functions from a set $X$ to a set $Y$ and permutations of those two sets.
No comments:
Post a Comment