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

[TeenieBopper]

Homework Statement

Suppose that A and B are both countably infinite sets. Prove that there is a one to one correspondence between A and B.

Homework Equations

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.

 

[SteveL27]

Homework Statement

Suppose that A and B are both countably infinite sets. Prove that there is a one to one correspondence between A and B.

Homework Equations

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.

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.

 

[HallsofIvy]

Homework Statement

Suppose that A and B are both countably infinite sets. Prove that there is a one to one correspondence between A and B.

Homework Equations

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.

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]?

 

[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.

 

[SteveL27]

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.

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

 

[HallsofIvy]

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

 

[SteveL27]

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

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