Bijection between Prime numbers and Natural numbers

We know that if set $S$ is countable then this set and set of all natural numbers are equivalent, which means that there must be some bijection between this two sets $F:S\rightarrow N$.

We know that set of all Prime numbers is countable as well as set of all Natural numbers.
So how to find bijection between Prime numbers and Natural numbers in an easy way?

Solution 1:

Xavier shows a "non-constructive" proof of the fact that $\#\mathbb P=\#\mathbb N$. I will show a constructive one:

Let $F_n=2^{2^n}+1$ be the $n$-th Fermat number. It is proved that Fermat numbers a coprime. Let $P_n$ be the smallest prime number dividing $F_n$. Then $P_n\neq P_m$ if $n\neq m$ (because the Fermat numbers are coprime hence having different primes in thei factorizations).

This means that the map $\mathbb N\to\mathbb P$ given by $n\to P_n$ is injective.

As well, the identity map $\mathbb P\to\mathbb N$ given by $p\to p$ is injective.

Therefore by Cantor-Bernstein theorem, we have $\#\mathbb P=\#\mathbb N$.

Solution 2:

Let $\mathbb{P}$ be the set of all prime numbers.

$\mathbb{P} \subsetneq \mathbb{N}$

Then you need to prove that $\mathbb{P}$ is infinite.

Suppose it is finite.

Let $p = 1 + \prod\limits_{i \in \mathbb{P}} i \in \mathbb{N}$

$\forall k \in \mathbb{P}, k \nmid p$ because otherwise, since $k \mid \prod\limits_{i \in \mathbb{P}} i$, $i \mid p - \prod\limits_{i \in \mathbb{P}} i$, ie $p \mid 1$ which is absurd.

So $p \in \mathbb{P}$. Absurd.

So $\mathbb{P}$ is infinite.

(At this point, you probably can say something like "$\mathbb{P}$ is infinite and in $\mathbb{N}$ hence countably infinite so you can get a bijection from $\mathbb{N}$ to $\mathbb{P}$. But I haven't learned that kind of things yet so I'm not sure...)

Then, since $\mathbb{P} \subset \mathbb{N}$, $\forall X \subset \mathbb{P}, \min( X )$ exists.

Let $X_0 = \mathbb{P}$ and $\forall n \geq 1, X_n = X_{n-1} \setminus \{ \min( X_{n-1}) \}$

Then you can use $\forall n \in \mathbb{N}, f(n)=min(X_n)$.