1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Theoretical Math: Proving an injection when it's countably infinite.

  1. Apr 25, 2012 #1
    1. The problem statement, all variables and given/known data

    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?

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Apr 26, 2012 #2
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook