Cardinal de la unión de $n$ conjuntos

RESUMEN. Demostramos una fórmula para hallar el cardinal de la unión de $n$ conjuntos.

    Enunciado
    Dado un conjunto $A$ denotamos por $|A|$ a su cardinal. Sean los $n$ conjuntos finitos $A_1,\ldots,A_n$ que podemos suponer contenidos en un conjunto universal $U$ finito. Se trata de demostrar la fórmula $$\left|A_1\cup \ldots \cup A_n\right|=\sum_{i=1}
    ^n\left|A_i\right|-\sum_{i,j=1,\;i < j} ^n\left|A_i\cap A_j\right|+$$ $$ \sum_{i,j,k=1,\;i < j < k} ^n\left|A_i\cap A_j\cap A_k\right|+\ldots +(-1)^{n+1}\left|A_1\cap A_2\cap \ldots \cap A_n\right|.$$ Se pide:
  1. Demostrar la fórmula para $n=2$.
  2. Demostrar la fórmula para $n=3$.
  3. Usando el método de inducción, demostrar que la fórmula es válida para todo $n\ge 2$.
    Solución
  1. Sabemos que si $B_1,\ldots,B_m$ son $m$ conjuntos finitos y disjuntos dos a dos se verifica $$\left|B_1\cup\ldots \cup B_m\right|=\left|B_1\right|+\ldots+\left|B_m\right|.\qquad [1]$$ Tenemos $$A_1=A_1\cap U= A_1\cap\left(A_2\cup A_2^c\right)= \left(A_1\cap A_2\right)\cup \left(A_1\cap A_2^c\right),$$ $$A_2=A_2\cap U= A_2\cap\left(A_1\cup A_1^c\right)= \left(A_1\cap A_2\right)\cup \left(A_2\cap A_1^c\right).$$ Además, $A_1$ está expresado como unión de los conjuntos disjuntos $A_1\cap A_2$ y $A_1\cap A_2^c$ y por $[1]$, $$\left|A_1\right|=\left|A_1\cap A_2\right|+\left|A_1\cap A_2^c\right|.\qquad [2]$$ De la misma manera, $$\left|A_2\right|=\left|A_1\cap A_2\right|+\left|A_2\cap A_1^c\right|.\qquad [3]$$ Por otra parte, $$A_1\cup A_2=\left(A_1\cap A_2\right)\cup \left(A_1\cap A_2^c\right)\cup \left(A_2 \cap A_1^c\right)$$ está expresado como unión de tres conjuntos disjuntos dos a dos, y por $[1]$, $$\left|A_1\cup A_2\right|=\left|A_1\cap A_2\right|+\left|A_1\cap A_2^c\right|+\left|A_2\cap A_1^c\right|.\qquad [4]$$ Sumando miembro a miembro $[2]$ y $[3]$ y pasando un $\left|A_1\cap A_2\right|$ al primer miembro $$\left|A_1\right|+\left|A_2\right|-\left|A_1\cap A_2\right|=\left|A_1\cap A_2\right|+\left|A_1\cap A_2^c\right|+\left|A_2\cap A_1^c\right|,$$ y usando la igualdad $[4]$ queda $$\left|A_1\cup A_2\right|=\left|A_1\right|+\left|A_2\right|-\left|A_1\cap A_2\right|=\sum_{i=1}^2\left|A_i\right|+(-1)^{2+1}\left|A_1\cap A_2\right|.$$
  2. Usando la fórmula deducida en el apartado anterior, $$\left|A_1\cup A_2\cup A_3\right|=\left|A_1\cup \left(A_2\cup A_3\right)\right|=$$ $$\left|A_1\right|+\left|A_2\cup A_3\right|-\left|A_1\cap\left(A_2\cup A_3\right)\right|$$ $$=\left|A_1\right|+\left|A_2\right|+\left|A_3\right|-\left|A_2\cap A_3\right|-\left|\left(A_1\cap A_2\right)\cup \left(A_1\cap A_3\right)\right|$$ $$=\left|A_1\right|+\left|A_2\right|+\left|A_3\right|-\left|A_2\cap A_3\right|$$ $$-\left(\left|A_1\cap A_2\right|+\left|A_1\cap A_3\right|-\left|\left(A_1\cap A_2\right)\cap \left(A_1\cap A_3\right)\right|\right)$$ $$=\left|A_1\right|+\left|A_2\right|+\left|A_3\right|-\left|A_2\cap A_3\right|$$ $$-\left|A_1\cap A_2\right|-\left|A_1\cap A_3\right|+\left|A_1\cap A_2\cap A_3\right|$$ $$=\sum_{i=1}^3\left|A_i\right|-\sum_{i,j=1,\; i < j}^3\left|A_i\cap A_j\right|+(-1)^{3+1}\left|A_1\cap A_2\cap A_3\right|.$$
  3. Sea la fórmula cierta para $n\ge 3$ y veamos que es cierta para $n+1$: $$\left|A_1\cup \ldots \cup A_n\cup A_{n+1}\right|=\left|\left(A_1\cup \ldots \cup A_n\right)\cup A_{n+1}\right|$$ $$=\left|A_1\cup \ldots \cup A_n\right|+\left|A_{n+1}\right|-\left|\left(A_1\cup \ldots \cup A_n\right)\cap A_{n+1}\right|$$ $$=\left|A_1\cup \ldots \cup A_n\right|+\left|A_{n+1}\right|-\left|\left(A_1\cap A_{n+1}\right)\cup \ldots \cup\left(A_n\cap A_{n+1}\right)\right|$$ $$ =\sum_{i=1}
    ^n\left|A_i\right|-\sum_{i,j=1,\;i < j} ^n\left|A_i\cap A_j\right| + \sum_{i,j,k=1,\;i < j < k} ^n\left|A_i\cap A_j\cap A_k\right|$$ $$+\ldots +(-1)^n\left|A_1\cap \ldots \cap A_n\right|+\left|A_{n+1}\right|$$ $$-\sum_{i=1} ^n\left|A_i\cap A_{n+1}\right|+\sum_{i,j=1,\;i < j} ^n\left|A_i\cap A_j\cap A_{n+1}\right|$$ $$-\sum_{i,j,k=1,\;i < j < k} ^n\left|A_i\cap A_j\cap A_k\cap A_{n+1}\right|$$ $$+\ldots -(-1)^{n+1}\left|A_1\cap \ldots \cap A_n\cap A_{n+1}\right|.$$ Agrupando los cardinales de las intersecciones de un conjunto, de dos, etc. obtenemos $$\left|A_1\cup \ldots \cup A_n\cup A_{n+1}\right|=\sum_{i=1} ^{n+1}\left|A_i\right|-\sum_{i,j=1,\;i < j} ^{n+1}\left|A_i\cap A_j\right|$$ $$+\sum_{i,j,k=1,\;i < j < k} ^{n+1}\left|A_i\cap A_j\cap A_k\right|+\ldots +(-1)^{(n+1)+1}p\left|A_1\cap\ldots\cap A_n\cap A_{n+1}\right|,$$ y la fórmula es cierta para $n+1$.
Esta entrada fue publicada en Álgebra. Guarda el enlace permanente.