The Student Room Group

Surjections

Hi I need help with a question.

If |A| = m 2 and |B| = 2, how many surjections are there from A to B?

My thinking process: if A and B are both sets, A contains m (which is greater than or equal to 2) elements and B contains 2 elements.
So let A = {a1,a2,...m}
Let b = {b1,b2}

So if you're mapping A onto B and it needs to be surjective, every element of B is assigned to some element of A.

Now I don't know where to go from here? To be a surjection b1 and b2 need something form A mapping onto them, right?
Original post by Monaa123
...


Rather than try and count the number of surjections directly, it would be much easier to count the total number of possible mappings and subtract the number that aren't surjections - there aren't many of the latter.
Reply 2
Okay. So would the total number of mappings be 2m? Since every element in A can go to b1 and b2?

It's not a surjection if nothing goes to b1 or nothing goes to b2. So would that just be 2?

2m - 2?
Original post by Monaa123
Okay. So would the total number of mappings be 2m? Since every element in A can go to b1 and b2?


It's somewhat more than 2m.

Consider, how many choices for a1? And a2? And a3? etc.
Edit: And for each choice of a1, we can have any other combination of choices for the others ai, hence 2 times "no. of combinations of other ai", etc., not 2+....



It's not a surjection if nothing goes to b1 or nothing goes to b2. So would that just be 2?

2m - 2?


Yep, there are only two that are not surjections.
(edited 9 years ago)
Reply 4
I think I get it, would it be 2^m - 2?
Original post by Monaa123
I think I get it, would it be 2^m - 2?


You got it.

PS. It's a good idea to quote the other person when you want a reply - a notification shows up on the TSR screen without having to refresh the screen, and you're likely to get a faster reponse.
(edited 9 years ago)
Reply 6
Thank you!!

Ohh okay, how do you quote someone? Sorry, I'm new here
Original post by Monaa123
Thank you!!

Ohh okay, how do you quote someone? Sorry, I'm new here


Just click the "reply" button on the post you want to respond to. You can subsequently edit it so you don't have to quote the whole post.
Reply 8
Original post by ghostwalker
Just click the "reply" button on the post you want to respond to. You can subsequently edit it so you don't have to quote the whole post.


Ohhhh. That makes sense, thank you!

Quick Reply