What is the cardinality of the set of prime numbers?

Question

I know that $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|=\aleph_0$ but which is the cardinal of $|\mathbb{P}|$? since there is no formula for primes, then I can conclude that there is not bijection between $\mathbb{N}$ and $\mathbb{P}$ and so $|\mathbb{P}|\ne\aleph_0$?

Answer 1

Since $\Bbb P\subseteq\Bbb N$ and $\Bbb P$ is infinite, it follows automatically that $|\Bbb P|=|\Bbb N|$: every infinite subset of $\Bbb N$ has the same cardinality as $\Bbb N$.

Suppose that $A\subseteq\Bbb N$ is infinite. Then we can recursively define a bijection $\varphi$ from $\Bbb N$ to $A$ by setting $$\varphi(n)=\min\big(A\setminus\{\varphi(k):k<n\}\big)\;:$$

$\Bbb N$ is well-ordered by $\le$ so $\min S$ is well-defined for any non-empty $S\subseteq\Bbb N$, and the hypothesis that $A$ is infinite ensures that $A\setminus\{\varphi(k):k<n\}\ne\varnothing$ for each $n\in\Bbb N$.

Answer 2

The primes are subset of $\Bbb N$. But they are infinite. Since $\Bbb N$ is well ordered we can define an injection from $\Bbb P$ to $\Bbb N$ as follows. Let $p_1$ be the least element of $\Bbb P$. Let $p_2$ be the least element of $\Bbb P-\{p_1\}$ and in general let $p_{n+1}$ be the least element of $\Bbb P_n=\Bbb P-\{p_1,\dots,p_n\}$. Then $n\mapsto p_n$ is a bijection. This works in the general case that $B$ is an infinite subset of $\Bbb N$.

Answer 3

Theorem: If $f\colon\mathbb N\to A$ is surjective then either $A$ is finite, or $|A|=|\mathbb N|$. Alternatively if $g\colon A\to\mathbb N$ is injective then the same conclusion about $A$ is true.

Theorem: The set of prime numbers is not finite.

Corollary: There are countably many prime numbers.

---

I should also add that there are not many formulas we can write, and there are many subsets to $\mathbb N$. The result is that almost all infinite subsets of $\mathbb N$, while having the same cardinality as $\mathbb N$ do not have a "formulated bijection" between them.

I should add that if we are given the set then we can produce from that set the bijection, but this is already a parameter which we use in the formula.

For such bijection, see If $X$ is an infinite set and there exists an injection $X \to \mathbb{N}$, is there also a bijection?

Answer 4

In short $|\mathbb{P}| = \aleph_0$. There are infinitely many primes, and every prime is an integer. So the primes are a countably infinite set, just like $\mathbb{N}$, $\mathbb{Z}$ and $\mathbb{Q}$. To put them in their place, consider the sum:

$$\sum_{k=1}^{\infty} \frac{1}{k^2} = \frac{\pi^2}{6} \, . $$

However, the sum of reciprocals $1/p$ where $p$ is prime, i.e. $1/2 + 1/3 + 1/5 + 1/7 + 1/11 + \cdots $ actually diverges! So, in some sense, there are "more" primes than there are square numbers. In short: there are "less" primes than there are natural numbers, but "more" primes than there are square numbers.