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: Real Analysis: one to one correspondence between two countably infinite sets

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


    2. Relevant equations



    3. The attempt at a solution

    By definition of countably infinite, there is a one to one correspondence between Z+ and A and Z+ and B.

    Let n ε Z+. All elements of A and B can be listed as follows

    A = a1, a2, a3, ... , an
    B = b1, b2, b3, ... , bn

    I was going to say that if f(n) = an and f(n) = bn, then an = bn, but f:Z -> A by x and f: Z -> B by x^2 makes this invalid. I know that because A and B are both countably infinite, they are cardinally equivalent, and that if they are cardinally equivalent, then there exists a one to one correspondence between the two sets, but I can't seem to get the proof.
     
  2. jcsd
  3. Feb 28, 2012 #2
    Right. And from here it's a one-liner.

    Hint 1: There's a bijection from A to Z+. There's a bijection from B to Z+. Can we find an easy bijection from A to B?

    Hint 2: Bijections are always invertible.
     
  4. Feb 28, 2012 #3

    HallsofIvy

    User Avatar
    Science Advisor

    Your first error is using "f" for two different functions! There exist a function f such that f(n)= an and another function g such that g(n)= bn. And, since these are one to one, each is invertible. What can you say about [itex]f(g^{-1}(bn))[/itex] or [itex]g(f^{-1}(an))[/itex]?
     
  5. Feb 28, 2012 #4
    There are bijections from Z onto A and Z onto B. Let these be f(n) and g(n), respectively. Because these are bijections, they are also invertable, expressed as f^1(n) and g^1(n), respectively. The bijection A onto B can be expressed as f(g^1(bn)) = an.
     
    Last edited: Feb 28, 2012
  6. Feb 28, 2012 #5
    Yes, but to be completely rigorous you would want to prove that the function f o g (f composed with g) is also a bijection.

    In other words you have a bijection from A to Z+ and a bijection from Z+ to B. By composing the bijections, we have a bijection from A to B -- once we have proved that the composition of bijections is a bijection.

    Pictorially:

    A --> Z+ --> B
     
  7. Feb 28, 2012 #6

    HallsofIvy

    User Avatar
    Science Advisor

    You mean the composition f composed with g-1, don't you?
     
  8. Feb 28, 2012 #7
    Yes, in the OP's notation. Right you are.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook