The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
218 views
If the set $S$ has a finite number of elements, prove that if $f$ maps $S$ onto $S$, then $f$ is one-to-one.
asked in Set Theory & Algebra by Veteran (98.9k points) | 218 views

1 Answer

+11 votes
Best answer
let set s={1,2,3,4}

now see mapping from s to s

for f to be onto every element of codomain must be mapped by every element in domain.

since cardinality is same for both domain and codomain. we can not have mapping like f(1)=1 & f(2)=1 if it happened then at least one element remain umapped in codomain,which resultant f not to be onto but it is given that f is onto.so every element in codomain have exactly one element in domain.so one of mapping be like f(1)=2, f(2)=3,f(3)=4,f(4)=1 which certainly prove that f is an one one function also.

NOTE:if s is infinite then this result may not always be true.
answered by Loyal (8.8k points)
selected by
0
Nice explanation...
+1
What is the meaning of this line " if f maps S onto S "?    Is it simply f : S--->S  ? or f : S--->S  is ONTO?

I think it is simply f : S--->S  , is'nt it.
+2
No the second one you mentioned that mapping from function S to s is onto!
0

Thanks, buddy.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,851 questions
41,834 answers
119,102 comments
41,454 users