2
$\begingroup$

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?

  • 0
    Identical to [Why doesn't this work imply that there are countably many subsets of the naturals?](http://math.stackexchange.com/questions/97509/why-doesnt-this-work-imply-that-there-are-countably-many-subsets-of-the-natural)2012-05-23

2 Answers 2

6

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.

  • 0
    Oh my god. I can't believe I missed that. Thank you very much!2012-04-25
0

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.