Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook