# Math Help - Cardinality and Bijection

1. ## Cardinality and Bijection

This was a question on my last test. The whole class got it wrong. I understand the falacy of my argument because there might be other functions f defined other than the bijection I stipulated. Can anyone help solve this? Thanks.

Suppose f: A $\rightarrow$B is a function between two finite sets A and B with the same cardinality. Prove that f is 1-1 iff f is onto.

2. Originally Posted by oldguynewstudent
This was a question on my last test. The whole class got it wrong. I understand the falacy of my argument because there might be other functions f defined other than the bijection I stipulated. Can anyone help solve this? Thanks.

Suppose f: A $\rightarrow$B is a function between two finite sets A and B with the same cardinality. Prove that f is 1-1 iff f is onto.

Let $A=\{a_1,...,a_n\}\,,\,\,B\{b_1,...,b_n\}$ :

1) Suppose f is 1-1 ==> the set $f(A)\subset B$ has as many elements as A (and as B) ==> $f(A)=B$, otherwise B is a finite set having a proper subset with its same cardinality and this is the definition of INFINITE sets ==> f is onto.

2) Suppose now that f is onto ==> $f(A)=B$; if $f(a_i)=f(a_j)\,\,and\,\,a_i\neq a_j$ then $Card(f(A))\leq n-1$, which is impossible since $Card(F(A))=Card (B)=n$, thus it must be that $a_i=a_j$ ==> f is 1-1.

Tonio

3. ## Thanks, we were never given that definition

Originally Posted by tonio
Let $A=\{a_1,...,a_n\}\,,\,\,B\{b_1,...,b_n\}$ :

1) Suppose f is 1-1 ==> the set $f(A)\subset B$ has as many elements as A (and as B) ==> $f(A)=B$, otherwise B is a finite set having a proper subset with its same cardinality and this is the definition of INFINITE sets ==> f is onto.

2) Suppose now that f is onto ==> $f(A)=B$; if $f(a_i)=f(a_j)\,\,and\,\,a_i\neq a_j$ then $Card(f(A))\leq n-1$, which is impossible since $Card(F(A))=Card (B)=n$, thus it must be that $a_i=a_j$ ==> f is 1-1.

Tonio
Thanks, we were never given that definition. The only definition in Rosen is "A set is said to be infinite if it is not finite."

This is the first math class I've ever taken that has not been fun!

4. Originally Posted by oldguynewstudent
Thanks, we were never given that definition. The only definition in Rosen is "A set is said to be infinite if it is not finite."

This is the first math class I've ever taken that has not been fun!

And yet it is a rather important class. Go to your school's library and dive into set theory books to help you out in your hours of desperation: set theory can be very nice, beautiful and mind-blowing.

Tonio