3.9. Set of Prime Numbers

A number p is prime provided it is divisible by only 1 and p; that means there are no other divisors for the number p apart from the number 1 and the number p. Of course 1 divides any number. And the number divides itself by default these are the 2 valid divisors of any number. If your number p is such that you do not have any other divisors other than the number itself and 1 then the number p will be called as the prime number. So if you take say 2, 3, 5, 7 they are all prime numbers. Whereas if you take the numbers like 4, 9, 15 they are not prime numbers because divisors of 4 are 2, divisors of 9 are 3, divisors of 15 are 3 and 5 and so on.

A prime number is defined based on its divisibility properties. Specifically, a prime number can only be evenly divided by 1 and itself. This means that there are no other numbers that can divide a prime number without leaving a remainder. Examples of prime numbers include 2 (which is divisible by 1 and 2 only), 3, 5, and 7. In contrast, numbers like 4, 9, and 15 are not prime because they have divisors other than 1 and themselves. For example, 4 can be divided by 2, 9 by 3, and 15 by both 3 and 5.

Think of prime numbers like a unique club where only two members are allowed: the number itself and the number 1. If you have a group (number), and you find that it can be broken down into smaller members (divisors) apart from its unique club members (1 and itself), then it's not part of the prime club. For example, if you take the number 7, it has no members other than 1 and 7, making it a prime number. But number 10 has 2 and 5 as extra members, thus it's not prime.

My claim is that a set of prime numbers is a countable set. So again those who are not familiar with number theory they might be knowing that there are infinite numbers of prime numbers. But what we are starting in this theorem is that cardinality wise the number of prime numbers, the cardinality of the set of prime numbers is same as the cardinality of the set of positive integers. So this I can either prove by giving you a valid sequence and the sequence is very straight forward. You just enumerate the prime numbers in increasing order that is all and it is a valid sequence because this is an infinite sequence; that is fine.

The concept here is that although there are infinitely many prime numbers, they still form a countable set. This means that we can arrange all the prime numbers in a sequence, listing them one after the other (like 2, 3, 5, 7, 11, 13,...). This sequence continues indefinitely, which confirms that every prime number can be reached by counting in this manner. By establishing this sequence, we show that the primes have the same 'number of elements' as the set of positive integers, in terms of cardinality.

Imagine counting the different types of candies in a huge candy store. Even though there are countless types (like prime numbers), you can keep adding each type to your list as you find them (like 2, 3, 5, 7, etc.). Just as you can eventually list every single type of candy, you can list every prime number in order—proving that though they are many, they are still countable like a manageable list.

But it is valid in the sense that every number in this sequence is a prime number, no number is going to be repeated and you take any element y belonging to the set of prime numbers it will eventually appear in this sequence. It will not be the case that you do not know where exactly; it is not the case that this number y will never appear in this sequence.

A bijection is a specific type of relationship between two sets, where each element from one set corresponds with exactly one element from another set. In this case, if we define a function that takes a positive integer n and gives us the nth prime number, we create a direct link between positive integers and prime numbers. This relationship shows that both sets (the set of primes and the set of positive integers) have the same number of elements — they can be paired one-to-one without any left out or repeated.

Think about a pair of shoes: for each foot (left and right), there’s a matching shoe. Similarly, each positive integer can be paired with a prime number (1 with the first prime 2, 2 with the second prime 3, etc.). There’s exactly one prime for every positive integer in your counting sequence, just like there’s a match for every foot, showing that the worlds of prime numbers and positive integers are closely linked.

So now what we have proved till now? We have proved will now that the set of prime number, it has the same number of elements as the set of odd positive integers which has the same number of elements as the set of positive integers. That means even though element wise they are different but cardinality wise they are same.

In conclusion, we have shown that the set of prime numbers can be counted just like the positive integers. Despite being distinct sets with different elements (primes are specific numbers like 2, 3, and so on), they share an important characteristic in mathematics — they have the same cardinality. This means that no matter how many primes you name, they can always be matched one-to-one with the counting numbers (1, 2, 3,...), confirming that they are indeed a countable infinity.

Let’s go back to our previous example of candies. Just as you can categorize all types of candies and still find a correlation to the overall count (where every candy type corresponds with a number in your list), prime numbers also relate in a similar way to natural numbers. Even though they are unique in flavor (or character), their overall amount can be reflected in your counting, showcasing their countable nature.

--