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!


2 Answers 2


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.


I did this counting as part of my bachelor's thesis a few years back. My proof goes in a different direction, but maybe it'll give you some insight.

First of all, define $P_n(\Bbb N) = \{I\subset \Bbb N|\: |I| = n\}$. Every such set is countable, since it's no larger than $\Bbb N^n$ (there is an injection $\iota:P_n(\Bbb N)\to \Bbb N^n$ given by taking an element $I$, sorting its elements and see it as a vector).

Note that we have $P_f(\Bbb N) = \bigcup_n P_n(\Bbb N)$.

Since every $P_n(\Bbb N)$ is countable, index each of them. Now, to index the elements $I_i \in P_f(\Bbb N)$, let $I_1$ be the first element of $P_1(\Bbb N)$, $I_2$ the first element of $P_2(\Bbb N)$, and $I_3$ the second element of $P_1(\Bbb N)$. Now for $I_4$, take the first element from $P_3(\Bbb N)$ and so on, going in a triangular manner. Every element of any $P_n(\Bbb N)$ will eventually be reached by this procedure, and thus we have indexed all elements of $P_f(\Bbb N)$.

PS. I realized toward the end that I had forgotten the empty set, but you know the story of Hilbert's hotel, right?


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .