Results 1 to 12 of 12

Math Help - Cardinality of Sets

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    Cardinality of Sets

    Q: Consider set A and B.

    Their exists 'f' an onto mappping from A -> B
    Similarliy their exists 'g' an onto mapping from B -> A

    Prove that their exists a bijection between A,B. (i.e. they have same cardinality)

    Can anyone please help me get started with this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    Q: Consider set A and B.

    Their exists 'f' an onto mappping from A -> B
    Similarliy their exists 'g' an onto mapping from B -> A

    Prove that their exists a bijection between A,B. (i.e. they have same cardinality)

    Can anyone please help me get started with this?
    Let f: A \rightarrow B be a surjection. Then there exists a function f^{-1}:B \rightarrow A defined such that f(f^{-1}(a)) = a - essentially, you look at the sets of pre-images of elements in B and choose a specific element from each set (this is a function as f is a surjection).

    So, for example, if A = \mathbb{Q} and B = \mathbb{N} with f:a.x_1x_2 \mapsto a (truncate the decimal expansion) then set f^{-1}(a) = a, but equally it could be a.5 or a.14159\ldots etc. Does that make sense?...

    What can you say about this function f^{-1}?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Swlabr View Post
    Let f: A \rightarrow B be a surjection. Then there exists a function f^{-1}:B \rightarrow A defined such that f(f^{-1}(a)) = a - essentially, you look at the sets of pre-images of elements in B and choose a specific element from each set (this is a function as f is a surjection).

    So, for example, if A = \mathbb{Q} and B = \mathbb{N} with f:a.x_1x_2 \mapsto a (truncate the decimal expansion) then set f^{-1}(a) = a, but equally it could be a.5 or a.14159\ldots etc. Does that make sense?...

    What can you say about this function f^{-1}?
    Yes I follow you -

    f^{-1} is an into function from B \rightarrow A

    But I'm sry, unable to take the argument forward.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    Yes I follow you -

    f^{-1} is an into function from B \rightarrow A

    But I'm sry, unable to take the argument forward.
    Well, it is well-known that if there is an injection h: A\rightarrow B then |A| \leq |B|. This is what I was heading for. Is this a fact that you know?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Swlabr View Post
    Well, it is well-known that if there is an injection h: A\rightarrow B then |A| \leq |B|. This is what I was heading for. Is this a fact that you know?
    Yes I know that. So your argument is |A|<=|B| and similarliy |A|>=|B| and thus conclude |A| = |B|. Am I correct?

    But I was trying to establish that
    1. there exists a bijection
    2. construct this bijection (if possible) and
    3. then arrive at |A| = |B|.

    (definition I am using is if there is bijection between A and B then |A| = |B|)

    Any idea there?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    Yes I know that. So your argument is |A|<=|B| and similarliy |A|>=|B| and thus conclude |A| = |B|. Am I correct?

    But I was trying to establish that
    1. there exists a bijection
    2. construct this bijection (if possible) and
    3. then arrive at |A| = |B|.

    (definition I am using is if there is bijection between A and B then |A| = |B|)

    Any idea there?

    Thanks
    But surely this proves that there is a bijection? If two sets have the same cardinality, there exists a bijection between them.

    What I would now do is look at the proof of the injectivity and see if this is a constructive proof. I recon it should be. This will then give you your answer.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Swlabr View Post
    But surely this proves that there is a bijection? If two sets have the same cardinality, there exists a bijection between them.

    What I would now do is look at the proof of the injectivity and see if this is a constructive proof. I recon it should be. This will then give you your answer.
    Yes it surely does.

    But I'm more interested in finding out a bijection.

    Can you guide me where can I read the approach you suggested further plz?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by aman_cc View Post
    Yes it surely does.

    But I'm more interested in finding out a bijection.

    Can you guide me where can I read the approach you suggested further plz?
    On second thought - you said

    " Well, it is well-known that if there is an injection then . "

    So, is this an axiom or a theorm. If later - any idea to prove it? Myabe that will help me get some clarity here
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    Yes it surely does.

    But I'm more interested in finding out a bijection.

    Can you guide me where can I read the approach you suggested further plz?
    The theorem is called, I believe, the Schroeder–Bernstein theorem. So, pick your favourite undergraduate introduction to pure mathematics and look in there.

    There is, apparently, a proof on wiki. I haven't read over it though.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Swlabr View Post
    The theorem is called, I believe, the Schroeder–Bernstein theorem. So, pick your favourite undergraduate introduction to pure mathematics and look in there.

    There is, apparently, a proof on wiki. I haven't read over it though.
    Thanks this is exactly what I was looking for. Thanks for your help.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    I agree that for this particular problem, it's probably better to refer to a textbook proof, since it is not the kind of problem a beginner is likely able to solve by him or herself.

    By the way, some proofs use recursion on the set of natural numbers (thus supposing the axiom of infinity), but other proofs don't rely on recursion. Two very different proofs (neither relying on recursion) can be found, e.g., in two different Dover textbooks: One by Stoll and one by Suppes. I think the proof in Stoll is the nicest I've seen. The one in Suppes is very clever too, but what a crazy winding road it is!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by MoeBlee View Post
    I agree that for this particular problem, it's probably better to refer to a textbook proof, since it is not the kind of problem a beginner is likely able to solve by him or herself.

    By the way, some proofs use recursion on the set of natural numbers (thus supposing the axiom of infinity), but other proofs don't rely on recursion. Two very different proofs (neither relying on recursion) can be found, e.g., in two different Dover textbooks: One by Stoll and one by Suppes. I think the proof in Stoll is the nicest I've seen. The one in Suppes is very clever too, but what a crazy winding road it is!
    Thanks for your help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 05:26 PM
  2. cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2010, 12:42 PM
  3. Cardinality of these sets!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 4th 2010, 07:27 AM
  4. Cardinality of sets Q and R
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 14th 2009, 12:30 PM
  5. Cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 18th 2007, 03:30 PM

Search Tags


/mathhelpforum @mathhelpforum