The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 votes
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 every element in codomain have exactly one element in 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
Nice explanation...
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.
No the second one you mentioned that mapping from function S to s is onto!

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
41,454 users