Suppose $A_1,A_2,…A_n$ are sets in some universal set $U$, and $n\geq2$. Prove that $\overline{A_1 \cup A_2 \cup … \cup A_n}$ = $\overline{A_1} \cap \overline{A_2} \cap … \cap \overline{A_n}$
[Math] Induction proof involving sets
induction
Related Solutions
For three sets (events), it is intuitively clear why the formula works: If we take the measure (probability) of the union then we count the pairwise intersections twice. So we subtract the measure (probability) of the intersections. But then we subtracted the measure (probability) of the triple intersection. So we have to add it.
If there are more sets (events) then you can argue the similar way. We added the measure of the pairwise intersections twice. So subtract them. But then we subtracted the measure (probability) of the triple intersections. So let's add them. But now we added the measure of the four-tuples of intersections. So subtract them...
We can try to analyse strong induction the same way as normal induction (in fact they are equivalent in "strength"), "step by step".
How does the above prove, for example, the case $n = 5$?
We have the base case $n = 2$.
For $n = 3$, we only use $n = 2$, and the result is proved in the induction step.
Now for $n = 4$, we have the results for $n = 2, 3$, and the induction step uses both and proves it.
If now we analyse $n = 5$, we have already seen that the result is true for $n = 2,3,4$, so the induction step can use all these previous results and prove that case.
Ad infinitum.
Best Answer
Prove the base case for $n=2$. So we have $\overline{A_1 \cup A_2} = \overline{A_1} \cap \overline{A_2}$. Assume it is true for $n=m$; i.e., $\overline{A_1 \cup A_2 \cup \ldots A_m}$ $=\overline{A_1} \cap \overline{A_2} \cap \ldots \overline{A_m}$.
Now, let $B = \overline{A_1 \cup A_2 \cup \ldots A_m}$. Then, $B =\overline{A_1} \cap \overline{A_2} \cap \ldots \overline{A_m}$ (by assumption).
So, $\overline{A_1 \cup A_2 \cup \ldots A_m \cup A_{m+1}}$ $= \overline{B \cup A_{m+1}}$ $= \overline{B} \cap \overline{A_{m+1}}$ (by the base case)
$=\overline{A_1 \cup A_2 \cup \ldots A_m} \cap \overline{A_3}$
$=\overline{A_1} \cap \overline{A_2} \cap \ldots \overline{A_m} \cap \overline{A_3}$
Proving base case is easy:
$x \in \overline{A_2 \cup A_2}$ $\iff x \notin A_1 \cup A_2$ $\iff x\notin A_1 \wedge x\notin A_2$ $\iff x \in \overline{A_1} \wedge x \in \overline{A_2}$ $\iff x \in \overline{A_1} \cap \overline{A_2}$