# Countable subet

1. Apr 3, 2008

### Doom of Doom

So, the task is to prove: Every infinite set has a infinite countable subset.

2. A set $$X$$ is countable if there exists a bijection $$\phi: \mathbb{N}\rightarrow X$$

3. So here's what I have:

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

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

Then I can show that $$\phi$$ 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. Apr 3, 2008

### Pere Callahan

I think it's alright. It's essentially what I suggested, but my answer has disappeared.. maybe it was too explicit..?

3. Apr 3, 2008

### Dick

Your post didn't disappear. It's on the other thread called 'countable sbset'. Don't repost the same question Doom of Doom.

4. Apr 3, 2008

### Pere Callahan

Oh, I see, thanks Dick

5. Apr 4, 2008

### Doom of Doom

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.