we give an example of how those parts may be used classify functions between sets.
For our classification example, we let $X=\{1,2,3\}$ and $Y=\{a,b,c\}$.
Each set has three elements, so there are $3^3=27$ functions from $\{1,2,3\}$ to $\{a,b,c\}$.
The image must be a subset of $\{a,b,c\}$, hence it can have $1, 2$ or $3$ elements.
This gives the first level of our classification, the cardinality of the image.
If (the image is a singleton),
the function $\functionf$ is completely determined by (which of $\{a,b,c\}$ is in its image).
There are precisely three functions (with image a singleton).
Their representations as words are: $$aaa, bbb, ccc \; .$$ If the image has $3$ elements, than $f$ must be a bijection between $\{1,2,3\}$ and $\{a,b,c\}$.
There are $3! = 6$ such bijections.
Their representations as words are: $$abc, acb, bac, bca, cab, cba \; .$$ That takes care of (the three functions whose image has one element)
and (the six functions whose image has three elements),
leaving $27-3-6=18$ functions to be accounted for.
Fortuitously (!) there are in fact precisely $18$ functions with image a doubleton (a $2$-subset).
For each such function, the size of both (its kernel-partition) and (its image) is two.
There are (three $2$-partitions of $\{1,2,3\}$) and (three doubletons ($2$-subsets) of $\{a,b,c\}$), and
for each ($2$-partition/$2$-subset pair) there are ($2!=2$ bijections) between (the $2$-partition) and (the $2$-subset),
giving ($3\times 2\times 3=18$ functions) whose kernel-partition and image are each a doubleton.
Those functions are shown in the following table,
indexed by their kernel-partition and image.
(The representation as a word) is used to specify (the function). \[\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{cccc} & \smash{\Rule {1px} {3ex} {23ex}} && \smash{\Rule {1px} {3ex} {23ex}} & {} \rlap{\mkern-2.2em \text{strong unordered $2$-partitions of $\{1,2,3\}$}} \\[2ex] \hline && && \bigl\{\{1,2\},\{3\}\bigr\} & \bigl\{\{1,3\},\{2\}\bigr\} & \bigl\{\{2,3\},\{1\}\bigr\}\\ && && 1\,2\mid 3 & 1\,3\mid 2 & 2\,3\mid 1\\[2ex] \hline && \{a,b\} && aab,\;bba & aba,\;bab & baa,\;abb\\ \text{$2$-subsets of $\{a,b,c\}$} && \{a,c\} && aac,\;cca & aca,\;cac & caa,\;acc\\ && \{b,c\} && bbc,\;ccb & bcb,\;cbc & cbb,\;bcc\\ \end{array}}\]
The following table summarizes the classification of the $3^3=27$ functions.
The rows correspond to (the potential size of the image, say $i$).
In each row, we show first (the partitions of $\{1,2,3\}$ with $i$ elements, the $i$-partitions),
then (the subsets of $\{a,b,c\}$ with $i$ elements, the $i$-subsets).
Finally we calculate (the total number of functions) with (image of size $i$) using the formula \[\begin{array}{c} \text{(number of partitions of size }i\text{)} & \times & i! & \times & \text{(number of subsets of size }i\text{)} & = \\ \displaystyle {3 \brace i} & \times & i! & \times & \displaystyle {3 \choose i} \\ \end{array}\] \[\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{cccccc} i & \smash{\Rule {1px} {3ex} {19ex}} & \text{$i$-partitions of }\{1,2,3\} && \text{$i$-subsets of }\{a,b,c\} && \text{functions}\\[2ex] \hline 0 && && \emptyset\\ 1 && \bigl\{\{1,2,3\}\bigr\} && \{a\},\;\{b\},\;\{c\} && 1 \times 1\times 3\\ 2 && \bigl\{\{1,2\},\{3\}\bigr\},\;\bigl\{\{1,3\},\{2\}\bigr\},\;\bigl\{\{2,3\},\{1\}\bigr\} && \{a,b\},\;\{a,c\},\;\{b,c\} && 3\times 2\times 3\\ 3 && \bigl\{\{1\},\{2\},\{3\}\bigr\} && \{a,b,c\} && 1\times (3! = 6)\times 1\\ \end{array}}\]
The following figure shows all $2^4=16$ functions
from $[4]=\{0,1,2,3\}$ (for variety we start $[n]$ at $0$) to $\{a,b\}$,
i.e., the elements of $\{a,b\}^{[4]}$,
arranged in columns according to their image multiset.
It shows each function first in ordered kernel-partition form
($a$ component of the partition to the left of the $\mid $-sign, $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\}$.
\[\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{lcccccccc}
&&& \displaystyle { 0,1 \mid 2,3 \brack aabb} \\
&& \displaystyle { 0,1,2 \mid 3 \brack aaab} & \displaystyle { 0,2 \mid 1,3 \brack abab } & \displaystyle { 0 \mid 1,2,3 \brack abbb}\\
&& \displaystyle { 0,1,3 \mid 2 \brack aaba} & \displaystyle { 0,3 \mid 1,2 \brack abba } & \displaystyle { 1 \mid 0,2,3 \brack babb}\\
& \displaystyle { 0,1,2,3 \mid {} \brack aaaa} && \style{color:red;}{\bullet} && \displaystyle { {} \mid 0,1,2,3 \brack bbbb}\\
&& \displaystyle { 0,2,3 \mid 1 \brack abaa} & \displaystyle { 1,2 \mid 0,3 \brack baab } & \displaystyle { 2 \mid 0,1,3 \brack bbab}\\
&& \displaystyle { 1,2,3 \mid 0 \brack baaa} & \displaystyle { 1,3 \mid 0,2 \brack baba } & \displaystyle { 3 \mid 0,1,2 \brack bbba}\\
&&& \displaystyle { 2,3 \mid 0,1 \brack bbaa }\\[2ex]
\hline
\text{size of $S_4$-orbit} & 1 & 4 & 6 & 4 & 1\\
\text{size of $S_4$-stabilizer} & 4!0! & 3!1! & 2!2! & 1!3! & 0!4!\\
\text{template (set form)} & \{\cdotp \cdotp \cdotp \cdotp\} \{\} & \{\cdotp \cdotp \cdotp\} \{\cdotp\} & \{\cdotp \cdotp\} \{\cdotp \cdotp\} & \{\cdotp\} \{\cdotp \cdotp \cdotp\} & \{\} \{\cdotp \cdotp \cdotp \cdotp\}\\
\text{template (divider form)} & \cdotp \cdotp \cdotp \cdotp \mid {} & \cdotp \cdotp \cdotp \mid \cdotp & \cdotp \cdotp \mid \cdotp \cdotp & \cdotp \mid \cdotp \cdotp \cdotp & {} \mid \cdotp \cdotp \cdotp \cdotp\\
\text{partition (binary form)} & 00001 & 00010 & 00100 & 01000 & 10000\\
\text{ordered weak 2-partitions of }4 & 4+0 & 3+1 & 2+2 & 1+3 & 0+4\\
\text{4-multisets on }\{a,b\} & a^4 & a^3b & a^2b^2 & ab^3 & b^4\\
\end{array}}\]
The above figure shows the functions from $[4]=\{0,1,2,3\}$ to $\{\elta,\eltb\}$, i.e., the members of $\hom {([4]=\{0,1,2,3\})} \Set {(\{\elta,\eltb\})}$.That set admits a left action (pre-composition) by $S_4$
and a right action (post-composition) by $S_{\{a,b\}}$,
which are compatible (i.e., associative),
thus it is a left-right bimodule under those two actions.
The orbits of this bimodule under the $S_4$ action (i.e, permutations of the source)
are precisely the five columns of the figure.
For the orbits of the bimodule under the $S_{\{a,b\}}$ action (i.e., permutations of the target),
note that the figure exhibits central symmetry about its center, the ‘$\style{color:red;}{\bullet}$’.
The action of permuting $a$ and $b$ is reflection through the center.
Thus the orbits of the bimodule under the $S_{\{a,b\}}$ action are precisely
the eight orbits under reflection through the center of the figure.
Finally,
the quotient resulting from dividing by both the left and right actions has three orbits,
corresponding to the three unordered weak 2-partitions of $4$: \[4+0, \quad 3+1, \quad 2+2 \; .\] I.e., the only remaining distinction is
identifying how many elements are in each of the two fibers of such a function,
without regard to which elements they are or where they go.
For further information on the quotienting process, see the post “The bimodule of sets, functions and permutations, and its quotients”.
A similar figure exists for the $2^n$ elements of $\{a,b\}^{[n]}$ for each $n \ge 1$.
To show the usefulness of these concepts,
here is a table that organizes the functions between sets
having cardinalities between 1 and 4,
and also the general case of functions between sets $X$ and $Y$
with arbitrary (but finite) cardinalities $|X|=n$, $|Y|=r$.
The organization of the table is that
the cardinality of the source determines the row,
the cardinality of the target determines the column.
For a given source($X$)-target($Y$) pair,
the cardinality of the image may be any number between 1 and $\min(\class{source}{|X|},\class{target}{|Y|})$.
That determines the row within each box.
The $\min$ in the last row of the generic case abbreviates $\min(\class{source}{|X|},\class{target}{|Y|})$.
| $|Y|=r$ | ||||||
|---|---|---|---|---|---|---|
| $1$ | $2$ | $3$ | $4$ | $r$ | ||
| $|X|=n$ | 1 | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}1&=&1\end{array}}=1=\class{target}1^{\class{source}1}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}2&=&2\end{array}}=2={\class{target}2}^{\class{source}1}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}3&=&3\end{array}}=3={\class{target}3}^{\class{source}1}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}4&=&4\end{array}}=4={\class{target}4}^{\class{source}1}$ | |
| $2$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}1&=&1\end{array}}=1={\class{target}1}^{\class{source}2}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}2&=&2\\\class{source}1\times2!\times\class{target}1&=&2\end{array}}=4={\class{target}2}^{\class{source}2}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}3&=&3\\\class{source}1\times2!\times\class{target}3&=&6\end{array}}=9={\class{target}3}^{\class{source}2}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}4&=&4\\\class{source}1\times2!\times\class{target}6&=&12\end{array}}=16={\class{target}4}^{\class{source}2}$ | ||
| $3$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}1&=&1\end{array}}=1={\class{target}1}^{\class{source}3}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}2&=&2\\\class{source}3\times2!\times\class{target}1&=&6\end{array}}=8={\class{target}2}^{\class{source}3}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}3&=&3\\\class{source}3\times2!\times\class{target}3&=&18\\\class{source}1\times3!\times\class{target}1&=&6\end{array}}=27={\class{target}3}^{\class{source}3}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}4&=&4\\\class{source}3\times2!\times\class{target}6&=&36\\\class{source}1\times3!\times\class{target}4&=&24\end{array}}=64={\class{target}4}^{\class{source}3}$ | ||
| $4$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}1&=&1\end{array}}=1={\class{target}1}^{\class{source}4}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}2&=&2\\\class{source}7\times2!\times\class{target}1&=&14\end{array}}=16={\class{target}2}^{\class{source}4}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}3&=&3\\\class{source}7\times2!\times\class{target}3&=&42\\\class{source}6\times3!\times\class{target}1&=&36\end{array}}=81={\class{target}3}^{\class{source}4}$ | $\boxed{\begin{array}{ccr}\class{source}1\times1!\times\class{target}4&=&4\\\class{source}7\times2!\times\class{target}6&=&84\\\class{source}6\times3!\times\class{target}4&=&144\\\class{source}1\times4!\times\class{target}1&=&24\end{array}}=256={\class{target}4}^{\class{source}4}$ | ||
| $n$ | $\boxed{\begin{array}{c}\displaystyle\class{source}{n\brace1}\times1!\times\class{target}{r\choose1}\\ \vdots\\ \displaystyle\class{source}{n\brace k}\times k!\times\class{target}{r\choose k}\\ \vdots\\ \displaystyle\class{source}{n\brace \min}\times \min!\times\class{target}{r\choose \min}\\ \end{array}}={\class{target}r}^{\class{source}n}={\class{target}{|Y|}}^{\class{source}{|X|}}$ | |||||
a table above shows all of the $2^4$ functions from
a set of cardinality $4$ ($\{0,1,2,3\}$) to one of size $2$ ($\{a,b\}$).
Beyond their computational significance,
there are a number of interesting theoretical ways to view these facts.
One of them is that they exemplify that $\Set$ is
the tensor product of its subcategories of surjections and injections
over their intersection, the bijections:
$$\Set \cong \Surj \otimes_\Bij \Inj.$$
References
QKA, “The quotient-kernel adjunction”, 2016PF, “The parts of a function”, 2016
Bimod, “The bimodule of sets, functions and permutations, and its quotients”, 2019
No comments:
Post a Comment