# Partitions for surjective functions

• Aug 21st 2011, 09:08 AM
StefanM
Partitions for surjective functions
Let A be the set of all functions f:{1,2,3,4,5}->{1,2,3} and for i=1,2,3 let Ai denote a subset of the functions f:{1,2,3,4,5}->{1,2,3}\i.

i)What is the size of :
1). A,
2).the sizes of its subsets Ai,and
3).AiAj (i<j) also
4).A1A2A3.

ii)Find with justification the number of surjective functions f:{1,2,3,4,5}->{1,2,3}.

iii)Explain how each surjective function gives a 3-partiton of f:{1,2,3,4,5}

iv)How many 3-partitons of f:{1,2,3,4,5} are there altogethere?

i)1).3^5........2).2^5 each 3).1^5 each.......4).0
ii)We can use stirling numbers of the second kind to find this out S(5,3).
iii)Because the image of the function is made up of 3 elements?
iv)I don't know...I"m still thinking the same as for part ii)
• Aug 21st 2011, 09:27 AM
Plato
Re: Partitions for surjective functions
Some notation. If $\displaystyle f:A\to B$ and $\displaystyle C\subseteq B$ then $\displaystyle f^{-1}[C]=\{x\in A:~f(x)\in C\}$.

It can be shown that if $\displaystyle f$ is a surjection then the collection $\displaystyle \left\{ {f^{ - 1} \left[ {\{ y\} } \right]:{\kern 1pt} y \in B} \right\}$ is a partition of $\displaystyle A$

So is your #iv correct?
• Aug 21st 2011, 09:46 AM
StefanM
Re: Partitions for surjective functions
ah...yes...there 3 in total .....I have the partitions properties in my head I can't describe them here because of the LaTex.
• Aug 21st 2011, 10:22 AM
Plato
Re: Partitions for surjective functions
Quote:

Originally Posted by StefanM
ah...yes...there 3 in total .....I have the partitions properties in my head I can't describe them here because of the LaTex.

Well there are more than three.
There are 150 surjections from a set of five to a set of three.
Each of those surjections defines a three-cell partition of the set of five.

If $\displaystyle \phi:\{1,2,3,4,5\}\to\{1,2,3\}$ is a surjection then $\displaystyle \left\{ {\phi ^{ - 1} (\{ 1\} ),\phi ^{ - 1} (\{ 2\} ),\phi ^{ - 1} (\{ 3\} )} \right\}$ is a partition of $\displaystyle \{1,2,3,4,5\}$