# Countability

• Oct 11th 2008, 06:05 PM
selinunan
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.
• Oct 11th 2008, 09:30 PM
ThePerfectHacker
Quote:

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.
• Oct 12th 2008, 05:45 AM
selinunan
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$.