Subsets of the set of primes - uncountable or countable?

In summary, the conversation discusses Cantor's proof that the subsets of natural numbers are uncountable and the question of whether the subsets of prime numbers are countable or not. It is argued that if the set of primes can be put in a 1-to-1 matching with the natural numbers, then the subsets of primes are uncountable. However, it is also pointed out that each subset of primes corresponds to a unique natural number through the product of its elements. The conversation ends with a discussion on creating a bijection between the set of subsets of primes and the set of subsets of natural numbers. The summary concludes with a humorous comment about finding a unique natural number for an infinite set of prime numbers.
  • #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.
 
Physics news on Phys.org
  • #2


realitybugll said:
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


realitybugll said:
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


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


realitybugll said:
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...
 

1. What are subsets of the set of primes?

Subsets of the set of primes are smaller groups of prime numbers that are contained within the larger set of primes. These subsets can be formed by selecting specific prime numbers or by using mathematical operations on the original set.

2. How do you determine if a subset of the set of primes is countable or uncountable?

A subset of the set of primes is considered countable if its elements can be put in a one-to-one correspondence with the natural numbers (1, 2, 3, etc.). This means that each element in the subset has a unique index number and can be counted. If the subset cannot be put in a one-to-one correspondence with the natural numbers, it is considered uncountable.

3. Are all subsets of the set of primes uncountable?

No, not all subsets of the set of primes are uncountable. Some subsets, such as the subset of prime numbers less than 10, can be put in a one-to-one correspondence with the natural numbers and are considered countable.

4. What is the significance of the set of primes being uncountable?

The uncountable nature of the set of primes has significant implications in mathematics. It means that there are infinitely many prime numbers and they cannot be listed or counted in a finite amount of time. This also has applications in number theory, cryptography, and other areas of mathematics.

5. Can the set of primes be partitioned into countably infinite subsets?

Yes, the set of primes can be partitioned into countably infinite subsets. This means that the set of primes can be divided into smaller groups, each of which is countable. For example, the set of prime numbers can be partitioned into subsets based on their last digit (e.g. all primes ending in 1, 3, 7, or 9). Each of these subsets is countable, but the entire set of primes is still uncountable.

Suggested for: Subsets of the set of primes - uncountable or countable?

Replies
1
Views
1K
Replies
6
Views
884
Replies
1
Views
685
Replies
1
Views
1K
Replies
9
Views
1K
Back
Top