Subsets of the set of primes - uncountable or countable?

[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?

Thanks for reading.

 

[Hurkyl]

However, each sub set of the set of primes can be shown to correspond to a unique natural number

Really? Could you demonstrate? Let's start with the simplest subsets:

• The empty subset
• The set of all primes

What natural number do these correspond to?

 

[awkward]

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.

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.

 

[BingJing]

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.

 

[Deveno]

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?

Thanks for reading.

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...