f: A --> A where A is finite. Prove f is onto if and only if f is one to one.
if f is 1-1 then it is onto
I was thinking that if f is a function, if a E A, then (a,b) E f and it is mapped to a unique b. therefore there must be at least as many b's as a's in order for f to be a function since A is finite. since all elements of A are present as a's and b's also come from A, all elements of A must be present as a b, therefore f is onto
if f is onto then it is 1-1
I was thinking that since f is onto then all elements of A are present as both first and second terms therefore there is the same number of first and second terms . if f is not 1-1 then there is at least one second term that is paired with two distinct first terms. but if there are the same number of first and second terms there will be at least one second term that cannot be paired with a unique first term since A is finite. it must then either be excluded or be paired with a first term that already appears with a different second term, both of these are contradictions since f is a function and f is onto.
therefore, f is 1-1.
Is this proof too informal? If it is incorrect can someone suggest a different approach
May 20th 2012, 06:06 AM
Re: One-to-one and onto
Yes, your proof is too informal. The first part also does not seem to be correct since you did not use the fact that is one-to-one.
Suppose is finite with elements and is one-to-one. Let Since is one-to-one, we have Therefore has elements since dsitnct give rise to distinct But also has elements and Hence therefore given any we have i.e. there exists such that i.e. is onto.
For the second part, it looks like you have the correct idea, but you need to write your proof like what I've done above. Can you do that?