# The set of subsets of size $k$ in $\mathbb{N}$ is countable

Let $P_{k}(\mathbb{N}) = \{ A \subset \mathbb{N} \ | \ |A|=k \}$. I want to prove that $P_k$ is countable for each $k$.

So I showed that this was a set of countable subsets, but I am not sure how to construct a one to one function to naturals.

I was also wondering how to prove that the set of all finite subsets of $\mathbb{N}$ is countable to make the proof easier, so I constructed the function $g = r^n$ from $r = 1$ to infinity where $n \in f$ where $f$ is a function that maps the elements of the finite countable sets into $\mathbb{N}$

An idea: take any element $\;X\in P_k(\Bbb N)\;$ and write its elements in ascending order:

$$X=\{a_1,a_2,...,a_k\} \;,\;\;a_1<a_2<\ldots <a_k$$

Now, with this agreement on, show that

$$f: P_k(\Bbb N)\to\Bbb N\;,\;\;f\left(\{a_1,...,a_k)\right):=\sum_{m=1}^k a_{m-1} 10^{m-1}$$

is an injection, and thus $\;\left|P_k(\Bbb N)\right|\le\aleph_0\;$

If by "countable" you also mean "infinite", show that

$$\;\left|\{\;\{1,2,...,k\}\,,\,\, \{1,2,...,k-1,k+1\}\;,\;\;\{1,2,...,k-1,k+2\}\,,\ldots\right|=\aleph_0$$

Let $\varphi:\Bbb P_k(\Bbb N)\to \Bbb N^k$ by $\varphi(A)=(x_1,\ldots,x_k)$ with $A=\{x_1,\ldots,x_k\}$ and $x_1<\ldots<x_k$.

$\varphi$ is injective, and $\Bbb N^k$ is countable. Hence $\Bbb P_k(\Bbb N)$ is countable.

• I think there's a fair chance the OP doesn't yet know /or can't use that $\;|\Bbb N^k|=\aleph_0\;,\;\;\forall\;k\in\Bbb N\;$ – Timbuc Oct 7 '14 at 12:34

Isn't $$P_k(\mathbb N) = \bigcup_l P_k^l(\mathbb N)$$ a countable union of countable sets, where $$P_k^l(\mathbb N) = \{ A \subseteq \{1,\dots,l\} | |A|=k\}$$