Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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
add comment

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.