El producto cartesiano $\mathbb{N} \times \mathbb{N}$ es contable

Question

Estoy examinando una prueba que he leído que pretende demostrar que el producto cartesiano $\mathbb{N} \times \mathbb{N}$ es contable, y como parte de esta prueba, estoy tratando de demostrar que el mapa dado es suryectiva (de hecho biyectiva), pero me temo que no puedo ver por qué este es el caso. Me pregunto si podría indicarme la dirección correcta.

De hecho, la prueba comienza así:

"Para cada $n \in \mathbb{N}$ , dejemos que $k_n, l_n$ sea tal que $n = 2^{k_n - 1} \left(2l_n - 1 \right)$ Eso es, $k_n - 1$ es la potencia de $2$ en la factorización prima de $n$ y $2 l_n - 1$ es el número (necesariamente impar) $\frac{n}{2^{k_n - 1}}$ ."

A continuación afirma que $n \mapsto \left(k_n , l_n \right)$ es una suryección de $\mathbb{N}$ a $\mathbb{N} \times \mathbb{N}$ y así termina la prueba.

Puedo ver intuitivamente por qué esto debería ser una biyección, creo, pero no estoy seguro de cómo hacer que estos sentimientos rigurosos?

Supongo que diría que el mapa es suryectivo ya que dado cualquier $\left(k_n , l_n \right) \in \mathbb{N} \times \mathbb{N}$ podemos simplemente tomar $n$ sea igual a $2^{k_n - 1} \left(2l_n - 1 \right)$ y observe que $k_n - 1 \geq 0$ y así $2^{k_n - 1}$ es a la vez mayor o igual que uno por lo que es un número natural (haciendo el argumento inductivo obvio, observando que la multiplicación en $\mathbb{N}$ es cerrado), y de forma similar que $2 l_n - 1 \geq 2\cdot 1 - 1 = 1$ y también es un número natural, y por tanto el producto de estos dos, $n$ también debe ser un número natural. ¿Es tan sencillo como esto?

Supongo que mi intuición al probar que el mapa es inyectivo sería suponer que $2^{k_n - 1} \left(2 l_n - 1 \right) = 2^{k_m - 1} \left(2 l_m - 1 \right)$ y luego utilizar el Teorema Fundamental de la Aritmética para concluir que $n = m$ . ¿Va esto por buen camino? La definición "implícita" de la cartografía me tiene un poco confundido sobre el enfoque.

---

En una nota relacionada, pero separada, soy de hecho consciente de que si $K$ y $L$ son cualesquiera conjuntos contables, entonces también lo son $K \times L$ por lo que trivialmente, tomando el mapa identidad vemos trivialmente que este mapa es biyectivo y por tanto que $\mathbb{N}$ es ciertamente contable (¡!), y por tanto también lo es $\mathbb{N} \times \mathbb{N}$ . Por lo tanto, no es realmente el enunciado lo que me interesa, sino la emocionante excursión a la teoría de números que proporciona la prueba alternativa anterior.

Answer 1

Su intuición es correcta. Utilizamos el teorema fundamental de la aritmética, es decir, la factorización de primos es única (hasta el orden, por supuesto).

Primero demostramos la inyectabilidad:

Supongamos que $(k_n,l_n),(k_m,l_m)\in\mathbb N\times\mathbb N$ y $2^{k_n - 1} (2 l_n - 1 ) = 2^{k_m - 1} (2 l_m - 1)$ .

$2$ es un número primo y $2t-1$ es impar para todos $t$ y así tenemos que el poder de $2$ es el mismo en ambos lados de la ecuación, y es exactamente $k_n=k_m$ .

Dividir por $2^{k_n}$ y por lo tanto $2l_n-1 = 2l_m-1$ Añadir $1$ y dividir por $2$ Así que $(k_n,l_n)=(k_m,l_m)$ y por lo tanto este mapeo es inyectivo.

La subjetividad es aún más simple, tome $(k,l)\in\mathbb N\times\mathbb N$ y que $n=2^{k-1}(2l-1)$ . Ahora $n\mapsto(k,l)$ porque $2l-1$ es impar, por lo que los poderes de $2$ en la descomposición primaria de $n$ son exactamente $k-1$ y a partir de ahí $l$ está decidido a ser nuestro $l$ . (Si te fijas bien, es exactamente el mismo argumento de la inyectividad sólo que aplicado "al revés", que es un rasgo que tienen muchas de las pruebas de este tipo)

---

En cuanto a pruebas más sencillas, hay infinitas... a partir de la función de emparejamiento de Cantor ( $(n,m)\mapsto\frac{(n+m)(n+m+1)}{2}+n$ ), a los argumentos de Cantor-Bernstein mediante $(n,m)\mapsto 2^n3^m$ y $k\mapsto (k,k)$ para las funciones inyectivas. Sin embargo, me gusta esta función. Intentaré recordarla y utilizarla la próxima vez que enseñe a alguien una prueba de este tipo.

Answer 2

Es posible que la notación esté impidiendo ver lo que ocurre.

