# Countability

• Oct 11th 2008, 05: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, 08: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 $\displaystyle S\in P_k(\mathbb{N})$ then $\displaystyle S$ can be well-ordered. Thus, basically write $\displaystyle \{a_0,a_1,...,a_{k-1}\}$ in increasing order. Then consider the mapping $\displaystyle \{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, 04:45 AM
selinunan
If it is true for $\displaystyle k$ i.e. there is injection $\displaystyle g: P_k(\mathbb{N}) \to \mathbb{N}^k$. Then define $\displaystyle f: P_{k+1}(\mathbb{N})\to \mathbb{N}^{k+1}$ by $\displaystyle f(S) = (a,g(S-\{ a \}))$ where $\displaystyle a$ is least element of $\displaystyle S$.