Subsets of the set of primes - uncountable or countable?

1. Mar 27, 2010

realitybugll

Subsets of the set of primes -- uncountable or countable??

Cantor proved that the sub-sets of the natural numbers are uncountable.

assuming that the the set of primes can be put in a 1-to-1 matching with the natural numbers (which I believe they can...) then it would follow that the sub sets of the set of primes is uncountable.

However, each sub set of the set of primes can be shown to correspond to a unique natural number -- the product of the subsets elements. For, each natural number has a unique prime factorization.

If the sub-sets of the set of primes can be put in a 1-to-1 matching with a a set of numbers that are all natural, clearly this set of numbers that are natural can be put in a 1-to-1 matching with the set of natural numbers, indicating that the subsets of the set of primes are countable

So are the subsets of the set of primes countable or not?

2. Mar 27, 2010

Hurkyl

Staff Emeritus
Re: Subsets of the set of primes -- uncountable or countable??

• The empty subset
• The set of all primes
What natural number do these correspond to?

3. Mar 27, 2010

awkward

Re: Subsets of the set of primes -- uncountable or countable??

That's only true for finite numbers of primes. What if you have an infinite subset?

The finite subsets of the natural numbers are countable. So are the finite subsets of the primes.

4. Oct 3, 2011

BingJing

Re: Subsets of the set of primes -- uncountable or countable??

I have the same claim as you. But I think that the proof of "The primes are countable" is not strict enough.
I still want to find someone strike the "mapping by elements' product" claim.

5. Oct 3, 2011

Deveno

Re: Subsets of the set of primes -- uncountable or countable??

if the prime numbers can be bijectively mapped to the natural numbers, we can use this bijection to create another bijection between the set of all subsets of the prime numbers, and the set of all subsets of the natural numbers:

if A is a subset of the natural numbers, and p_k is the k-th prime, send:

A <----> f(A) = { p_k : k in A}.

i lol'd so hard when i read this. "an infinite set of prime numbers" does NOT mean a set of "infinite prime numbers", no? let me know when you have found the unique natural number corresponding to the set of every other prime number, because i'd like the extra cash....