Problem
Let $\{A_i \in I\}$ be a collection of events where $I$ is an arbitrary index set.
Show that
$(\bigcup_{i \in I} A_i)^c = \bigcap_{i \in I} A_i^c$
and
$(\bigcap_{i \in I} A_i)^c = \bigcup_{i \in I} A_i^c$
Solution
In the book, the hint is given: "first prove this for $I = \{1, ..., n\}$
So working it out on my own I think I successfully did that via induction:
Base Case $n=1$
$(\bigcup_{i=1}^n A_i)^c$ with $n=1$ is $(A_1)^c$ which clearly is the same as $A_1^C$
Inductive step
Given that $(\bigcup_{i=1}^n A_i)^c = \bigcap_{i=1}^n A_i^c$ prove this for $n+1$.
$(\bigcup_{i=1}^{n+1} A_i)^c$
=$(A_{i+1} \cup \bigcup_{i=1}^n A_i)^c$
=$A_{i+1}^c \cap (\bigcup_{i=1}^n A_i)^c$
=$A_{i+1}^c \cap \bigcap_{i=1}^n A_i^c$
=$\bigcap_{i=1}^{n+1} A_i^c$
So I've shown this for one of the cases for $I = \{1, ..., n\}$. I think showing it for the other case would be similar, applying demorgan's law in the inductive step.
How do we map this for an arbitrary index set? I can't figure out how to show this step by step, but I think it makes sense to say that for any arbitrary index set, you can arrange the indices in increasing order, and from there, why not use the same induction technique? None of the steps would not hold because subsequent indices are more than one step apart. But ¯\_(ツ)_/¯.
In the solution, the author took a different approach (apparently ignoring the hint from the problem description) of proving:
$(\bigcup_{i \in I} A_i)^c = \bigcap_{i \in I} A_i^c$
by showing both that
- $(\bigcup_{i \in I} A_i)^c \subseteq \bigcap_{i \in I} A_i^c$
- $\bigcap_{i \in I} A_i^c \subseteq (\bigcup_{i \in I} A_i)^c$
using the definitions of $\subseteq$. For example, for (1):
$(\bigcup_{i \in I} A_i)^c$ means that For any $x \in (\bigcup_{i \in I}A_i)^c$, then $x \notin \bigcup_{i \in I}A_i$.
$x \notin \bigcup_{i \in I}A_i$
$\implies \nexists i \in I$ s.t $x \in A$
$\implies x \in A^c, \forall i \in I$
$\implies x \in \bigcap_{i \in I} A_i^c$
Sources
- 36-705 hw1 problem 2