# which is the cardinal of primes?

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$?

-
$\aleph$ is often the notation for a general [well-ordered] cardinal or for the cardinal of the continuum. The cardinality of $\mathbb N$ is denoted $\aleph_0$. – Asaf Karagila Jan 10 '13 at 18:43
There no practical/nice/closed-form/easily-computable formula for the $n-$th prime, but it's easy to program an algorithm for that. Furthermore, any infinite subset of the naturals can be put in bijective correspondence with the naturals. – leonbloy Jan 10 '13 at 18:50
Just because there is no formula for a bijection does not mean there isn't a bijection. The common misunderstanding that a lot of people have is that functions need to have "formulas" or "equations". This is not always the case. Check out the Dirichlet Function. – chharvey Feb 10 '13 at 17:37

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$.

-
@Peter: You must have commented while I was adding exactly that argument. – Brian M. Scott Jan 10 '13 at 18:46
@Peter: There is no need to use the axiom of choice. If you have an injection into a well-ordered set, or a surjection from a well-ordered set, then things can be done constructively from those functions. – Asaf Karagila Jan 10 '13 at 19:43
@AsafKaragila Yes, I realized that later. – Pedro Tamaroff Jan 10 '13 at 19:56

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.

-
Fewer? You mean more. Bigger sum, more summands. – Asaf Karagila Jan 10 '13 at 18:58
@AsafKaragila Absolutely! Thanks for picking that up. – Fly by Night Jan 10 '13 at 19:00
Nice argument. Can this notion of "more" and "less" be somehow formalized? – dtldarek Jan 10 '13 at 19:23
@dtldarek: You can define a "measure" on the natural numbers which assigns $A\subseteq\mathbb N$ the measure $\sum_{n\in A}\frac1n$ (assume $0\notin\mathbb N$ for that matter). I never sat to fully verify this but it seems that most of the axioms of a measure hold here. Then you can really say what's less and what's more. – Asaf Karagila Jan 10 '13 at 20:04
@AsafKaragila But what happens to the sequences $(a_i)$ for which $\sum a_i^{-1}$ diverges? With this measure the primes and the natural numbers are indistinguishable. – Fly by Night Jan 10 '13 at 20:08

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.

-

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$.

-