4
$\begingroup$

The question in my homework is:

How many functions from $\{0,1\} \times \{0,1\}$ to $\{0,1,2\}$ are there? How many are one-to-one? How many are onto?

My first step was to take the Cartesian Product of $\{0,1\} \times \{0,1\}$ in order to get a set

$$A = \{(0,0),(0,1),(1,0),(1,1)\}$$

However I am unsure what to do next. Any help would be greatly appreciated

$\endgroup$
8
  • $\begingroup$ Are you sure you understand the definitions of "one-to-one" and "onto"? can you give an example of each such functions? $\endgroup$ – Daniel Jul 6 '16 at 23:28
  • 1
    $\begingroup$ Then, a useful way begin is by writting down some examples of one-to-one functions and onto functions from $\{0,1\}^2$ to $\{0,1,2\}$ $\endgroup$ – Daniel Jul 6 '16 at 23:32
  • 1
    $\begingroup$ Try to think the problem with cardinalities. How many functions from a set of size $n$ to a set of size $m$ are there? If $n>m$ then there must happen something to the quantity 1-1 functions and therefore to the amount of surjective functions. If you're not familiar with this result try to see what happens with a set of size 3 to sets with size 2,3 and 4. $\endgroup$ – edgar alonso Jul 6 '16 at 23:35
  • 1
    $\begingroup$ @sufronausea okay, I think I understand, since there are 4 possible elements of A then there is no case where a function is injective, because every element in the input needs mapped to the output. $\endgroup$ – Turtle Jul 6 '16 at 23:50
  • 1
    $\begingroup$ @RodrigodeAzevedo Since you have created tags for injective, surjective and bijective functions, I thought it might be a good idea to let you know that it is discussed on meta whether these tags should be kept and removed. I will also add link to this discussion on meta related to creating tags. $\endgroup$ – Martin Sleziak Jul 9 '16 at 7:43
4
$\begingroup$

There's a very very easy way to count how many functions exist from A to B - how many elements does A have? For each element of A, how many different elements of B are there it could map to? Thus, how many total different mappings are there from A to B?

For one-to-one functions, what does that imply? Is it possible to take every element in A and map it to a different element of B?

For onto functions, I can't offhand think of a good way to enumerate them other than to just list all the functions and mark off which ones are onto. You could possibly do it in the other direction by counting how many functions there are such that a given element of B isn't in the image of the function, but then you risk double-counting. Thankfully, the number of possible functions is pretty small.

$\endgroup$
5
  • $\begingroup$ There's a way to count all surjective functions in the general case, but it's pretty ugly actually (Stirling numbers...). $\endgroup$ – Daniel Jul 6 '16 at 23:33
  • $\begingroup$ You can use the Inclusion-Exclusion Principle to count the number of surjective functions. $\endgroup$ – N. F. Taussig Jul 6 '16 at 23:43
  • 2
    $\begingroup$ Okay, I think I understand now.. There are 3 different choices for each possible element of A to map to. I drew out a tree representing each pattern which showed me that there is 3^4 mappings/ functions I believe. Your explanation helped a lot, thank you $\endgroup$ – Turtle Jul 6 '16 at 23:47
  • $\begingroup$ No problem. And @N.F.Taussig is right that you could count the onto functions using Inclusion-Exclusion, which is probably a bit quicker (but also potentially prone to error if you misapply it). $\endgroup$ – ConMan Jul 7 '16 at 0:46
  • $\begingroup$ Or @André Nicolas' answer, which is easier still. $\endgroup$ – ConMan Jul 7 '16 at 0:47
4
$\begingroup$

We count the onto functions. In general, one would use an Inclusion/Exclusion argument, but in our case we can get away with a simpler approach.

If our function is onto, it must map two of the four elements of $A$ to the same thing, and the other two to different things.

The two elements that will be mapped to the same thing can be chosen in $\binom{4}{2}$ ways. The object that they are mapped to can be chosen in $3$ ways, for a total of $\binom{4}{2}\cdot 3$.

For each of these ways, there are $2$ ways to choose where one of the remaining elements of $A$ goes, and now the function is determined. So there are $\binom{4}{2}\cdot 3\cdot 2$ onto functions.

$\endgroup$
2
  • $\begingroup$ Thank you very much for your explanation! $\endgroup$ – Turtle Jul 7 '16 at 0:19
  • $\begingroup$ @Turtle: You are welcome. The same idea works for the number of onto functions from a $k+1$-element set $A$ to a $k$-element set $B$. One can use a similar idea from $k+2$ elements to $k$ elements. Soon after that the number of cases becomes unwieldy, and one uses Inclusion/Exclusion, that is, Stirling numbers of the second kind (please see Wikipedia). $\endgroup$ – André Nicolas Jul 7 '16 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.