Cardinality and Bijection

**oldguynewstudent** · November 4th 2009, 03: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** · November 4th 2009, 04:32 AM

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

**oldguynewstudent** · November 4th 2009, 06:48 PM

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!

**tonio** · November 4th 2009, 08:51 PM

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

Thread: Cardinality and Bijection

LinkBack

Thread Tools

Display

Cardinality and Bijection

Thanks, we were never given that definition

Similar Math Help Forum Discussions

bijection of e^x * ln x

Bijection

Bijection

bijection help

bijection and cardinality

Search Tags