¿Por qué esta prueba de $\mathbb{N}\times\mathbb{N}$ ¿que sea contable y no formal?

Question

Mi copia de Introducción al Análisis Real: Bartle y Sherbert da:

Teorema: El conjunto $\mathbb{N}\times\mathbb{N}$ es contable.

Prueba informal: Recordemos que $\mathbb{N}\times\mathbb{N}$ consiste en todos los pares ordenados $(m,n)$ , donde $m,n \in \mathbb{N}$ . Podemos enumerar estos pares como:

$(1,1), \text{ } (1,2),\text{ } (2,1), \text{ }(1,3), \text{ }(2,2), \text{ }(3,1), \text{ }(1,4) \text{ }...$ según la suma creciente $m+n$ y el aumento de $m$ $...$

Obsérvese que si bien este argumento es satisfactorio en el sentido de que muestra exactamente lo que la biyección de $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ debería hacer, no es una "prueba formal", ya que no define esta biyección con precisión.

Mi problema es entender dónde se pierde la formalidad, la prueba que se da en el apéndice es larga y da un poco de miedo. ¿Alguien puede decir en qué sentido es informal?

Answer 1

Examinemos lo que dice el libro: Para demostrar que $\mathbb N\times\mathbb N$ es contable, necesitamos exhibir una biyección desde $\mathbb N\times \mathbb N$ en $\mathbb N$ .

Los autores del libro describen la biyección diciendo: Enumerar los pares $(m,n)$ según la suma creciente $m+n$ y, para cada fijo $m+n$ según el aumento de $m$ .

[Sólo por diversión, vamos a enumerar algunas de las parejas en orden: Desde $m,n\in\mathbb N$ entonces $m+n\ge2$ por lo que el primer valor de $m+n$ es $2$ . Sólo hay un par $(m,n)$ con esa suma, es decir $(1,1)$ . El siguiente valor posible para $m+n$ es $3$ . La ecuación $m+n=3$ tiene dos soluciones en los números naturales, a saber $m=2,n=1$ y $m=1,n=2$ . La descripción nos dice que primero hacemos una lista $(1,2)$ y luego $(2,1)$ . El siguiente valor es $m+n=4$ y los pares de soluciones se enumeran como $(1,3),(2,2),(3,1)$ . Les seguirán $(1,4),(2,3),(3,2),(4,1)$ en ese orden. etc. Así comienza la lista: $$(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),(2,3),(3,2),(4,1),(1,5),\dots$$ Por ejemplo, esto significa que si $f$ es la función que hemos descrito, entonces $f(2,1)=3$ y si $f(a,b)=10$ entonces $(a,b)=(4,1)$ .]

¿Asigna esto un número natural como valor a cada par $(m,n)$ de los números naturales? Sí.

(De hecho, hay un algoritmo fácil que nos permite encontrar ese valor, aunque eso es irrelevante: El algoritmo en sí no es muy imaginativo: Basta con ir enumerando primero los pares con suma $2$ , entonces los que tienen suma $3$ , entonces los que tienen suma $4$ y así sucesivamente, hasta $(m,n)$ está en la lista, y luego cuenta los elementos que han sido listados hasta ahora para encontrar en qué parte de la lista $(m,n)$ aparece, y ese es el número que se le asigna).

¿Esta asignación es inequívoca? Sí.

Por supuesto. La descripción es inequívoca, no hay ningún margen de maniobra para elaborar la lista. Así que, hasta ahora, sabemos que tenemos un función con dominio todo $\mathbb N\times\mathbb N$ y el rango en $\mathbb N$ .

[Podemos decir más si es necesario, pero creo que esto es sólo desorden en algún momento: Para cada número natural fijo $k$ sólo hay un número finito de pares $(m,n)$ avec $m+n=k$ . De hecho, podemos identificarlas todas, ya que $m+n=k$ implica que $m\le k$ Así que $m$ es uno de $1,2,\dots,k-1,k$ y para cada una de estas opciones hay un valor único de $n$ que funciona, es decir $n=k-m$ . ¿Qué nos aporta eso? Bueno, dado cualquier par $(m,n)$ si definimos $k$ por $k:=m+n$ sólo hay un número finito de pares $(a,b)$ avec $a+b\le k$ por lo que podemos enumerarlas en una lista finita, en el orden descrito -- primer orden por el tamaño de $a+b$ y entre los que tienen el mismo $a+b$ , ordenados por el tamaño de $a$ -- para que efectivamente asignemos a $(m,n)$ un número, porque las uniones finitas de conjuntos finitos son finitas (o, más bien, en nuestro caso, la concatenación de listas finitas sigue siendo una lista finita), y este número está bien definido. Si se nos presiona, podríamos elaborar una fórmula para saber qué número es el que asignamos a $(m,n)$ pero, de nuevo, no es necesario].

Si un número natural $n$ se asigna a un par $(a,b)$ ¿es este el único par que $n$ se asigna a? Obviamente.

Cualquier lista con al menos $n$ sólo tiene un elemento en el $n$ posición. Esto significa que la función que tenemos es inyectiva.

¿Es el rango de esta función un segmento inicial de $\mathbb N$ ? Sí.

Al fin y al cabo, estamos enumerando los números. Esto significa que no estamos omitiendo ningún valor. Si $f(a,b)=20$ , entonces la lista tiene asignados los números $1,2,\dots,19$ a otros pares $(m,n)$ también.

¿Es el rango todo de $\mathbb N$ ? Sí.

