I want to know the cardinality of the set of prime numbers. Is it aleph not? The cardinality of natural numbers and all countably infinite sets? But, how can we make a mapping of the set of prime numbers with the set of natural numbers? Is there such a mapping to impose the same cardinality on the set of primes as that of natural numbers?

  • $\begingroup$ See this question $\endgroup$ – lulu Feb 27 '20 at 11:34
  • 3
    $\begingroup$ The mapping you're looking for is simply an enumeration of the prime numbers, for instance the one sending 1 to 2, 2 to 3, 3 to 5, and so on. $\endgroup$ – Ben Steffan Feb 27 '20 at 11:36
  • 3
    $\begingroup$ Welcome to Mathematics Stack Exchange. Did you mean aleph naught? $\endgroup$ – J. W. Tanner Feb 27 '20 at 12:09
  • 1
    $\begingroup$ I will point out that the function described by BenSteffan certainly exists. That it is difficult to compute is irrelevant. It doesn't bother us that we have a difficult time saying within a short amount of time what the four-billionth prime number is. It is obvious that there is a four-billionth prime number (and indeed an $n$'th prime number for any finite $n$) and that is all that we needed to convince ourselves of in regards to the validity of the existence of the described function. $\endgroup$ – JMoravitz Feb 27 '20 at 14:15

Any infinite subset $A$ of the natural numbers $\Bbb N$ must have cardinality $\aleph_0$: being infinite implies there is an injection $\Bbb N\to A$, and since $A$ is a subset of $\Bbb N$, the identity map forms an injection $A\to \Bbb N$.

By the Cantor-Schröder-Bernstein theorem it follows that $|A|=|\Bbb N|=\aleph_0$.

In fact, you can make the above even stronger: any subset of the rational numbers, algebraic numbers or even computable numbers is countable, since each of those sets is countable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.