one to one and onto

**stuffthings** · May 20th 2012, 05:25 AM

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

**Sylvia104** · May 20th 2012, 06:06 AM

Yes, your proof is too informal. The first part also does not seem to be correct since you did not use the fact that $f$ is one-to-one.

Suppose $A=\{a_1,a_2,\ldots,a_n\}$ is finite with $n$ elements and $f:A\to A$ is one-to-one. Let $f(A)=\{f(a_i):1\leqslant i \leqslant n\}.$ Since $f$ is one-to-one, we have $i\ne j \Rightarrow a_i\ne a_j \Rightarrow f(a_i)\ne f(a_j).$ Therefore $f(A)$ has $n$ elements since dsitnct $i$ give rise to distinct $f(a_i).$ But $A$ also has $n$ elements and $f(A)\subseteq A.$ Hence $f(A) = A;$ therefore given any $a_j\in A,$ we have $a_j\in f(A),$ i.e. there exists $a_i\in A$ such that $f(a_i)=a_j,$ i.e. $f$ 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?

Thread: one to one and onto

LinkBack

Thread Tools

Display

one to one and onto

Re: One-to-one and onto