Cómo demuestro la cardinalidad de la diferencia simétrica de $n$ establece

Question

Intento demostrar que la cardinalidad de la diferencia simétrica de $n$ conjuntos es
$$\sum\limits_{i}|A_i|-2\sum\limits_{i<j}|A_i\cap A_j|+4\sum\limits_{i<j<k}|A_i\cap A_j\cap A_k|-\ldots$$ Trato de utilizar la Función Característica $\chi(x)$ . Sé que para una diferencia simétrica $A\Delta B$ la función característica es $(\chi_A-\chi_B)^2$ y la cardinalidad de cada conjunto es $|X|=\sum_x\chi(x)$ . pero no sé cómo probarlo para $n$ ¿conjuntos? Así tendré la función característica de cada uno de ellos.

Muchas gracias.

Answer 1

Como dijo Asaf en los comentarios, esto es contabilidad e inducción. Voy a escribir el paso de inducción en su totalidad, pero voy a hacerlo de una manera muy compacta que puede no ser fácil de seguir al principio. Lo hago por dos razones. En primer lugar, deberías intentar resolver el paso de la inducción por tu cuenta, así que no quiero que sea demasiado fácil de leer. (Si tienes problemas para hacerlo en general, te sugiero que escribas el argumento para $n=3$ y quizás $n=4$ primero; en ese momento deberías ser capaz de ver con bastante claridad lo que está pasando, y el principal problema será probablemente expresarlo con claridad en el caso general). En segundo lugar, en algún momento querrás acostumbrarte a leer este tipo de argumentos compactos.

Primero escribamos la suma completa:

$$\left|\bigoplus_{k=1}^nA_k\right|=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\left|\bigcap_{i\in S}A_i\right|\;,\tag{1}$$

donde he utilizado $\oplus$ para la diferencia simétrica, y $[n]=\{1,\dots,n\}$ . Para evitar tener demasiados subíndices, dejemos que $\chi_k$ sea la función característica de $A_k$ y que $\varphi_n$ sea la función característica de $\bigoplus_{k=1}^nA_k$ . Entonces $(1)$ será ciertamente cierto si

$$\varphi_n=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\;,\tag{2}$$

desde $\prod_{i\in S}\chi_i$ es la función característica de $\bigcap_{i\in S}A_i$ .

Puede probar $(2)$ por inducción en $n$ . Hay que utilizar el hecho de que para cualquier función característica $\chi$ , $\chi^2=\chi$ . Usted ya sabe que $\chi_{A\oplus B}=(\chi_A-\chi_B)^2$ . Ahora para el paso de inducción tienes

$$\begin{align*} \varphi_{n+1}&=\left(\varphi_n-\chi_{n+1}\right)^2\\ &=\varphi_n^2+\chi_{n+1}^2-2\varphi_n\chi_{n+1}\\ &=\varphi_n+\chi_{n+1}-2\varphi_n\chi_{n+1}\\ &=\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i+\chi_{n+1}-2\chi_{n+1}\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\tag{3} \end{align*}$$

para empezar. La primera legislatura en $(3)$ se puede dividir como

$$\sum_{i\in[n]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\tag{4}$$

y el primer término de $(4)$ puede combinarse con el $\chi_{n+1}$ término en $(3)$ para rendir

$$\begin{align*} \varphi_{n+1}&=\sum_{i\in[n+1]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i-2\chi_{n+1}\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\\ &=\sum_{i\in[n+1]}\chi_i+\sum_{k=2}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i-2\sum_{k=1}^n(-1)^{k-1}2^{k-1}\sum_{S\subseteq[n]\atop|S|=k}\prod_{i\in S}\chi_i\chi_{n+1}\tag{5}\;. \end{align*}$$

Ahora dejemos que $S$ sea un subconjunto de $[n+1]$ tal que $|S|=k$ . Si $k=1$ entonces $\prod_{i\in S}$ es uno de los $\chi_i$ y aparece en el primer término de $(5)$ con el coeficiente $1=(-1)^02^0=(-1)^{k-1}2^{k-1}$ .

Supongamos ahora que $1<k\le n$ . Si $n+1\notin S$ , $\prod_{i\in S}\chi_i$ se cuenta en el segundo término de $(5)$ donde aparece con el coeficiente $(-1)^{k-1}2^{k-1}$ . Si $n+1\in S$ entonces $\prod_{i\in S}\chi_i$ aparece en el último término de $(5)$ como $\prod_{i\in S'}\chi_i\chi_{n+1}$ , donde $S'=S\setminus\{n+1\}$ y $|S'|=k-1$ . En este caso, el coeficiente de $\prod_{i\in S}\chi_i$ es $-2(-1)^{k-2}2^{k-2}=(-1)^{k-1}2^{k-1}$ .

Por último, supongamos que $k=n+1$ . Entonces $S=[n+1]$ y $\prod_{i\in S}\chi_i=\prod_{i\in[n]}\chi_i\chi_{n+1}$ aparece en el último término de $(5)$ con el coeficiente $-2(-1)^{n-1}2^{n-1}=(-1)^n2^n=(-1)^{k-1}2^{k-1}$ .

De ello se desprende que $(5)$ (y por lo tanto $\varphi_{n+1}$ ) es igual a

$$\sum_{k=1}^{n+1}(-1)^{k-1}2^{k-1}\sum_{S\subset[n+1]\atop|S|=k}\prod_{i\in S}\chi_i\;,$$

que completa el paso de la inducción.

---

Por cierto, un enfoque más sencillo es mostrar que $a\in\bigoplus_{k=1}^nA_k$ si $|\{k\in[n]:a\in A_k\}|$ es impar, lo cual es una inducción fácil, y luego demostrar que el lado derecho de $(1)$ cuenta los elementos de $\bigcup_{k=1}^nA_k$ que están en un número impar de la $A_k$ . Esta es una consecuencia bastante fácil del teorema del binomio. Si un elemento $a$ está exactamente en $m$ de la $n$ conjuntos, para cada $k$ de $1$ a través de $m$ está en $\binom{m}k$ $k$ -intersecciones dobles, por lo que contribuye

$$\begin{align*} \sum_{k=1}^m\binom{m}k(-1)^{k-1}2^{k-1}&=-\frac12\sum_{k=1}^m\binom{m}k(-2)^k\\ &=-\frac12\left(\sum_{k=0}^m\binom{m}k(-2)^k-1\right)\\ &=\frac12\Big(1-(1-2)^m\Big)\\ &=\frac{1-(-1)^m}2\\ &=\begin{cases} 1,&\text{if }m\text{ is odd}\\ 0,&\text{if }m\text{ is even} \end{cases} \end{align*}$$

a la derecha de $(1)$ .