# An infinite subset of a countable set is countable

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$.

• 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}$. – user2093 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.

• 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.

• I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering. – user2093 Feb 9 '12 at 21:44
• With g :ℕ→N, g(0) is undefined. – davide Jul 31 '18 at 13:00
• @davide: ??? I explicitly defined it. – Asaf Karagila Jul 31 '18 at 13:04
• g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ. – davide Jul 31 '18 at 13:09
• @davide: Did you read the word "define"? We define the function $g$. And we define it by recursion. – Asaf Karagila Jul 31 '18 at 13:13