## 1.1. Notation and Set Theory

### Theorem 1.1.4: De Morgan's Laws

i.e. the complement of the intersection
of any number of sets equals the union of their complements.

i.e. the complement of the union of any number of sets equals the intersection of their complements.

### Proof:

We will prove two set-inequalities to prove equality of the left and right hand sides.- Take x contained in the complement of the intersection of all sets
A
_{j}, i.e. x is not in the intersection of all A_{j}. Then there must be at least one set A_{j}that does not contain x (because if all A_{j}would contain x then x would be in their intersection as well). Call this set**A**. Since x is not in**A**, x is in the complement of**A**. But then x is also in the union of all complements of A_{j}, because**A**is one of those sets. This proves that the left hand set is contained in the righ one. - Now take x contained in the union of all complements of
A
_{j}. That means there is at least one complement that contains x, or in other words, at least one of the A_{j}does not contain x. But then x is not in the intersection of all A_{j}, and hence it must be in the complement of that intersection. That proves the other inequality, and hence both sets must be equal.