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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.