Results 1 to 4 of 4

Math Help - Cardinality and Bijection

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    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 \rightarrowB is a function between two finite sets A and B with the same cardinality. Prove that f is 1-1 iff f is onto.
    Attached Thumbnails Attached Thumbnails Cardinality and Bijection-one_b.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    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 \rightarrowB 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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Thanks, we were never given that definition

    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. bijection of e^x * ln x
    Posted in the Calculus Forum
    Replies: 8
    Last Post: January 20th 2010, 12:46 PM
  2. Bijection
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: January 7th 2010, 06:24 AM
  3. Bijection
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 15th 2009, 12:55 PM
  4. bijection help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 12th 2009, 07:59 PM
  5. bijection and cardinality
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 10th 2008, 01:41 PM

Search Tags


/mathhelpforum @mathhelpforum