Un ejercicio de prueba biyectiva en combinatoria

Como se sabe, el número de elementos del producto cartesiano de dos conjuntos finitos es el producto de las cardinalidades de los conjuntos. Pero aquí vamos a exhibir una demostración de ese hecho aplicando una prueba biyectiva de $|A \times B| = |A| |B|$.

Para demostrarlo vamos a definir una función entre el producto cartesiano $A\times B$ y el conjunto de enteros $S = \{0, 1, ..., |A||B| - 1\}$.

Sea $A = \{a_0, a_1, ..., a_{m-1}\}$ y $B = \{b_0, b_1, ..., b_{n-1}\}$, con $m = |A|$ y  $n = |B|$ , y definamos la función $ f : A\times B \to S $ de la siguiente manera:  $f(a_i, b_j) = i + m j$, donde $i = 0, 1, \dots , m-1$ y $j = 0, 1, \dots, n-1$.

(Nota: la idea que está por detrás de esta función es contar sobre las columnas de la tabla de doble entrada --o representación matricial-- del producto cartesiano. En la primera columna $j=0$, y al continuar sobre la segunda columna se vuelve a empezar agregando $m$. Notemos que el elemento $ij$ del producto cartesiano es $(a_i,b_j)$ y está ubicado en la fila $i$ y columna $j$; y si llegamos a él contando por columnas, ya hemos contado $jm$ elementos de las $j$ columnas anteriores más los que van de la columna $j$. Notemos también que esta forma de contar es algo extraña pues inicia con el cero.)

Demostremos que $f$ es inyectiva.

Para ello tomemos dos imágenes $i + m j = k + m l$. Vamos a demostrar que $i = k$ y $j = l$, es decir, que los elementos del producto cartesiano de donde provienen son también iguales.

Si consideramos las imágenes desde la perspectiva de la aritmética modular, se tiene $i = k$ (mod $m$), es decir, las dos imágenes son equiresiduales respecto al módulo $m$. Y si ahora consideramos que $0 \leq i, k < m$, se sigue que $i = k$. De aquí que $m j = m l$, y finalmente que $j = l$.

Demostremos ahora que $f$ es sobreyectiva:

Sea $p$ un elemento de $S = \{0, 1, ..., mn-1\}$. Vamos a demostrar que existe un $i \in \{ 0, 1, \dots, m-1\}$ y un $j \in \{ 0, 1, \dots, n-1\}$ tal que $p = i + m j$, es decir, vamos a demostrar que existe un elemento del producto cartesiano cuya imagen es $p$.

Esto se logra dividiendo $p$ entre $m$: puesto que $p$ es de $S$, el cociente --digamos $i$-- debe ser menor que $n$, y el residuo --digamos $j$-- debe ser menor que $m$. Y ya acabamos.

Comentario final

El ejercicio parece ocioso pues todo mundo puede ver el resultado con solamente mirar la representación matricial del producto cartesiano. La verdadera utilidad de este ejercicio no está en demostrar un resultado obvio, sino en practicar el método que debe seguir una demostración biyectiva.

Los saluda
jmd