Bijección entre números primos y números naturales

Question

Sabemos que si se establece $S$ es contable, entonces este conjunto y el conjunto de todos los números naturales son equivalentes, lo que significa que debe haber alguna bijección entre estos dos conjuntos $F:S \rightarrow N$ .

Sabemos que el conjunto de todos los números primos es contable, así como el conjunto de todos los números naturales.
Entonces, ¿cómo encontrar la bijección entre los números primos y los números naturales de una manera fácil?

Answer 1

Dejemos que $\mathbb{P}$ sea el conjunto de todos los números primos.

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

---

Entonces tienes que demostrar que $\mathbb{P}$ es infinito.

Supongamos que es finito.

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

$\forall k \in \mathbb{P}, k \nmid p$ porque de lo contrario, ya que $k \mid \prod\limits_{i \in \mathbb{P}} i$ , $i \mid p - \prod\limits_{i \in \mathbb{P}} i$ , es decir $p \mid 1$ lo cual es absurdo.

Así que $p \in \mathbb{P}$ . Absurdo.

Así que $\mathbb{P}$ es infinito.

(En este punto, probablemente pueda decir algo como " $\mathbb{P}$ es infinito y en $\mathbb{N}$ por lo tanto contablemente infinito por lo que se puede obtener una biyección de $\mathbb{N}$ a $\mathbb{P}$ . Pero aún no he aprendido ese tipo de cosas así que no estoy seguro...)

---

Entonces, como $\mathbb{P} \subset \mathbb{N}$ , $\forall X \subset \mathbb{P}, \min( X )$ existe.

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

Entonces puede utilizar $\forall n \in \mathbb{N}, f(n)=min(X_n)$ .

Answer 2

Xavier muestra una prueba "no constructiva" del hecho de que $\#\mathbb P=\#\mathbb N$ . Voy a mostrar una constructiva:

Dejemos que $F_n=2^{2^n}+1$ sea el $n$ - número de Fermat. Se ha demostrado que los números de Fermat son coprimos. Sea $P_n$ sea el menor número primo que divide a $F_n$ . Entonces $P_n\neq P_m$ si $n\neq m$ (porque los números de Fermat son coprimos y por lo tanto tienen diferentes primos en sus factorizaciones).

Esto significa que el mapa $\mathbb N\to\mathbb P$ dado por $n\to P_n$ es inyectiva.

Además, el mapa de identidad $\mathbb P\to\mathbb N$ dado por $p\to p$ es inyectiva.

Por lo tanto, por el teorema de Cantor-Bernstein, tenemos $\#\mathbb P=\#\mathbb N$ .