Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
See also math.stackexchange.com/questions/97509/… –  Jonas Meyer May 23 '12 at 14:27
    
add comment

2 Answers 2

up vote 3 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|improve this answer
    
Oh my god. I can't believe I missed that. Thank you very much! –  iolo Apr 25 '12 at 14:32
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.