Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
See also… – Jonas Meyer May 23 '12 at 14:27
up vote 4 down vote accepted

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.

share|cite|improve this answer
Oh my god. I can't believe I missed that. Thank you very much! – iolo Apr 25 '12 at 14:32

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.