Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Subsets of the set of primes - uncountable or countable?

  1. Mar 27, 2010 #1
    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.
     
  2. jcsd
  3. Mar 27, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    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?
     
  4. Mar 27, 2010 #3
    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.
     
  5. Oct 3, 2011 #4
    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.
     
  6. Oct 3, 2011 #5

    Deveno

    User Avatar
    Science Advisor

    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....
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook