I am fighting with an exercise of set theory. There is given a hint to it, but i can't totally understand it, because i am stuck in the first part of it… May i ask you a for little help, please?
Given is $P_{f}(\mathbb{N})\subset P(\mathbb{N})$, where $P_{f}(\mathbb{N})=\left \{ I\subset \mathbb{N}\mid I\, is\, finite \right \}$, defines the power set of $\mathbb{N}$, consisting only of all finite subsets. The idea of the exercise is to show that there exists a bijection between $P_{f}(\mathbb{N})$ and $\mathbb{N}$.
For this exercise i have the following hint. I have to consider the set of the prime numbers $\mathbb{P}$ and $\mathbb{P\, '}\subset \mathbb{P}$, the set of all non zero powers of prime numbers.
a) Consider a set $A\subset \mathbb{N}$, which is infinite. Show that there is a bijective map $g_{A}:A\rightarrow \mathbb{N}$ with $g_{A} (a)=card(A\cap [0,a])$.
So, i know that $A$ as a subset of countable set should be also countable. Then from this follows that the map $g_{A}$ must be injective. It is also surjective, because $A$ is a subset of $\mathbb{N}$. Is this correct? I said nothing about the cardinality of the both subsets…the problem is, that they are both infinite. Intuitively, i think that $\left | A \right |\leq \left | \mathbb{N} \right |$, because both are infinite and contain only natural numbers.
b) Use (a) to show that there is a bijection $\tau :P_{f}(\mathbb{P}\, ')\rightarrow P_{f}(\mathbb{N})$.
Ok, here is clear that it's true, because $P_{f}(\mathbb{P}\, ')\subset P_{f}(\mathbb{N})$ and $\mathbb{P}\, '\subset \mathbb{N}$, both infite sets, because we know by Euclid that the prime numbers are infinitely many.
c) Show that the map $P_{f}(\mathbb{P}\, ')\rightarrow \mathbb{N}$, sending a finite subset $I\subset \mathbb{P}\, '$ to the number $\prod_{q\in I}q$ is a bijection.
Here i intuitively understand what do they mean. I have to use the prime factorization of the numbers, but how to formulate it i am not sure.
Clearly from (c) should follow that there is a bijection between $P_{f}(\mathbb{N})$ and $\mathbb{N}$.
Can anybody help me with this proof? I would be glad to read your remarks, if you have some. Thanks in advance!
Best Answer
Here's how I would do it:
There is an obvious injective map from $\mathbb N$ to $\mathcal P_f(\mathbb N)$.
There is a slightly less obvious injective map the other way: $\{n_1, n_2, n_3, \dotsc, n_k\} \mapsto 2^{n_1}3^{n_2}\dotsb p_k^{n_k}$ where $n_1 < n_2 < \dotsb < n_k$ and $p_i$ denotes the $i$th prime. Injectivity follows from the fundamental theorem of arithmetic.
Now apply Cantor–Bernstein–Schroeder.