• Support PF! Buy your school textbooks, materials and every day products Here!

Help with surjective maps

  • Thread starter battousai
  • Start date
  • #1
86
0

Homework Statement



Let S = {1,2,3,...,n}

How many surjective maps are there from S to S?

Homework Equations



n/a

The Attempt at a Solution



The book's answer is n!

However, I thought that total number of surjective maps = n^n because 1-1 isn't required. Where am I wrong?
 

Answers and Replies

  • #2
hunt_mat
Homework Helper
1,724
16
This is understandable as a surjective map from itself to itself, and this is essential just the set S being rearranged, so the answer will be n!.

Mat
 
  • #3
4
0
1-1 is implicitly required, because each element of the domain can only map to one element of the range - so to map to every element of the range you'll need a 1-1 mapping.
 
  • #4
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,517
733

Homework Statement



Let S = {1,2,3,...,n}

How many surjective maps are there from S to S?


The book's answer is n!

However, I thought that total number of surjective maps = n^n because 1-1 isn't required. Where am I wrong?
But since S is finite, if the map wasn't 1-1 it couldn't be onto, could it?
 
  • #5
86
0
1-1 is implicitly required, because each element of the domain can only map to one element of the range - so to map to every element of the range you'll need a 1-1 mapping.
But since S is finite, if the map wasn't 1-1 it couldn't be onto, could it?
Got it. Thanks.
 

Related Threads for: Help with surjective maps

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
4
Views
1K
Replies
28
Views
25K
  • Last Post
Replies
2
Views
3K
Replies
4
Views
19K
  • Last Post
Replies
18
Views
807
Replies
4
Views
1K
Top