¿Cómo demostrar que este mapa es biyectivo?

Question

En el ejemplo 2 de la sección 7 de su libro TOPOLOGÍA, 2ª edición, James R. Munkres demuestra que el producto cartesiano $Z_+ \times Z_+$ , donde $Z_+$ denota el conjunto de todos los enteros positivos, es contablemente infinito como sigue:

En primer lugar, define un subconjunto $A$ de $Z_+ \times Z_+$ de la siguiente manera: $$A \colon= \{ \, (x,y) \in Z_+ \times Z_+ \, \colon \, y \leq x \, \}. $$ A continuación, define un mapa $f \colon Z_+ \times Z_+ \to A$ de la siguiente manera: $$f(x,y) \colon= (x+y-1, y) $$ para todos $(x,y) \in Z_+ \times Z_+$ .

Por último, define un mapa $g \colon A \to Z_+$ de la siguiente manera: $$ g(x,y) \colon= \frac{1}{2} x(x-1) + y$$ para todos $(x,y) \in A$ .

Ahora he conseguido demostrar que el mapa $f$ es biyectiva. Cómo demostrar que el mapa $g$ ¿también es biyectiva?

Encontrando las imágenes de los puntos $(1,1)$ , $(2,1)$ , $(2,2)$ , $(3,1)$ , $(3,2)$ , $(3,3)$ , $(4,1)$ , $(4,2)$ , $(4,3)$ , $(4,4)$ y así sucesivamente, es intuitivo que el mapa $g$ cuenta los puntos en $A$ .

¿Cómo demostrar esta biyectividad de forma rigurosa?

Answer 1

El comportamiento general del mapa $g$ es exactamente como usted sospecha. (1,1) se asigna al primer entero 1. (2,1) y (2,2) se asignan a los enteros siguientes 2, 3. (3,1), (3,2), (3,3) se asignan a los siguientes enteros 4, 5, 6. En general, para encontrar g(x,1), debemos contar cuántos pares han sido asignados antes. Ese número es la cardinalidad del conjunto $B = \{(x', y') | 1 \leq x' \lt x, 1 \leq y' \leq x' \}$ . $B$ es la unión disjunta de los conjuntos $C_{x'} = \{ (x',y') | 1 \leq y' \leq x' \}$ para $1\leq x' \lt x$ . Obviamente, $|C_{x'}| = x'$ Así que $|B| = |C_1| + \cdots + |C_{x - 1}| = 1 + 2 + \cdots + (x - 2) + (x - 1) = x (x - 1) / 2$ . Aquí, la última igualdad es una "identidad bien conocida". Sólo asumo, que lo has visto antes.

Así, cuando queremos mapear (x,1), todos los enteros de 1 a $x(x-1)/2$ ya han sido elegidos, y el siguiente entero libre es $g(x,1) = x(x-1)/2 + 1$ . Siguiendo así, el siguiente entero libre para (x,y) con $1 \leq y \leq x$ es $g(x,y) = x(x-1)/2 + y$ .

Para asignar los pares $(x+1,1), \ldots, (x+1,x+1)$ repetimos todo este argumento con $x+1$ en lugar de $x$ .

En definitiva, vemos que si ordenamos los elementos del conjunto $A$ de su pregunta lexicográficamente (es decir $(x,y) \lt (x',y')$ si $(x \lt x')$ o $(x = x'$ y $y \lt y')$ entonces g(x,y) es simplemente el número de (x,y) en ese ordenamiento.

Esto demuestra que $g$ es una biyección. La inversa $h$ de $g$ funciona de la siguiente manera. Dado $m \in \mathbb Z^+$ , set $x = \max\{x' | x' (x' - 1)/2 \lt m \}$ y $y = m - x$ . Entonces $h(m) = (x,y)$ y $g(x,y) = m$ .