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

  • $\begingroup$ 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\}$? $\endgroup$ – Mees de Vries Aug 26 '16 at 12:34
  • $\begingroup$ Thats right.... $\endgroup$ – Bozo Vulicevic Aug 26 '16 at 12:37
  • $\begingroup$ I could do it using prime numbers $\endgroup$ – Bozo Vulicevic Aug 26 '16 at 12:38
  • $\begingroup$ 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. $\endgroup$ – Zestylemonzi Aug 26 '16 at 12:47
  • $\begingroup$ 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. $\endgroup$ – hkr Aug 26 '16 at 17:03

Your Answer

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

Browse other questions tagged or ask your own question.