Cardinality and Bijection

oldguynewstudent · #1 $Old$ November 4th, 2009, 05:29 AM

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.

tonio · #2 $Old$ November 4th, 2009, 06:32 AM

Quote:

Originally Posted by oldguynewstudent $View Post$

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

oldguynewstudent · #3 $Old$ November 4th, 2009, 08:48 PM

Quote:

Originally Posted by tonio $View Post$

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!

tonio · #4 $Old$ November 4th, 2009, 10:51 PM

Quote:

Originally Posted by oldguynewstudent $View Post$

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