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

• Any subset of a countable set is also countable. So it seems fairly easy to prove. Do you need to give an explicit bijection? – 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.

• Glad I could help :-) – Gregory Grant May 5 '15 at 16:42
• 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\}$ – MathNerd May 7 '15 at 17:44