0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What about $g(n) = \{1, 2, ..., n\}$ which is an injective map from $\mathbb{N} \to S_n$ $\endgroup$ – Mustafa Said Apr 23 '14 at 4:32
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Apr 23 '14 at 4:32
  • $\begingroup$ Sorry, I will not do so in the future. $\endgroup$ – mrQWERTY Apr 23 '14 at 4:35
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$

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