Theoretical Math: Proving an injection when it's countably infinite.

[mmilton]

Homework Statement

Let f: A --> B be an injection and suppose that the set A is countably infinite; how can I prove that there is an injection from B to A if and only if B is countably infinite?

Also, if we would suppose that A is uncountable, can B be countable?

Homework Equations

The Attempt at a Solution

Here is what I have thus far,

First direction:
Suppose B is countably infinite. Then, by definition, there is a
bijection from B to the naturals. Since A is also countably infinite, there is a bijection
from A to the naturals, and hence a bijection between B and A (and hence injection from B to A).

Next direction:
First show that since f is an injection of a countably infinite set to B, then B must be infinite.
Now, if there is an injection from B to A, then there is a bijection from B to a subset of A, call this subset S. So B and S have the same cardinality. But any infinite subset S of a countably infinite set A is countably infinite, so B has the same cardinality as a countably infinite set S.

 

[Dustinsfl]

For your first direction, I would say instead that since A and B can be put into a 1-1 correspondence with [itex]\mathbb{N}[/itex] we can map the first element of B which is mapped to 1 to the element in A which is mapped to 1 and so forth. Hence we have an injective map from B to A. You don't need bijection since you are only asked about injection.

We are given f is injective from A to B, [itex]A\mapsto\mathbb{N}[/itex] i.e. A is countable infinite, and g:B->A is injective. So since f is injective every element of A maps to an element of B. However, there could be more elements in B but we have that g is also injective so every element of B maps to an element of A and A is countable infinite so B must be what?

I think these are pretty much just straight forward. I don't think you need to worry about a subset for the second one.