Take the 2-minute tour ×

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

share|improve this question

marked as duplicate by Asaf Karagila, Austin Mohr, Martin Sleziak, Rahul, Rudy the Reindeer May 10 '12 at 11:15


Huh? Where does $B$ get into the picture? Did you mean $C\subseteq B$? –  Asaf Karagila May 10 '12 at 8:14
Right It was a typo ;) –  Katlus May 10 '12 at 8:15

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer

Elements of $B$ can be arranged in a sequence $(x_n)$. Construct a subsequence $(x_{n_k})$ inductively as follows: Let $x_{n_1}$ be the first element of $(x_n)$ which is in $C$. Assuming $x_{n_k}$ has been chosen, consider the least integer $n_{k+1}$ such that $n_{k+1}>n_k$ and that $x_{n_{k+1}}\in C$. Clearly the subsequence $(x_{n_k})$ contains all of $C$, following which $C$ is denumerable.

share|improve this answer
