Infinite subset of Denumerable set is denumerable? > **Possible Duplicate:** > An infinite subset of a countable set is countable If $B$ is a denumerable set and $C$ is a subset of $B$ and is infinite, $C$ is denumerable. Hint or proof please

Since $B$ is denumerable, there is a bijection $f: B \rightarrow \mathbb{N}$. Put a strict total order $\prec$ on $B$ defined by $x \prec y$ if and only if $f(x) < f(y)$ for $x,y \in B$.

Define now $\prec$ on $C$ via restriction and define a function $g: \mathbb{N} \rightarrow C$ in the natural way ($g(0)$ is the least element of $C$, $g(1)$ is the least element of $C \setminus \\{g(0)\\}$, and so on).

The function $g$ is injective because $\prec$ is a strict total order and is surjective because $C$ is infinite.