Prove that any subset of any countable set $S$ is countable Prove that any subset of any countable set S is countable
Here is what I got
Proof: 
We assume that $W$ is a subset of a countable set $S$. We will show that $W$ is also countable.
Since $W$ is a subset of $S$, we need to consider 2 cases where 
Case 1:$W=S$
In this case, since $S$ is countable and  $W=S$, so $W$ is also countable.
Case 2 : $W⊂S$
Since S is countable, S has the same cardinality as the set of positive integers N. By the definition of “having same cardinality”, there is a one to one function $f:S→N$ for N={1,2,3,…,n} for $n$ is a positive integer. Since $W⊂S$, for $m∈N$, let $i_1,i_2,…,i_m$ be the element of {1,2,3,…,n} in the image of W. Define g:W→{1,2,3…,m} such that $g(w)=j$ for $f(w)=i_j$ for all$ w∈W$. This show that g:W→{1,2,3,…,m} is one to one, so $W$ is finite, thus W is countable. 
Is it correct? I'm not so sure about case 2.
 A: A set $S$ is countable iff there is an onto map $f:\mathbb{N} \rightarrow S$.  Using this criterion, it is easy to see that a subset of a countable set is countable.
A: There is a mistake in your proof. You assume that a countable set $S$ has a bijection $f: S \rightarrow \mathbb{N}$, but you only have an injection:
Otherwise i.e. a one-element subset would not be countable.
Here is how you could fix it:
As $S$ is countable there is an injective map $f: S \rightarrow \mathbb{N}$. Now
let $U\subseteq S$. Consider the restriction $g: U \rightarrow \mathbb{N}$ of $f$ onto $U$. 
If $g(x)=g(y)$ for some $x,y \in U$ then $f(x)=f(y)$ and thus $x=y$. Therefore $g$ is injective, which shows that $U$ is countable.
A: Since S is countable, there is a bijection $f: \mathbb{N} \rightarrow S$.
Now let $M=f^{-1}(W)$, and define a bijection $g: \mathbb{N} \rightarrow W$ inductively as follows:
1) Let $g(1)=f(i_1)$, where $i_1=\min M$.
2) If $g(1),\cdots,g(n)$ have been defined, let 
$\;\;\;g(n+1)=f(i_{n+1})$, where $i_{n+1}=\min\{i:i>i_n, i\in M\}$.
A: Since $S$ is countable there is an injective map $f : S \to \mathbb{N}$.  Since $W$ is a subset of $S$, there is an injective map $g\colon W\to S$.  The composition $f\circ g : W \to \mathbb{N}$ exists and is an injection, hence $W$ is countable.
(You may need to prove an injection composed with an injection is still injective, depending on your professor and what material you have covered or taken for granted.  You may also need to write some exposition on the existence of $g$, depending on your prof.)
