Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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

This question was marked as an exact duplicate of an existing question.

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
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|cite|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|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.