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