# Proving that $S_k = \{A \subset \mathbb{N} : |A| = k\}$ for $k\in\mathbb{N}$ is denumerable. [duplicate]

I am having trouble with this problem for quite some time. I posted this question before but I still can not figure out this problem.

So far,from the suggestion of user134824, I have tried to define an injective function $f$ from $S_k$ to $\mathbb{N}$ as $f_k({n_1,n_2,...n_k})=p_1^{n_1}p_2^{n_2}...p_k^{n_k}$. I am able to prove that this function is injective. However, after this point, I am stuck. I can either prove that $f$ is bijective by proving it is surjective or I can find an injective function $g:\mathbb{N}\rightarrow S_k$ and use the Schroeder-Bernstein theorem.

## marked as duplicate by ml0105, Asaf Karagila♦, user99914, user63181, user98602 Apr 23 '14 at 6:55

• What about $g(n) = \{1, 2, ..., n\}$ which is an injective map from $\mathbb{N} \to S_n$ – Mustafa Said Apr 23 '14 at 4:32
• The correct course is not to re-post, but rather to ask for clarification, or edit the previous question to emphasize what you don't understand from the previously given answers. – Asaf Karagila Apr 23 '14 at 4:32
• Sorry, I will not do so in the future. – mrQWERTY Apr 23 '14 at 4:35

Your function $f$ is clearly not surjective, since $p_{k+1}$ (I assume that the $p_k$'s are the sequence of prime numbers) is not in the range of $f$.
However, there are plenty of injections from ${\mathbb N}$ into $S_k$: $g(n)=\{\ n,n+1,\dots,n+k-1\ \}$ for example.
You want to prove that the set of all $k$-sized subsets of $\mathbb N$ is countable (or denumerable if you like).
So the problem is essentially combinatorial. You have $k$ "slots" in which to place a natural number. So in fact, the set of all such $A$ is a subset of $\mathbb N \times \mathbb N \times \dotsc \mathbb N$ (k times). (precisely, it is the subset of this product such that no two numbers are equal. In any case - the product is countable)