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

In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I wrote below is valid?

Let $S$ be an infinite subset of a countable set $T$. Since $T$ is countable, there exists a bijection $f: \mathbb{N} \rightarrow T$. And $S \subseteq T = \{ f(n) \ | \ n \in \mathbb{N} \}$. Let $n_{1}$ be the smallest positive integer such that $f(n_{1}) \in S$. And continue where $n_{k}$ is the smallest positive integer greater than $n_{k-1}$ such that $f(n_{k}) \in S$. And because $S$ is infinite, we continue forever. Now consider the function $\beta : \mathbb{N} \rightarrow S$ which sends $k \rightarrow f(n_{k})$.

So in order for $S$ to be countable, $\beta$ would have to be a bijection. $\beta$ is injective since if $f(n_{k}) = f(n_{j})$, then $n_{k} = n_{j}$ because $f$ is injective. We also can conclude $k = j$ because the various $n_{i}$ chosen were strictly increasing.

Edit: $\beta$ also needs to be surjective. So for every $r \in S$ there exists a $q \in \mathbb{N}$ such that $\beta(q) = f(n_{q}) = r$. We know that $f^{-1}(r) \in \{n_{1}, n_{2}, ..., n_{k} ... \}$, so we can let $f^{-1}(r) = n_{d}$. Thus $\beta(d) = f(n_{d}) = r$.

share|cite|improve this question
Your last statement doesn't really prove $\beta$ is surjective. You still need to establish that $q=f^{-1}(r)$ is equal to $n_k$ for some $k$. – Bill Cook Feb 9 '12 at 21:41
You're on the right track. Perhaps it is easier to show that any infinite subset of $\mathbb{N}$ is countable. In this case you can always use the fact that any nonempty subset of $\mathbb{N}$ contains the least element, in which case you have already done most of the proof above. Once you have demonstrated that any infinite subset of $\mathbb{N}$ is countable, notice that $f$ establishes a bijection between $S$ and an infinite subset of $\mathbb{N}$. – William Feb 9 '12 at 21:41
@Bill: That $f$ is a bijection is given. – Brian M. Scott Feb 9 '12 at 21:41

To fix the last statement:

Suppose that $q=f^{-1}(r)$. Then $\{ 0,1,2,\dots,q\}$ is a finite set. Intersect this with $f^{-1}(S) = \{ n \in \mathbb{N} \;|\; f(n) \in S\}$ and get a finite set. By your definition of the $n_k$'s this set is $\{n_0,n_1,\dots,n_\ell\}$ for some $\ell$. Thus $q=n_\ell$. Therefore, $\beta(\ell)=f(n_\ell)=f(q)=r$. Patched.

share|cite|improve this answer
Can you see if I understand what you mean in my edit? – Student Feb 9 '12 at 22:23
That's seems reasonable. – Bill Cook Feb 9 '12 at 22:35
@BillCook how is {0,1,2,...q} is finite ? thanks – Taylor Ted Jul 8 '15 at 5:17
It's finite since $\{0,1,2,\dots,q\}$ has exactly $q+1$ elements (a finite number of elements). – Bill Cook Jul 8 '15 at 11:18

The set $A$ is countable if there is $f:A\to\mathbb N$ which is injective.

Suppose $B\subseteq A$ then $f|_B:B\to\mathbb N$ is also injective, simply because you restrict an injective function you cannot counterexample the injectivity.

Suppose that $f:A\to\mathbb N$ is a bijection and $B\subseteq A$ is infinite. Let $N=\{f(b)\mid b\in B\}$, the image of $B$.

Since $B$ is infinite, we have that $N$ is infinite. Let us show that an infinite subset of $\mathbb N$ is countable:

We define inductively a function $g:\mathbb N\to N$, $g(0)=\min N$ the minimal number in $N$. Suppose $g(n)$ was defined, let $g(n+1)$ be the least number in $N$ which is larger than $g(n)$.

It is obvious that $g$ is a bijection between $\mathbb N$ and $N$. Now we have that $g^{-1}\circ f|_B:B\to\mathbb N$ is a bijection, as wanted.

share|cite|improve this answer
I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering. – William Feb 9 '12 at 21:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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