Real Analysis: one to one correspondence between two countably infinite sets

1. Feb 28, 2012

TeenieBopper

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. Feb 28, 2012

SteveL27

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.

3. Feb 28, 2012

HallsofIvy

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 $f(g^{-1}(bn))$ or $g(f^{-1}(an))$?

4. Feb 28, 2012

TeenieBopper

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
5. Feb 28, 2012

SteveL27

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

6. Feb 28, 2012

HallsofIvy

You mean the composition f composed with g-1, don't you?

7. Feb 28, 2012

SteveL27

Yes, in the OP's notation. Right you are.