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.

And how can I prove it by using induction?

4. Originally Posted by selinunan

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$.