3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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\;$ $\endgroup$ – Timbuc Oct 7 '14 at 12:34
0
$\begingroup$

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\} $$

$\endgroup$

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.