Para probar que el conjunto de primos es numerable.
Sea P el conjunto de los primos y N el de numeros naturales.
Se sabe que N es numerable. Se sabe que todo subconjunto de N es finito o bien infinito numerable. Se sabe que P no es finito (lo cual se prueba con elementos basicos de teoria de numeros). Entonces solo puede ser infinito numerable.
Si lo que interesa es escribir de forma explícita una función biyectiva entre P y N, se puede proceder de esta manera:
En todo momento se debe utilizar el principio de buena ordenacion de los numeros naturales, que dice así: dado un conjunto A no vacío de numeros naturales, existe un elemento \( a \) que es minimo en A, o sea, es menor o igual que todo otro elemento de A.
En consecuencia, por ser P un subconjunto de N, existe un elemento minimo (que obviamente es el primo 2) que denotamos con \( p_1 \).
Supongamos ahora definidos los elementos \( p_1,...,p_k \), para algun k entero positivo dado.
Como el conjunto P de primos es infinito, el subconjunto de P formado por aquellos elementos distintos de \( p_1,...,p_k \) es infinito, y en particular es no vacio. Como es no vacio, existe un elemento minimo en el, que denotamos \( p_{k+1} \).
De esta manera hemos dado una ley de recurrencia que define el k-esimo primo para cada k natural.
Pero parece claro que la funcion que a cada k le asigna el primo \( p_k \) es biyectiva, y es la funcion buscada.
Lo primero que debe hacerse es verificar que la recurrencia esta bien construida. Cada una de las conclusiones siguientes debe demostrarse usando induccion en el indice k.
* Para cada k, \( p_k \) esta bien definido, porque \( p_1,...,p_k \) es una lista finita de numeros primos, y su complemento respecto a P es no vacio, permitiendo elegir algun elemento de alli.
* Como el elemento elegido en el paso k-esimo es siempre el minimo de los RESTANTES, se ve que \( p_1,...,p_k \) es siempre menor que \( p_{k+1} \).
* Por lo tanto \( p_k \) es una sucesion estrictamente creciente.
* Esto ultimo nos dice que la aplicacion \( k\rightarrow p_k \) es inyectiva.
* Para ver que es sobreyectiva, supongamos que no lo es y lleguemos a un absurdo. Sea p un primo que no esta en la sucesion antes definida \( p_k \).
Spoiler
Denotamos con Q al conjunto de todos los elementos de la sucesion \( p_k \). Entonces estamos suponiendo que p no pertenece a Q.
Sabemos que Q debe ser infinito, porque \( k\rightarrow p_k \) es una aplicacion inyectiva. O sea, es una BIYECCION entre N y Q.
De manera que p debe ser menor que alguno de los elementos de Q, porque si fuera mayor o igual que todos ellos, Q no podria tener mas que p elementos, o sea, Q seria finito, lo cual no es cierto.
En otras palabras, existe un elemento q en Q que es mayor que p. Usando el principio del minimo en N, podemos elegir el minimo elemento q con esa propiedad. Denotamos con h al indice tal que \( q=p_h \)
Ahora bien. Si no hubiese elementos en Q menores esrictamente que p, significaria que p, en particular, es menor que \( p_1 \).
Pero p es primo, y es menor que \( p_1 \), que habiamos elegido como el minimo de los primos, lo cual resulta absurdo.
Asi que p debe ser mayor o igual que alguno de los elementos r de Q.
Como \( q=p_h \) y la sucesion \( p_k \) es creciente, esto nos dice que los elementos r en Q, que son menores o iguales que p, deben ser de la forma \( r=p_j \), con j<h.
El elemento \( p_{h-1} \) es menor que \( q=p_h \), y como q es el minimo de los elementos de Q mayores que p, resulta que \( p_{h-1}\leq p \).
Ahora bien, si p fuese estrictamente mayor que \( p_{h-1} \), por definicion, el numero \( p_h \) deberia ser menor o igual que p, porque p esta entre los candidatos posibles de aquellos primos mayores que \( p_1,...,p_{h-1} \).
Pero habiamos supuesto que p era menor que \( p_h \), contradiccion.
Esto parecera engorroso, pero si tratas de hacerlo por ti mismo veras que la logica es facil intuitivamente, y lo complicado es expresarlo con la debida precision en lenguaje logico.
Para ver que la union numerable de conjuntos numerables es numerable... conviene el procedimiento descrito por numerarius.
Sin embargo puede que la cosa se complique si algunos de los conjuntos son finitos, o si tienen elementos repetidos.
Lo que yo haria, para trabajar de forma ordenada, es separar en dos partes, por un lado aquellos conjuntos que son finitos, y por otra parte aquellos que son infinitos.
La union finita de conjuntos finitos es finita, y eso no ofrece dificultad (si alguno quiere detalles que los pida).
La union numerable de conjuntos finitos es finita o numerable.
Para verlo, denotemos con \( F_n \) a la sucesion de conjuntos finitos, que supondremos no vacios.
Denotemos con \( c_n \) al cardinal de cada uno de esos conjuntos.
Ahora definimos \( s_n \) como la suma:
\( s_n=c_1+...+c_n \).
Como los conjuntos son no vacios, la sucesion de \( s_n \) crece estrictamente, y dado algun numero natural k, hay algun n para el cual
\( s_n\leq k<s_{n+1} \).
Ahora definimos una funcion f de la siguiente manera.
Sea k un numero natural. Sea n tal que \( s_n\leq k<s_{n+1} \). Ordenamos los elementos de \( F_n \) de menor a mayor, y el que ocupa la posicion j-esima, donde \( j = k-s_n+1 \) es lo que llamamos f(k).
Lo que hemos hecho es ir PEGANDO los conjuntos \( F_n \) uno al lado del otro, SOBRE la lista de los naturales. O sea, los hemos enumerado de esa manera.
Puede ocurrir que algunos elementos se repitan en mas de un \( F_n \), pero esto no importa, ya veremos por que.
La funcion f esta bien definida, porque a cada natural k corresponde un y solo un elemento de los \( F_n \). Ademas, dado un \( F_n \), cada uno de sus elementos tiene preimagen al menos entre \( s_n \) y \( s_{n+1} \).
Asi que f es una aplicacion suryectiva de N es la union de todos los \( F_n \).
Pero esto quiere decir que dicha union es, o bien finita, o bien infinita numerable.
**********************
Ahora veamos el caso de una union numerable de conjuntos infinitos numerables.
Basta realizar en detalle el procedimiento TRIANGULAR descrito por numerarius.
De nuevo la funcion asi construida estara bien definida, y sera suryectiva en la union total.
*****************************