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$
$\endgroup$
4
-
$\begingroup$ See this question $\endgroup$– luluCommented Feb 27, 2020 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 SteffanCommented Feb 27, 2020 at 11:36
-
3$\begingroup$ Welcome to Mathematics Stack Exchange. Did you mean aleph naught? $\endgroup$– J. W. TannerCommented Feb 27, 2020 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$– JMoravitzCommented Feb 27, 2020 at 14:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
