# Prove De Morgan's Law: $(A \cap B)^c=A^c\cup B^c$

Prove De Morgan's Law: $(A \cap B)^c=A^c\cup B^c$ and derive from it the law $(A \cup B)^c=A^c\cap B^c$.

Proof of first: Let x be an arbitrary element of $(A \cap B)^c$ then x does not belong to A and B. Then by law of excluded middle(not sure if this is correct) x is either not in A, not in B or not in either. Thus x belongs to $A^c \cup B^c$ and $(A \cap B)^c \subseteq A^c \cup B^c$

Let x be an arbitrary element of $A^c \cup B^c$. Then either x does not belong to A or x does not belong to B. Then x can't belong to $A \cap B$. Thus $A^c \cup B^c \subseteq (A \cap B)^c$.

For the second part I'm not entirely sure what is meant by derive. But my guess is to use the inclusive case from $A^c \cup B^c$.

Suppose x belongs to $A^c \cap B^c$ then by the first law x belongs to $(A \cap B)^c$ and since x belongs to $A^c$ and $B^c$ then x belongs to $(A \cup B)^c$.

Your argument for the first part seems ok. For the second part notice that $(X^c)^c = X$. By the first part we have $$A \cup B = (A^c)^c\cup (B^c)^c = (A^c \cap B^c)^c.$$

Therefore $$(A\cup B)^c = A^c\cap B^c.$$

Simply note that $$x\in (A\cup B)^c\Longleftrightarrow x \notin A\cup B \Longleftrightarrow x\notin A \text{ and }\ x \notin B\Longleftrightarrow x\in A^c \text{ and } x\in B^c.$$ Therefore, $$x\in A^c\cap B^c$$