Question

Prove the following DeMorgan's laws: if LaTeX: XX, LaTeX: AA and LaTeX: BB are sets and LaTeX: \{A_i: i\in I\} {Ai:i∈I} is a family of sets, then

LaTeX: X-(A\cup B)=(X-A)\cap (X-B)

LaTeX: X-(\cup_{i\in I}A_i)=\cap_{i\in I}(X-A_i)

Answer 1

• 
  `X-(A\cup B)=(X-A)\cap(X-B)`

I'll assume the usual definition of set difference,
`X-A=\{x\in X,x\\ot\in A\}`.

Let
`x\in X-(A\cup B)`. Then
`x\in X` and
`x\\ot\in(A\cup B)`. If
`x\\ot\in(A\cup B)`, then
`x\\ot\in A` and
`x\\ot\in B`. This means
`x\in X,x\\ot\in A` and
`x\in X,x\\ot\in B`, so it follows that
`x\in(X-A)\cap(X-B)`. Hence
`X-(A\cup B)\subset(X-A)\cap(X-B)`.

Now let
`x\in(X-A)\cap(X-B)`. Then
`x\in X-A` and
`x\in X-B`. By definition of set difference,
`x\in X,x\\ot\in A` and
`x\in X,x\\ot\in B`. Since
`x\\ot A,x\\ot\in B`, we have
`x\\ot\in(A\cup B)`, and so
`x\in X-(A\cup B)`. Hence
`(X-A)\cap(X-B)\subset X-(A\cup B)`.

The two sets are subsets of one another, so they must be equal.

• 
  `X-\left(\bigcup\limits_(i\in I)A_i\right)=\bigcap\limits_(i\in I)(X-A_i)`

The proof of this is the same as above, you just have to indicate that membership, of lack thereof, holds for all indices
`i\in I`.

Proof of one direction for example:

Let
`x\in X-\left(\bigcup\limits_(i\in I)A_i\right)`. Then
`x\in X` and
`x\\ot\in\bigcup\limits_(i\in I)A_i`, which in turn means
`x\\ot\in A_i` for all
`i\in I`. This means
`x\in X,x\\ot\in A_(i_1)`, and
`x\in X,x\\ot\in A_(i_2)`, and so on, where
`\{i_1,i_2,\ldots\}\subset I`, for all
`i\in I`. This means
`x\in X-A_(i_1)`, and
`x\in X-A_(i_2)`, and so on, so
`x\in\bigcap\limits_(i\in I)(X-A_i)`. Hence
`X-\left(\bigcup\limits_(i\in I)A_i\right)\subset\bigcap\limits_(i\in I)(X-A_i)`.