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}|$ ?
Best Answer
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.