Cada positivo entero $n$ es una potencia de $2$ veces un número impar. (Tenga en cuenta que $2^0$ es una potencia de $2$ .)

Por ejemplo, $840=2^3 \times 105$ y $747=2^0 \times 747$ .

En símbolos, $$n=2^e \times a$$ donde $e$ es un número entero no negativo, y $a$ es un número entero positivo impar.

Además, la representación anterior es única: Si conocemos $e$ y $a$ sabemos $n$ y si sabemos $n$ sabemos $e$ y $a$ .

Desde $a$ es impar, es de la forma $2b+1$ donde $b$ es un número entero no negativo. Como $a$ abarca los enteros positivos Impares, $b$ abarca los números enteros no negativos.

Sea $f$ sea la función que toma $n$ al par ordenado $(e,b)$ . Por ejemplo $840=2^3 \times 105$ tenemos $f(840)=(3,52)$ . Del mismo modo, $f(747)=(0,373)$ .

Sea $\mathbb{N}_0$ sea el conjunto de enteros no negativos. Entonces $f$ es un mapa biyectivo de $\mathbb{N}$ a $\mathbb{N}_0 \times \mathbb{N}_0$ . Esto es una consecuencia inmediata del hecho de que si conocemos $e$ y $b$ sabemos $n$ y a la inversa, si sabemos $n$ sabemos $e$ y $b$ .

No es exactamente lo que busca, pero se le acerca mucho. Y fácil de arreglar, ya que $\mathbb{N}$ es sólo $\mathbb{N}_0$ impulsado por $1$ .

Todo lo que tenemos que hacer es asignar $n$ a $(e+1, b+1)$ .

Answer 3

Para una prueba rápida, ¿por qué no tomar un par de primos, como, por ejemplo , 2 y 3, a continuación, inyectar un par (a,b) inf: $\mathbb N \times \mathbb N$ a $2^a3^b$ y, para la dirección opuesta, inyectar n en $\mathbb N$ en $\mathbb N\times \mathbb N$ por $n\rightarrow(n,0)$ y luego usar a Rick Schroder-Bernstein. Parece claro que si f(a,b)=f(a',b'), por lo que $2^a3^b=2^{a'}3^{b'}$ entonces $2^{a-a'}3^{b-b'}=1$ forzando a=a' y b=b'(alternativamente, si $2^x3^y=1$ entonces ambos $2^x$ y $3^y$ debe dividir a 1, de modo que x=y=0, y se sigue la inyectabilidad); OTOH, si (n,0)=(n',0) , entonces claramente n=n'

EDIT: Los mapas de Cantor-Schroeder-Bernstein pueden extenderse (unívocamente) en biyecciones.

Answer 4

En la pregunta del OP escribe

es una suryección de $\mathbb{N}$ a $\mathbb{N} \times \mathbb{N}$ y así termina la prueba

Eso es un poco divertido ya que la subjetividad es todo lo que se necesita - la imagen de cualquier enumeración es un conjunto finito o contablemente infinito .

El PO también afirma

Por lo tanto, no es realmente el enunciado lo que me interesa, sino más bien la emocionante excursión a la teoría de números que proporciona la prueba alternativa anterior.

Así que para otra excursión "emocionante" (o quizá sólo humorística, rozando la tontería), preguntamos,

¿Cuál es la cantidad mínima de teoría de números necesaria para construir una enumeración suryectiva de
$\mathbb{N}$ en $\mathbb{N} \times \mathbb{N}$ ?

Sea $T = \{\,(2^j3^k,m) \, | \, j,k \in \Bbb N_0 \land m \in \Bbb N\}$ .

Tenemos un mapeo inyectivo $f$ de $\mathbb{N}$ en $T$ definido por

$\quad m \mapsto (2^0 3^0, m)$

Podemos definir una relación de equivalencia $\sim$ en $T$ ,

$\quad (2^j 3^k, m) \sim (2^\bar j 3^\bar k, \bar m) \; \text{ if } 2^j 3^k m = 2^\bar j 3^\bar k \bar m $ .

Tenemos el mapa cociente $\rho$ definido por $\sim$ ,

$\quad \rho: T \mapsto \frac{T}{\sim}$

Cualquier elemento de la imagen de $\rho$ puede representarse mediante un par ordenado $(2^j 3^k, m)$ con $m$ mínimo. Demostrar que estos representantes deben ser únicos se reduce a demostrar que

$\tag 1 \text{If } 2^s = 3^t \text{ Then } s = 0 \land t = 0$

Por tanto, podemos definir una correspondencia $g$ del cociente a $\mathbb{N} \times \mathbb{N}$ tomando el representante único $(2^j 3^k, m)$ de un bloque y asignarlo a $(j,k)$ .

Siempre es cierto que $(2^0 3^0, 2^j 3^k) \sim (2^j 3^k, 1)$ .

Sumando todo esto vemos que el mapeo $g \circ \rho \circ f$ es una suryección.

Así que $\text{(1)}$ es la única teoría de números que se necesita aquí.