Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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