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: Countable subet

  1. Apr 3, 2008 #1
    So, the task is to prove: Every infinite set has a infinite countable subset.


    2. A set [tex]S[/tex] is countable if there exists a bijection [tex]\phi: \mathbb{N}\rightarrow X[/tex]


    3. The attempt at a solution
     
  2. jcsd
  3. Apr 3, 2008 #2
    You can easily construct a countable subset [itex]\{s_1,s_2,\dots\}[/itex] wiht [itex]s_1,s_2,\dots[/itex] being elements of S.

    Let [itex]s_1[/itex] be some element of S. Let inductively [itex]s_n[/itex] be some element of [itex]S-\{s_1,\dots,s_{n-1}\}[/itex].

    Can you show that this works for any infinte set, and that it does not work for any finite set?
     
    Last edited: Apr 3, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook