Cardinality of the set of prime numbers

It was proved by Euclid that there are infinitely many primes. But what is the cardinality of the set of prime numbers ?

Cantor showed that the sets $\mathbb{Q}$ and $\mathbb{Z}$ have the same cardinality as the natural numbers $\mathbb{N}$ by constructing a pairing of the two sets, or a bijective function $ \pi_{\mathbb{Z}} : \mathbb{N} \rightarrow \mathbb{Z}$ and $ \pi_{\mathbb{Q}} : \mathbb{N} \rightarrow \mathbb{Q}$.

Let $\mathbb{P}$ denote the set of prime numbers. Is it possible to construct such a pairing function, $ \pi_{\mathbb{P}} : \mathbb{N} \rightarrow \mathbb{P}$ ?

It's clear that $|\mathbb{P}| \leq |\mathbb{N}| = \aleph_0$ since $\mathbb{P} \subset \mathbb{N}$. Is it possible to show that $|\mathbb{P}| \geq |\mathbb{N}|$, or do we have $|\mathbb{P}| < |\mathbb{N}|$ ?

Solution 1:

It is not hard to show that every infinite subset of $\Bbb N$ is in fact of cardinality $\aleph_0$. Let $A$ be such set, and define the following function: $$f(a)=\big|\{n\in A\mid n<a\}\big|.$$

It's not very hard to see that this is a bijection between $A$ and $\Bbb N$.

So we have that the cardinality of $\Bbb P$ is $\aleph_0$ just as well.

Another point worth mentioning is that if $|A|<\aleph_0$ then by definition $A$ is finite (because $\aleph_0$ is a minimal cardinal above the finite cardinals), so if $\Bbb P$ has cardinality smaller than $\aleph_0$ it is finite, in contradiction to all those proofs given that it's not.

Solution 2:

Since $\Bbb P \subset \Bbb N$, we have a natural ordering inherited on $\Bbb P$. Since it is a subset of a well-ordering, the induced ordering is again a well-ordering.

Thus we have that $(\Bbb P, <)$ is an infinite well-ordering; it is clear that it contains no limits.

Therefore, the order-type of $(\Bbb P, <)$ must be $\omega$, meaning that it can be put in direct bijective correspondence with $\Bbb N$.

Effectively, this proof (which hinges on the theorem "every well-ordering is order-isomorphic to a unique ordinal") gives a bijection by the following recursive definition:

$$f: \Bbb N \to \Bbb P: f(n) := \begin{cases}\inf \Bbb P &: n = 0\\\inf(\Bbb P \setminus\{f(1)\ldots f(m)\}) &: n = m+1\end{cases}$$

That is, "$f(n)$ is the $n+1$st smallest prime number".

Solution 3:

$\aleph_0$ is the smallest infinite cardinal. Therefore, since $\mathbb{P}$ is infinite, $|\mathbb{P}| \geq \aleph_0$. Finally, $|\mathbb{P}|= \aleph_0$.