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: Every countably infinite set has a countably infinite set

  1. Mar 1, 2012 #1
    1. The problem statement, all variables and given/known data
    Show that every infinite set contains a countably infinite set.


    2. Relevant equations



    3. The attempt at a solution
    Let A be an infinite set

    Since A is infinite and not empty, there exists an a∈A
    Let f be a mapping such that for all n in ℕ such that f(n)=[itex]a_{n}[/itex] for some [itex]a_{n}[/itex].

    Then f(1)=[itex]a_{1}[/itex]. A is an infinite set, so there exists another element [itex]a_{2}[/itex] that is not [itex]a_{1}[/itex] such that f(2)=[itex]a_{2}[/itex] and so on.

    This makes f a 1-1 function.

    Since every element of ℕhas an image, the subset generated by f is onto ℕ.

    Therefore, since f creates a subset of A, infinite subsets have a countable subset.

    --
    Is this a valid proof on why infinite sets have a countably infinite subset?
     
  2. jcsd
  3. Mar 1, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, it is. I would rephrases some of the sentences, but in spirit it's correct.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook