Use De Morgan's laws for sets and induction to prove that

Question

Use De Morgan's laws for sets and induction to prove that $$D-(A_1 \cup A_2 \cup ...\cup A_n)=(D-A_1)\cap(D-A_2)\cap...\cap(D-A_n)$$

I am familiar with De Morgan's laws and understand the distribution through sets but applying that and induction is throwing off. to start obviously the starting case is trivial but then to prove k+1 is where i am struggling.

Answer 1

For the inductive step:

$$D-(A_1 \cup A_2 \cup ... \cup A_k \cup A_{k+1}) =$$ ( definition - for set)

$$ D \cap (A_1 \cup ... \cup A_{k+1})^C=$$ (De Morgan)

$$ D \cap A_1^C \cap ... \cap A_{k+1}^C=$$ ($D = D \cap D)

$$ D \cap A_1^C \cap ... \cap D \cap A_k^C \cap D \cap A_{k+1}^C =$$ (definition - for sets)

$$ (D -A_1) \cap (D-A_2)... \cap (D-A_{k+1})$$

OK, so that isn't using the inductive hypothesis, ans indeed you really don't need induction for this at all, but it is an inductive proof (once you add the base case)

Answer 2

We only need to use De Morgan's Law and the fact if $A$ and $B$ are any two sets then $$A-B=A\cap B^c.$$

For each $n\in\Bbb N$, we have $$ \begin{align} (D-A_1)\cap(D-A_2)\cap...\cap(D-A_n)&=(D\cap A_1^c)\cap(D\cap A_2^c)\cap\dots\cap(D\cap A_n^c)\\ &=D\cap \big(A_1^c\cap A_2^c\cap \dots\cap A_n^c \big)\\ &=D\cap \big(A_1\cup A_2\cup\dots\cup A_n \big)^c\\ &=D-\big(A_1\cup A_2\cup\dots\cup A_n \big). \end{align}$$

Answer 3

Prove it for $n=1$ (trivial) and prove it for $n=2.$ For $n\geq 2,$ assume it holds for $n.$

Let $\cup_{j=1}^nA_j=A'_1$ and $A_{n+1}=A'_2 .$ Then we have $$D-\cup_{j=1}^{n+1}A_j=D-(A'_1\cup A'_2)=$$ $$=(D-A'_1)\cap (D-A'_2) =(\cap_{j=1}^n(D-A_j))\cap (D-A_{n+1})=$$ $$=\cap_{j=1}^{n+1}(D-A_j).$$