Countability

Printable View

October 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.
October 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 $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.
October 12th 2008, 04:45 AM
selinunan

Thank you for your answer.

And how can I prove it by using induction?
October 12th 2008, 06:26 AM
ThePerfectHacker

Quote:

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