# Cardinality of the power set of the set of all primes

Please show me what I am doing wrong...

Given the set $P$ of all primes I can construct the set $Q$ being the power set of P.
Now let $q$ be an element in $Q$. ($q = \{p_1,p_2,p_3,\ldots\}$ where every $p_n$ is an element in $P$.)

Now I can map every $q$ to a number $k$, where $k$ is equal to the product of all elements of $q$. ($k = p_1p_2p_3\ldots$) (for an empty set $q$, $k$ may be equal to one)

Let the set $K$ consist of all possible values of $k$. Now because of the uniqueness of the prime factorization I can also map every number $k$ in $K$ to a $q$ in $Q$. (letting $k=1$ map to $q=\{\}$)
Thus there exists a bijection between $Q$ and $K$. But $K$ is a subset of the natural numbers which are countable, and $Q$, being the power set of $P$, needs to be uncountably infinite (by Cantor's theorem), since $P$ is countably infinite.

This is a contradiction since there cannot exist a bijection between two sets of different cardinality. What am I overlooking?

-
–  Jonas Meyer May 23 '12 at 14:27
–  MJD May 23 '12 at 15:44

Many (most) of the elements $q$ have an infinite number of elements. Then you cannot form the product of those elements. You have shown that the set of finite subsets of the primes is countable, which is correct.
Some of the elements of $Q$ are infinite sets, and for these your proposed $k$ is not well-defined.
The subset $Q'$ of $Q$ where every element of $Q'$ is a finite set of primes is indeed countable, and your argument is valid for this subset.