Subsets of the set of primes - uncountable or countable?

  • #1

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?

Thanks for reading.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19


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?
 
  • #3
329
0


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.
 
  • #4
1
0


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
Deveno
Science Advisor
906
6


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

Related Threads on Subsets of the set of primes - uncountable or countable?

Replies
11
Views
9K
  • Last Post
Replies
4
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
3
Views
4K
Replies
25
Views
12K
Replies
13
Views
4K
Replies
8
Views
14K
  • Last Post
Replies
7
Views
8K
  • Last Post
Replies
6
Views
2K
Top