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!

Solution 1:

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.

Solution 2:

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

Solution 3:

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