= Solution
Prove both identities by <mathematical induction>. The base case $n=2$ is the two-set form of <De Morgan's laws>. For the <union> identity, suppose the result holds for $n$. Applying the two-set identity and then the <inductive hypothesis> gives
$$
\begin{aligned}
A\setminus\bigcup_{i=1}^{n+1}B_i
&=\left(A\setminus\bigcup_{i=1}^{n}B_i\right)\cap(A\setminus B_{n+1})\\
&=\left(\bigcap_{i=1}^{n}(A\setminus B_i)\right)\cap(A\setminus B_{n+1})
=\bigcap_{i=1}^{n+1}(A\setminus B_i).
\end{aligned}
$$
For the <intersection> identity, the corresponding step is
$$
\begin{aligned}
A\setminus\bigcap_{i=1}^{n+1}B_i
&=\left(A\setminus\bigcap_{i=1}^{n}B_i\right)\cup(A\setminus B_{n+1})\\
&=\left(\bigcup_{i=1}^{n}(A\setminus B_i)\right)\cup(A\setminus B_{n+1})
=\bigcup_{i=1}^{n+1}(A\setminus B_i).
\end{aligned}
$$
These close the two inductions.
Back to article page
