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.
Best Answer
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.