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]X[/tex] is countable if there exists a bijection [tex]\phi: \mathbb{N}\rightarrow X[/tex]

    3. So here's what I have:

    Let [tex]A[/tex] be an infinite set, and pick some [tex]a_{1}\in A[/tex]. Define [tex]S_{n}=\left\{a_{i} [/tex], [tex]i\in \mathbb{N} \left| 1\leq i \leq n \right\} [/tex].
    Pick [tex]a_{n}\in (A - S_{n-1})[/tex] for each [tex]n \in \mathbb{N}[/tex], [tex]n>1[/tex].

    Let [tex]X=\left\{a_{n}|n \in \mathbb{N}\right\}[/tex], and let [tex]\phi: \mathbb{N}\rightarrow X[/tex] by [tex]\phi(x)=a_{x}[/tex].

    Then I can show that [tex]\phi[/tex] is a bijection, and thus I am done. Is this good? I'm sure there has to be a better way to do this.
    Last edited: Apr 3, 2008
  2. jcsd
  3. Apr 3, 2008 #2
    I think it's alright. It's essentially what I suggested, but my answer has disappeared.. maybe it was too explicit..?
  4. Apr 3, 2008 #3


    User Avatar
    Science Advisor
    Homework Helper

    Your post didn't disappear. It's on the other thread called 'countable sbset'. Don't repost the same question Doom of Doom.
  5. Apr 3, 2008 #4
    Oh, I see, thanks Dick :smile:
  6. Apr 4, 2008 #5
    I am sorry. My internet crashed right when i submitted the post, then when I went back later I didn't see my original post, so I made a new one.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook