1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Showing two countably infinite sets have a 1-1 correspondence

  1. Feb 28, 2012 #1
    1. The problem statement, all variables and given/known data
    Suppose A and B are both countably infinite sets. Prove there is a 1-1 correspondence between A and B.


    2. Relevant equations



    3. The attempt at a solution

    Since A is countably infinite, there exists a mapping f such that f maps ℕto A that is 1-1 and onto.

    Similarly for B, there exists a mapping g such that g maps ℕto B that is 1-1 and onto.

    Since g is 1-1 and onto, g^-1 exists and g^-1 maps B into ℕ

    Hence g^-1(b)=n for all b in B.

    Since f(n)=a for all n in ℕ, then f(g^-1(b))=a for all b in B since g^-1(b) yields its corresponding number from ℕ.

    Since f and g are bijective, we can define h as a mapping from B to A by h(b)=a for all b in B by using the ordering created by the mapping g.

    Does this make sense?
     
  2. jcsd
  3. Feb 28, 2012 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Everything is fine up to this point.

    What is n?

    What? This means that f is a constant function, certainly not a bijection.

    You have the right idea, but you aren't expressing it correctly.

    f is a 1-1 mapping of N onto A
    g is a 1-1 mapping of N onto B

    You seek a 1-1 mapping of A onto B. What is that mapping, and how do you know that it is 1-1 and onto?
     
  4. Feb 28, 2012 #3

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Not really.

    At least three of your statements say something other than what you probably intended.

    "Hence g^-1(b)=n for all b in B." says every b in B gets mapped to the same n in .

    Similarly, "Since f(n)=a for all n in ℕ" says that all of the elements of get mapped to the same element of A.

    Also, "then f(g^-1(b))=a for all b in B" says that all of the elements of B get mapped to one single element of A.

    It should be enough to note that since g is a bijection, then so is g-1. Then since f and g-1 are bijections, so is f○g-1.
     
  5. Feb 28, 2012 #4
    n is supposed to be some n in ℕ. What ever it is mapped to.

    I think the mapping is the composite function f(g^-1(n)) and since f and g are 1-1 and onto, the composite function is too.
     
  6. Feb 28, 2012 #5
    I am trying to say that f(some n) = some unique a when I say "f(n)=a". Should I say that for all a in A and n in ℕ?
     
  7. Feb 28, 2012 #6

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    What you want to say is covered by the composition, of f with g-1 being a bijection.

    Otherwise:
    Each element of ℕ is the image of exactly one element of B.

    etc.​
    would be OK, I suppose.
     
  8. Feb 28, 2012 #7
    Here is my revised argument:

    Since A is countably infinite, there exists a mapping f such that f maps ℕto A that is 1-1 and onto.
    Similarly for B, there exists a mapping g such that g maps ℕto B that is 1-1 and onto.

    Since g is 1-1 and onto, g-1 exists and g-1 is 1-1 and onto and maps B into ℕ.

    Then for every element of ℕ, there exists exactly one b that it is the image of.
    Hence there exists a b in B such that g-1(b)=n for some n in ℕ

    Using g-1 in f creates the 1-1 correspondence from A to B.

    Therefore f○g-1 is a bijective mapping from A to B.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook