Una ayuda para entender el método de biyección mediante el recuento

Question

Estoy tratando de dar sentido al argumento de que $$| \mathbb{N} \times \mathbb{N}|=|\mathbb{N}|$$

mediante la búsqueda de una biyección (sin usar Cantor-Bernstein).

El método que quiero utilizar es hacer considerando la lista de pares como

$$(0,0) (0,1) (0,2) (0,3) (0,4)...$$ $$(1,0) (1,1) (1,2) (1,3) (1,4)...$$ $$(2,0) (2,1) (2,2) (2,3) (2,4)...$$

y contando como

$\begin{matrix} 0 & 1 & 3 & 6 & 10.. \\ 2 & 4 & 7 & 11... \\ 5 & 8 & 12 & 17.. \\ 9 & 13 & 18.. \end{matrix}$

Es decir, una forma de mapear desde cada par a un único número natural.

Mis pensamientos:

Me he dado cuenta de algunas cosas, en primer lugar si ordenamos los puntos como $(m,n)$ y la diagonal como k empezando por la diagonal 0, tenemos que $m+n=k$

Además, veo que parece que $f(0,n)-f(0,n-1)=n$ pero no estoy seguro de cómo puedo demostrar que siempre es cierto. Por ejemplo, $f(0,3)-f(0,2)=6-3=3$ , $f(0,4)-f(0,3)=10-6=4$ etc. Así que f(0,n)=f(0,n-1)+n. pero $f(0,n-1)=f(0,n-2)+(n-1)$

por lo que parece que $$f(0,n)=n+(n-1)+...+1+0=\frac{n(n+1)}{2}$$

También observo que la kª diagonal tiene $k+1$ puntos.

No estoy seguro de cómo puedo unirlo o si es un enfoque correcto. Tampoco estoy seguro de cómo hacerlo formal. Se agradece cualquier ayuda, gracias.

Answer 1

Ya casi has llegado.

Ha visto que necesita definir $f(0,n) = \frac{n(n+1)}{2}$ para todos $n \in \mathbb{N}$ . Ahora bien, fíjate en que $$f(k,n-k) = \frac{n(n+1)}{2}+k$$ para todos $n \in \mathbb{N}$ y todos $k \le n$ .

Sustitución de $n-k$ por $\ell$ obtenemos $$f(k,\ell) = \frac{(k+\ell)(k+\ell+1)}{2} + k$$ para todos $(k,\ell) \in \mathbb{N} \times \mathbb{N}$ .

Ahora puedes comprobar que esto define una biyección.

---

Otra posible biyección utiliza la factorización de primos. Definir $g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ por $g(k,\ell) = 2^k(2\ell+1)-1$ para todos $(k,\ell) \in \mathbb{N} \times \mathbb{N}$ y comprueba los detalles.