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

## Main Question or Discussion Point

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?

Related Set Theory, Logic, Probability, Statistics News on Phys.org
Hurkyl
Staff Emeritus
Gold Member

However, each sub set of the set of primes can be shown to correspond to a unique natural number
• The empty subset
• The set of all primes
What natural number do these correspond to?

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.

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?