# Countable subet

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:

Related Calculus and Beyond Homework Help News on Phys.org
I think it's alright. It's essentially what I suggested, but my answer has disappeared.. maybe it was too explicit..?

Dick