# 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

## 3 Answers

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}$? – user203867 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
• Please let me know why my edit was deleted. – Axion004 Aug 23 '18 at 18:07
• @Axion004: I did not reject the edit, but I am guessing that the reason is that you've added too much content. Answers are supposed to reflect a user's mind. Changing someone's answers too much is not considered a good edit. If you want to elaborate or expand on someone's answer, you should post your own answer. This, on its own, might be frowned upon by some users, especially as a function of how old the question is (e.g. here were we are almost six years past the original post date). So handle with care. – Asaf Karagila Aug 23 '18 at 20:48

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$