Exclusión Inclusión Principio De Inducción A Prueba De

Question

Tengo nueva casa el trabajo que me pidieron la prueba de la exclusión a la inclusión principio de inducción, y mi pregunta es ¿cómo puedo hacer eso?

Cualquier ayuda será apreciada!

Answer 1

Una gran sugerencia es probar el resultado para los tres grupos, $A_1, A_2, A_3$, dado el resultado para los dos conjuntos. Supongo que ya has visto el resultado de dos conjuntos: $$|A_1\copa A_2| = |A_1|+|A_2|-|A_1\cap A_2|$$ Entonces, ¿qué queremos conseguir con tres juegos? Se comienza por escribir la triple unión como la unión de dos conjuntos: $$|A_1\copa A_2\copa A_3|=|(A_1\copa A_2)\cup A_3|$$ y por lo que podemos utilizar los dos-set resultado en $A_1\cup A_2$$A_3$, por lo que $$|(A_1\copa A_2)\cup A_3|=|A_1\copa A_2| + |A_3|-|(A_1\copa A_2)\cap A_3|$$ Ahora podemos utilizar los dos-set resultado en $|A_1\cup A_2|$ para obtener $$\begin{align} |A_1\cup A_2\cup A_3|&=|A_1\cup A_2| + |A_3|-|(A_1\cup A_2)\cap A_3|\\ &=|A_1|+|A_2|-|A_1\cap A_2|+ |A_3|-|(A_1\cup A_2)\cap A_3|\\ &=|A_1|+|A_2|+ |A_3|-|A_1\cap A_2|-|(A_1\cup A_2)\cap A_3| \end{align}$$ Ahora usa la propiedad distributiva en el último término: $$|A_1\copa A_2\copa A_3|=|A_1|+|A_2|+ |A_3|-|A_1\cap A_2|-|(A_1\cap A_3)\cup (A_2\cap A_3)|$$ y el uso de los dos-set de la propiedad de nuevo en el último término, con los conjuntos de $A_1\cap A_3$ $A_2\cap A_3$ para obtener $$\begin{align} |(A_1\cap A_3)\cup (A_2\cap A_3)|&=|A_1\cap A_3|+|A_2\cap A_3|-|(A_1\cap A_3)\cap (A_2\cap A_3)|\\ &=|A_1\cap A_3|+|A_2\cap A_3|-|A_1\cap A_2\cap A_3| \end{align}$$ Por último, sustituimos esto en nuestra gran expresión (recordar que fue negado) para obtener $$\begin{align} |A_1\cup A_2\cup A_3|=&\phantom{-}|A_1|+|A_2|+ |A_3|\\ &-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3|\\ &+|A_1\cap A_2\cap A_3| \end{align}$$ En otras palabras, tenemos que el tamaño de una de tres conjunto de la unión puede ser calculado por el $$|A_1\copa A_2\copa A_3| = \sum_{1\le i\le 3}|A_i|-\sum_{1\le i < j\le 3}|A_i\cap A_j|+\sum_{1\le i < j < k\le 3}|A_i\cap A_j\cap A_k|$$

---

Ahora la mala noticia es que después de todo este trabajo no va a usar este resultado en la inducción de la prueba. Es sólo una sugerencia para guiarle a conseguir a través del paso inductivo. Ciertamente inducción sobre el número, $n$, de los conjuntos. El caso base es $n=2$, que es sólo el resultado conocido dijimos en la parte superior de este post.

La parte difícil es saber cómo escribir el resultado en una forma ordenada. Me gustaría sugerir que se definen los distintos sumandos mediante algo parecido a esto: $$\text{Permita }J_{n, k}=\sum_{1\le i_1<i_2<\cdots<i_k\le n}|A_{i_1}\cap A_{i_2}\cap\dots\cap A_{i_k}|$$ así, en el paso inductivo desea mostrar que si $$|A_1\copa A_2\cup\dots\copa A_n|=\sum_{k=1}^n(-1)^{k+1}J_{n, k}$$ entonces $$|A_1\copa A_2\cup\dots\copa A_n\copa A_{n+1}|=\sum_{k=1}^{n+1}(-1)^{k+1}J_{n+1, k}$$ Para ello, adaptar la sugerencia que me dio para mostrar el paso inductivo y así completar su prueba. La mejor de las suertes.