Functions Problem 7

Solution, Method 1

There are \(2^5 = 32\) functions from A to B. Most of these are onto, the only exceptions being the two functions that map all elements of A to the same element of B. So there are \(32- 2 = 30\) onto functions from A to B. This method is very slick but also harder to come up with. A student found it, not the course staff.

Solution, Method 2

Since it doesn't matter what the elements of A and B are named, let's suppose that \(A = \{1,2,3,4,5\}\) and \(B = \{x,y\}\). Now, let's divide up our problem based on how many elements of A map to x. Since the function is onto, this number must be between 1 and 4. Case 1: 1 element of A maps onto x. There are five possibilities for what this element is. Case 2: 2 elements of A map onto x. There are \(5 \cdot 4 = 20\) ways to choose an ordered pair of two elements. But we don't care about the order, so we need to divide by 2. So there are 10 ways to choose a pair of two elements. Case 3: 3 elements of A map onto x. This is similar to case 2, just reverse the roles of x and y. Case 4: 4 elements of A map onto y. This is similar to case 1. So, in total, we have \(5 + 10 + 10 + 5 = 30\) ways to construct our onto function. This method is more plodding but also easier to come up with.