9.3: Cardinalidad de una Unión

Sabemos que si\(A\) y\(B\) son disjuntas, entonces la cardinalidad de\(A \cup B\) es\(\# A+\# B\). Aquí hay una fórmula que funciona incluso cuando los conjuntos no son disgregantes:

Proposición\(9.3.1\).

Para cualquier conjunto finito\(A\) y\(B\), tenemos

\[#(A \cup B)=\# A +\# B-\#(A \cap B).\]

Prueba

De Ejercicio\(4.5.6\), sabemos que\(A \backslash B\),\(B \backslash A\), y\(A \cap B\) son par-disjuntas, y que su unión es\(A \cup B\), así\[\#(A \backslash B)+\#(B \backslash A)+\#(A \cap B)=\#((A \backslash B) \cup(B \backslash A) \cup(A \cap B))=\#(A \cup B) .\]

Además, tenemos\ [\ begin {aligned}
\ # A &=\ # ((A\ backslash B)\ cup (A\ cap B))\\
&=\ # (A\ backslash B) +\ # (A\ cap B)
\ end {aligned}\]

(Primero: Ejercicio\(4.5.4(2)\) Segundo: Ejercicio\(4.5.5(4)\)).

Del mismo modo, tenemos\[\# B=\#(B \backslash A)+\#(A \cap B).\]

Por lo tanto\ [\ begin {alineado}
\ # A+\ # B & =(\ # (A\ diagonal inversa B) +\ # (A\ cap B)) + (\ # (B\ diagonal inversa A) +\ # (A\ cap B))\\
&=\ # (A\ diagonal inversa B) +\ # (B\ diagonal inversa A) +2\ # (A\ cap B)\\
&=\ # (A\ copa B) +\ # (A\ cap B).
\ end {alineado}\]

La conclusión deseada se obtiene restando\(\#(A \cap B)\) de ambos lados.

Figura\(9A\). La suma\(\# A+\# B\) incluye todos los elementos de\(A \cup B\), pero cuenta los elementos de\(A \cap B\) dos veces, así\(\# A+\# B=\#(A \cup B)+\#(A \cap B)\). Por lo tanto\(\#(A \cup B)=\# A+\# B-\#(A \cap B)\).

Ejemplo\(9.3.2\).

Dejar\(A=\{\mathrm{p}, \mathrm{r}, \mathrm{o}, \mathrm{n}, \mathrm{g}\}\) y\(B=\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\). Entonces

Solución

\[\# A=5, \# B=5, \text { and } \#(A \cap B)=\#\{\mathrm{r}, \mathrm{o}, \mathrm{n}\}=3,\]

así que Proposición nos\(9.3.1\) dice que\[\#(A \cup B)=\# A+\# B-\#(A \cap B)=5+5-3=7 .\]

Esto es correcto, ya que # (A B) = # {p, r, o, n, g, h, s} = 7.

Ejemplo\(9.3.3\).

Cada uno de los 4000 estudiantes de Modern U posee ya sea un celular o un iPod (o ambos). Las encuestas muestran que:

• 3500 estudiantes poseen un teléfono celular, y
• 1000 estudiantes poseen un iPod.

¿Cuántos alumnos poseen tanto un celular como un iPod?

Solución

Let

• \(S\)ser el conjunto de todos los estudiantes de Modern U,
• \(C\)ser el conjunto de alumnos que poseen un celular, y
• \(I\)ser el conjunto de alumnos que poseen un iPod.

Entonces, por suposición,\[\# S=4000, \quad \# C=3500, \quad \# I=1000\]

Como cada estudiante posee ya sea un celular o un iPod, nosotros tenemos\(S=C \cup I\). Por lo tanto, Proposición nos\(9.3.1\) dice que\[\# S=\#(C \cup I)=\# C+\# I-\#(C \cap I),\]

por lo\[\#(C \cap I)=\# C+\# I-\# S=3500+1000-4000=500 \text {. }\]

De ahí que haya exactamente 500 alumnos que poseen tanto un celular como un iPod.

Ejercicio\(9.3.4\).

1. Supongamos\(\# U=15\)\(\# V=12\),, y\(\# (U \cap V)=4\). Encuentra\(\# (U \cup V )\).
2. Supongamos\(\# R=13\)\(\# S=17\),, y\(\# (R \cup S)=25\). Encuentra\(\# (R \cap S)\).
3. Supongamos\(\# J = 300\)\(\# (J \cup L) = 500\),, y\(\# (J \cap L) = 150\). Encuentra\(\# L\).
4. En una universidad pequeña, hay 90 estudiantes que están tomando Cálculo o Álgebra Lineal (o ambos). Si la clase de Cálculo tiene 70 alumnos, y la clase de Álgebra Lineal tiene 35 alumnos, entonces ¿cuántos estudiantes están tomando tanto Cálculo como Álgebra Lineal?
5. (más difícil) Supongamos\(A\)\(B\),, y\(C\) son conjuntos finitos. Mostrar\ [\ comenzar {alineado}
   \ # (A\ copa B\ copa C) =\ # A+\ # B+\ # C\\
   -\ # (A\ cap B) -\ # (A\ cap C) -\ # (B\ cap C)\\
   &+\ # (A\ cap B\ cap C).
   \ end {aligned}\]
   [Pista: Tenemos fórmulas para\(\#((A \cup B) \cup C)\) y\(\# (A \cup B)\). Otra fórmula útil viene de la igualdad\((A \cup B) \cap C=(A \cap C) \cup(B \cap C) .]\).]

Los siguientes ejercicios son ejemplos de otro tipo de aplicación de la fórmula para la cardinalidad de una unión.

Ejercicio\(9.3.5\).

1. Supongamos\(A\) y\(B\) son subconjuntos de un conjunto finito\(C\). Demuéstralo si\(\# A+\# B>\# C\), entonces\(A \cap B \neq \varnothing\). [Pista: Usa Proposición\(9.3.1\) para mostrar eso\(\#(A \cap B) \neq 0\).]
2. Mostrar que si\(A\) es un conjunto de al menos 600 números naturales que son menores de 1000, entonces dos de los números en\(A\) difieren exactamente en 100. [Pista: Vamos\(B=\{a+100 \mid a \in A\}\), y usa el ejercicio anterior para demostrarlo\(A \cap B \neq \varnothing\).]

Ejercicio\(9.3.6\).

1. Supongamos que\(A_{1}, A_{2}, \ldots, A_{n}\) son conjuntos finitos. Mostrar\[\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) \leq \# A_{1}+\# A_{2}+\cdots+\# A_{n} .\]
   [Pista: El paso de inducción usa Proposición\(9.3.1\).]
2. Demostrar el Principio de encasillamiento (\(9.2.1\)).
   [Pista: El contrapositivo afirma que si\(\# A_{i} \leq 1\) por cada\(i\), entonces\(\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) \leq n\).]

OBSERVACIÓN\(9.3.7\).

Ejercicio generalizante\(9.3.4(5)\), la fórmula Inclusión-Exclusión calcula la cardinalidad de la unión de cualquier número de conjuntos:\[\left|A_{1} \cup \cdots \cup A_{n}\right|=\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{1 \leq i<j \leq n}\left|A_{i} \cap A_{j}\right|+\sum_{1 \leq i<j<k \leq n}\left|A_{i} \cap A_{j} \cap A_{k}\right|-\cdots+(-1)^{n+1}\left|A_{1} \cap \cdots \cap A_{n}\right|.\]

(El signo +/− depende del número de conjuntos que se intersectan: se suman las intersecciones impares y se restan las intersecciones pares, lo que concuerda tanto con la Proposición\(9.3.1\) como con el Ejercicio)\(9.3.4(5)\). No necesitamos esta fórmula, pero se puede leer sobre ella en un libro de texto de Combinatoria (o en Wikipedia).