# Infinite DeMorgan laws

Let $X$ be a set and $\{Y_\alpha\}$ is infinite system of some subsets of $X$.
Is it true that:
$$\bigcup_\alpha(X\setminus Y_\alpha)=X\setminus\bigcap_\alpha Y_\alpha,$$
$$\bigcap_\alpha(X\setminus Y_\alpha)=X\setminus\bigcup_\alpha Y_\alpha.$$
(infinite DeMorgan laws)

Thanks a lot!

#### Solutions Collecting From Web of "Infinite DeMorgan laws"

The first thing to do is the write and understand the definitions of all the symbols in the equation.

Let us recall those:

1. $\bigcup_\alpha A_\alpha=\{a\mid\exists\alpha.a\in A_\alpha\}$
2. $\bigcap_\alpha A_\alpha=\{a\mid\forall\alpha.a\in A_\alpha\}$
3. $A\setminus B=\{a\in A\mid a\notin B\}$

Now we can write a simple element chasing proof:

Let $x\in X\setminus\bigcap_\alpha Y_\alpha$. Then $x\in X$ and $x\notin\bigcap_\alpha Y_\alpha$, therefore for some $\alpha$, $x\notin Y_\alpha$, fix such $\alpha$. Therefore $x\in X\setminus Y_\alpha$, and therefore there exists $\alpha$ such that $x\in X\setminus Y_\alpha$, and by definition we have that $x\in\bigcup_\alpha (X\setminus Y_\alpha)$.

The other direction is as simple, take $x\in\bigcup_\alpha(X\setminus Y_\alpha)$, then for some $\alpha$ we have $x\in X\setminus Y_\alpha$. Therefore $x\in X$ and $x\notin Y_\alpha$, so by definition $x\in X$ and $x\notin\bigcap_\alpha Y_\alpha$, i.e. $x\in X\setminus\bigcap_\alpha Y_\alpha$.

The second identity has a similar proof. I like these proofs because they not hard and give a good exercise in definitions and elements chasing.

For example:

$$x\in \bigcup_\alpha(X\setminus Y_\alpha)\Longrightarrow \exists \alpha_0\,\,s.t.\,\,x\in X\setminus Y_{\alpha_0}\Longrightarrow x\notin Y_{\alpha_0}\Longrightarrow$$

$$\Longrightarrow x\notin\bigcap_\alpha Y_\alpha\Longrightarrow x\in X\setminus\left(\bigcap_{\alpha} Y_\alpha\right)$$

(i) The following statements are equivalent:

1. $y \in X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha}$
2. $y \in X \wedge y \notin \bigcap\limits_{\alpha \in I} A_{\alpha}$
3. $y \in X \wedge \neg((\forall \alpha \in I)\: y \in A_{\alpha})$
4. $y \in X \wedge (\exists \alpha \in I)\: y \notin A_{\alpha}$
5. $(\exists \alpha \in I)(y \in X \wedge y \notin A_{\alpha})$
6. $(\exists \alpha \in I)(y \in X \setminus A_{\alpha})$
7. $y \in \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha})$

(ii) The following statements are equivalent:

1. $y \in X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha}$
2. $y \in X \wedge y \notin \bigcup\limits_{\alpha \in I} A_{\alpha}$
3. $y \in X \wedge \neg((\exists \alpha \in I)\: y \in A_{\alpha})$
4. $y \in X \wedge (\forall \alpha \in I)\: y \notin A_{\alpha}$
5. $(\forall \alpha \in I)(y \in X \wedge y \notin A_{\alpha})$
6. $(\forall \alpha \in I)(y \in X \setminus A_{\alpha})$
7. $y \in \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha})$

Since the first and the last statements are equivalent for all $y$, we have
$$\underbrace{X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha} = \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha})}_{(i)} \wedge \underbrace{X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha} = \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha})}_{(ii)}.$$ $\Box$