# The set of all finite sub-sets of $\mathbb{N}$ is countable and the set of **all** sub-sets of $\mathbb{N}$ is continuum. My Proof.

$K_\mathbb{N}$ set of all finite sub-sets of $\mathbb{N}$. Prove that the cardinal number of $K_\mathbb{N}$ is countable. Also prove that the cardinal number of the set of all sub-sets of $\mathbb{N}$ is continuum($A_\mathbb{N}$). Create a bijection (or injection) between $K_\mathbb{N}$ and $\mathbb{N}$.

First things first, I proved in class that the set of all sequences which members are from $\mathbb{N}$ is continuum. So can I just represent these subsets as sequences? (but rising sequences, so the mapping could be bijective). Then all I would have to do is modify the proof from class that the set of all rising sequences of naturals is continuum cardinality.

Proving that $K_\mathbb{N}=\{a_i,...,a_n\}$is countable, I could maybe do the mapping:

$$f(\{a_1,...,a_n\})=0,a_1...a_n$$ The codomain is a subset of $\mathbb{Q}$ which is countable. This function is injective at the very least, therefore $K_\mathbb{N}$ is countable.

I do know how to make this function (bijection or injection) between $K_\mathbb{N}$ and $\mathbb{N}$.

• Well, if you have a bijection $\mathbb Q \to \mathbb N$, then you could compose them. However, your $f$ does not seem injective -- what about $\{2\}$ and $\{20\}$? Or about $\{1,234\}$ and $\{12,34\}$? – Mees de Vries Aug 26 '16 at 12:34
• Thats right.... – Bozo Vulicevic Aug 26 '16 at 12:37
• I could do it using prime numbers – Bozo Vulicevic Aug 26 '16 at 12:38
• You could - if $A=\{a_1,a_2,...a_n\}$ is a size $n$ subset with $a_1<a_2<...<a_n$ then you can map $A$ to $p_1^{a_1} p_2^{a_2}....p_n^{a_n}$ where the $p_i$ are the first $n$ primes. This is clearly an injection and proves the countability of finite subsets. – Zestylemonzi Aug 26 '16 at 12:47
• Isn't the second half of what you're trying to prove that the set of all subsets of $\mathbb{N}$ is uncountable? It can be proven using Cantor's diagonal argument. That it's the cardinality of the continuum is called the continuum hypothesis, and quite a different matter. – hkr Aug 26 '16 at 17:03