I got this problem:

Show that the set of all finite subsets of $\mathbb{N}$ whose size is exactly $n$ where $0<n\in\mathbb{N}$ is countable.

I.e. Show that $|\{P\in\mathbb{P}(\mathbb{N})| |P|=n\}|=\aleph_0$ where $0<n\in\mathbb{N}$.

My solution:

I've defined a one to one map from $\{P\in\mathbb{P}(\mathbb{N})| |P|=n\}$ to the set $\mathbb{N}$ that is based on prime numbers in a similar manner to the first answer in

Show that the set of all finite subsets of $\mathbb{N}$ is countable.

but when I tried to define a one to one map from $\mathbb{N}$ to the set $\{P\in\mathbb{P}(\mathbb{N})| |P|=n\}$, my map wasn't very elegant and very hard to understand.

I am sure there is some elegant solution.

Thanks for any solution.

  • $\begingroup$ Any subset of a countable set is also countable. So it seems fairly easy to prove. Do you need to give an explicit bijection? $\endgroup$ – Thibaut Dumont May 5 '15 at 16:39

Denote $S_n = \{P \subseteq \Bbb N: |P| = n\}$.

Define $f: \Bbb N \to S_n$ by:

$$f(m) = \{1, \ldots, n-1, n+m\}$$

Then it is manifest that $f(m) = f(m')$ implies $n+m = n+m'$ and thus $m = m'$.

Hence $f$ is one-to-one.


Choose $n$ different primes $p_1,\dots,p_n$ and map the finite set $S=\{a_1,\dots,a_n\}$ to $\mathbb N$ by $S\mapsto p_1^{a_1}\cdots p_n^{a_n}$. By unique factorization this is a one-to-one map. You don't need a map in the other direction, any subset of $\mathbb N$ is countable.

  • $\begingroup$ Glad I could help :-) $\endgroup$ – Gregory Grant May 5 '15 at 16:42
  • $\begingroup$ Sorry but I do not get why $|\{P\in\mathbb{P}(\mathbb{N})| |P|=n\}|\geq |\mathbb{N}|$. We already know that $|\{P\in\mathbb{P}(\mathbb{N})| |P|=n\}|\leq |\mathbb{N}|$ since the set $\{P\in\mathbb{P}(\mathbb{N})| |P|=n\}$ is a subset of the set of all finite sets of $\mathbb{N}$ which is countable, But we also need to show that $|\{P\in\mathbb{P}(\mathbb{N})| |P|=n\}|\geq |\mathbb{N}|$ and I am stucked when I try to find a one to one map from the set $\mathbb{N}$ to the set $\{P\in\mathbb{P}(\mathbb{N})| |P|=n\}$ $\endgroup$ – MathNerd May 7 '15 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.