# Thread: Countability

1. ## Countability

Q ) For a fixed positive integer k, let P_k(N) be the set of all subsets of N with exactly k elements. Prove that P_k(N) is countable.

I think that I should find a 1-1 map from P_k(N) into N^k=N*N*...*N (k times). But unfortunately I couldn't prove it.

2. Originally Posted by selinunan
Q ) For a fixed positive integer k, let P_k(N) be the set of all subsets of N with exactly k elements. Prove that P_k(N) is countable.

I think that I should find a 1-1 map from P_k(N) into N^k=N*N*...*N (k times). But unfortunately I couldn't prove it.
If $S\in P_k(\mathbb{N})$ then $S$ can be well-ordered. Thus, basically write $\{a_0,a_1,...,a_{k-1}\}$ in increasing order. Then consider the mapping $\{a_0,...,a_{k-1} \}\mapsto (a_0,a_1,...,a_{k-1})$. It depends how formal you want to be that is why I used 'basically' - just to say the idea. I think you might need to use an induction and recursion argument here to write out all the details formally if that is what you are looking for.

3. Thank you for your answer.

And how can I prove it by using induction?

4. Originally Posted by selinunan
Thank you for your answer.

And how can I prove it by using induction?
If it is true for $k$ i.e. there is injection $g: P_k(\mathbb{N}) \to \mathbb{N}^k$. Then define $f: P_{k+1}(\mathbb{N})\to \mathbb{N}^{k+1}$ by $f(S) = (a,g(S-\{ a \}))$ where $a$ is least element of $S$.