Obvio: Para cualquier $k$ según la descripción de la lista, los pares $(1,1),(2,2),\dots,(k,k)$ se enumeran en ese orden, con posiblemente muchos otros números interpolados entre ellos. Así que la lista de números tiene una longitud de al menos $k$ , por lo que a algún par se le ha asignado el número $k$ . Ahora hemos demostrado que la función que tenemos también es suryectiva.

Eso es, esa es la prueba. ¿Se puede ampliar? Por supuesto. Podemos añadir muchas cosas, pero parece totalmente innecesario. Mi punto aquí es que, como explicaciones van, realmente no hay mucho que decir. La biyección fue de hecho inequívoca y definidos con precisión (a pesar de lo que dicen los autores).

El boceto del libro no es una prueba completa: No argumenta que esta descripción nos da efectivamente una función, que su dominio es todo $\mathbb N\times\mathbb N$ que la función es inyectiva, su rango es un segmento inicial de $\mathbb N$ y, de hecho, que este segmento inicial es todo $\mathbb N$ . Esos son todos los detalles que necesitábamos verificar para comprobar que teníamos una biyección. Pero, tal y como van estas cosas, en realidad no nos faltaban muchos detalles.

Un consejo: Lee los detalles de la prueba en el libro, aunque sea "largo y un poco aterrador". Aunque sólo sea por curiosidad. Si el libro no dice más que lo que digo arriba, al final vemos que no había mucho que temer. Si el libro entra en detalles adicionales, al final puede que sepamos aún más sobre esta bijección, y la entendamos mejor. Tal vez el libro amplíe con gran detalle algunos de los puntos que he calificado esencialmente de triviales en este escrito, y tal vez en el contexto del libro tenga sentido que estos detalles sean necesarios, y no tan triviales como yo creo. (Pero si este es el caso, sólo tendrá sentido si estás familiarizado con el libro, y con lo que los autores se permiten asumir a través de él. No será algo que se pueda discernir sólo leyendo los detalles de ese apéndice).

O tal vez vea que los autores se preocupan innecesariamente, lo que bien puede ser el caso. Sea cual sea el resultado, parece que saldrás ganando con la experiencia. Como puedes ver en los comentarios y en las muchas respuestas, no es que haya un consenso universal entre los matemáticos sobre lo que nos permitimos asumir (incluso dependiendo del público). Eso siempre es interesante de experimentar, creo que hace que las matemáticas se sientan más reales y vivas, lo que siempre es bueno de realizar.

Answer 2

Dicen precisamente por qué: "no define esta biyección con precisión". Cualquier cosa que suponga que entiendes lo que quiere decir no va a ser formal.

Recomiendo que se intente definir con precisión. Hágame saber si necesita ayuda.

También hay biyecciones mucho más fáciles: $2^{n-1}(2m-1)$ nos da una biyección (suponiendo que $\mathbb{N}$ no contiene $0$ (lo que se desprende del extracto que has dado).

Answer 3

Defina una función f: N -> N x N recursivamente como sigue:

f (1) = (1, 1)
f (n + 1) = (1, x + 1)     if f (n) = (x, y) and y = 1,
f (n + 1) = (x + 1, y - 1) if f (n) = (x, y) and y != 1.

Ahora sólo tienes que demostrar que f (i) != f (j) siempre que i != j, y que para cada par (x, y) hay un i tal que f (i) = (x, y). Lo cual no he hecho, así que esto tampoco es una prueba formal, pero debería hacer evidente lo que falta.

Answer 4

Estoy de acuerdo con la respuesta de Andrés E. Caicedo, pero para elevar la prueba a los estándares de calidad, se pueden añadir las dos líneas siguientes:

$\quad$ Las diagonales finitas $D_k \; (m + n = k$ ) partición $\mathbb N\times\mathbb N$ .

$\quad$ Cada diagonal $D_k$ viene equipado con una ordenación lineal.

Si quieres algún aparato formal para dejar esto claro, tenemos lo siguiente (contable significa finito o contablemente infinito):

Teorema 1: Sea $(D_k)_{\, k \in \mathbb N}$ sea una familia indexada de conjuntos contables no vacíos. Además, para cada $k$ y que se defina una ordenación lineal $ \le_k$ en $D_k$ convirtiéndolo en un conjunto bien ordenado e isomorfo a $\mathbb N$ cuando $D_k$ es infinito. Entonces existe una correspondencia biyectiva

$\tag 1 C: \bigcup D_k \to \mathbb N$

Prueba
Primero se demuestra el teorema 1 para el caso en que todos los $D_k$ son conjuntos finitos, en cuyo caso $C$ tiene una "construcción natural" (véase la prueba aquí ). A continuación, se puede establecer una biyección $\mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ y usar eso (junto con un argumento de partición) para completar esta prueba manejando el

$\text{ Is this } D_k \text{ finite or infinite?}$

preguntas de manera estructurada. $\qquad \blacksquare$

Nota: La demostración del teorema anterior fue informal, omitiendo algunos detalles que pueden ser manejados de maneras ligeramente diferentes. Esto es diferente de una prueba informal que tiene todos los 'guardrails' en su lugar, como en la pregunta del OP.

---

No estoy seguro de cómo verían los expertos en ZFC este teorema. Si tenemos una familia de conjuntos contables, indexados por $\mathbb N$ con cada conjunto "una copia" de $\mathbb N$ ', entonces supongo que no necesitamos AOC para saber que la unión (indexada sobre $\mathbb N$ ) de esos $\mathbb N$ es contable.