Una prueba elegante de la asociatividad de la diferencia simétrica

De rebote (de hecho, en el artículo de Halmos: “Does mathematics have elements?”) me encontré con una prueba elegante de que la operación de diferencia simétrica en el conjunto \mathcal{P}(X) de subconjuntos de un conjunto X, definida como A\Delta B:=(A\setminus B) \cup (B\setminus A)  para todo A,B\subset X es asociativa.

La prueba que yo conocía era: remangarse y hacer cuentas como un anormal. En su momento yo preferí hacer una “prueba” con diagramas de Venn y convencerme de que estos reflejaban realmente todos los casos posibles. Pero igual no era muy satisfactorio.

Hete aquí el argumento:

A cada A\in \mathcal{P}(X) le podemos asociar una función X\to \mathbb{Z}, su función característica \chi_A, definida como \chi_A(x)=\begin{cases}0 & \text{si } x\not\in A \\ 1 & \text{si }x\in A\end{cases}  .

En el conjunto de funciones \mathrm{Fun}(X,\mathbb{Z}) tenemos una estructura de grupo abeliano dada por la suma punto a punto.

Observemos ahora que (\chi_A+\chi_B)(x)=\begin{cases}0 & \text{si } x\in (A\cup B)^c \\ 1 & \text{si } x\in A\Delta B \\ 2 & \text{si } x\in A\cap B\end{cases}. En particular, (\chi_A+\chi_B)(x) \equiv \begin{cases} 0 & \text{si } x\not\in A\Delta B \\ 1 & \text{si } x\in A\Delta B \end{cases} (\text{mod } 2).

Esto nos dice que la función \mathcal{P}(X) \to \mathrm{Fun}(X,\mathbb{Z}_2), A\mapsto \overline{\chi_A}, donde \overline{\chi_A}(x)=\overline{\chi_A(x)} manda la diferencia simétrica en la suma, i.e. \overline{\chi_{A\Delta B}}=\overline{\chi_A} + \overline{\chi_B}.

Ahora bien, esta “función que respeta la estructura” entre \mathcal{P}(X) y \mathrm{Fun}(X,\mathbb{Z}_2) es obviamente inyectiva. Pero la operación en este último conjunto tiene las propiedades de un grupo abeliano, en particular es asociativa, entonces ya está 😀 En efecto (omitiendo las barritas arriba):

\chi_{(A\Delta B)\Delta C}=(\chi_{A\Delta B})+\chi_C =(\chi_A+\chi_B)+\chi_C=\chi_A+(\chi_B+\chi_C)=\chi_A+\chi_{B\Delta C}=\chi_{A\Delta (B\Delta C)}.

Pero \chi es inyectiva, entonces (A\Delta B)\Delta C=A\Delta (B\Delta C)

Anuncios
Esta entrada fue publicada en anillos y módulos. Guarda el enlace permanente.

2 respuestas a Una prueba elegante de la asociatividad de la diferencia simétrica

  1. Maru S dijo:

    Una solucion genial para un problema super engorroso. Me encanto! 😀

  2. C. dijo:

    ‘pecable, chau cuentitas!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s