# 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!

-
Yes, it is, and the proof is basically the same as with finite unions/intersections – DonAntonio Oct 5 '12 at 3:45
@DonAntonio: Not exactly, actually. The finite case is done by induction where the step uses the fact we proved these for two sets and associativity. The general case uses a slightly different approach. – Asaf Karagila Oct 5 '12 at 13:07
I suppose induction can be used whenever something countable kicks in, yet I wouldn't do it that way but showing one side is contained in the other one and the other way around, as shown in my answer below. Following this strategy both proofs are practically indistinguishable. – DonAntonio Oct 5 '12 at 13:09
@DonAntonio: Yes, this is true. – Asaf Karagila Oct 5 '12 at 15:19

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.

-
When you say (in line 6), for some $\alpha$, do you mean there exists $\alpha$ such that $x \notin Y_{\alpha}$? – Learner Mar 27 '15 at 1:01
I am not entirely sure what is line 6, possibly due to different line breaks on my phone, but every time "some $\alpha$" appears it is right next to "such that...", so I am guessing the answer is yes. – Asaf Karagila Mar 27 '15 at 7:55

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$

-