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.

While going through this book (p.9), I came across the familiar definition of $\sigma$-algebras where, if $A_i \in \mathcal{F}$ is a countable sequence of sets for some $\sigma$-algebra $\mathcal{F}$ and $\cup_i A_i \in \mathcal{F}$ by definition, then it follows that $\cap_i A_i^C \in \mathcal{F}$ by de Morgan's law.

That's when it occurred to me that I had never seen a proof that de Morgan's law holds over a countably infinite number of sets. I don't have my measure theory/probably theory books with me right now, but I'm quite sure that I've never seen any of them prove this before extending $\sigma$-algebras to countable union or intersection, depending on which definition it started with.

On the one hand, it seems obvious that it would hold. On the other hand, seeming obvious is not a proof, especially when it comes to something involving infinity.

I can imagine an inductive proof where I

  1. assume de Morgan's law holds for an index set of size $n$
  2. Then prove that it holds for an index set of size $n+1$

and wrap it up by $n \rightarrow \infty$ but I'm not convinced that's right. For example, an argument like that doesn't work for countable intersection being closed on a collection of open sets.

So what's a good proof that can extend de Morgan's law to an infinite collection of sets.

share|improve this question

4 Answers 4

up vote 14 down vote accepted

The result holds for every family, countable or not, of sets A(i) and is a simple matter of logic: the assertion "x belongs to the union" means "there exists i such that x belongs to A(i)" hence its negation "x belongs to the complement of the union" is also "for all i, x does not belong to A(i)", that is, "for all i, x belongs to the complement of A(i)". You are done.

share|improve this answer

I expect you are looking for an informal mathematical argument, not a formal proof in (say) ZFC.

When is $x$ not in $\cup_i A_i$? Precisely when $x$ is outside all the $A_i$, so precisely when $x\in A_i^C$ for all $i$, so precisely when $x \in \cap_i A_i^C$

share|improve this answer
    
How scary does it get if ZFC is invoked? (confession, outside of having seen ZFC on wikipedia, I know nothing about it) –  JasonMond May 4 '11 at 22:17
    
@JasonMond: It is not bad, the hard part is mastering the notation. However, once that is done, the informal argument translates in a straightforward way. –  André Nicolas May 4 '11 at 22:25

First we need to recall what $\cup_{k=1}^\infty A_k$ is. We say that $a\in \cup_{k=1}^\infty A_k$ if and only if there exists $A_k$ so that $a\in A_k$.

Now, if $a \in \cup_{k=1}^\infty A_k^c$, then $a\in A_k^c$ for some $k$. In particular, $a\not \in \cap_{k=1}^\infty A_k$, so we must have $a\in (\cap_{k=1}^\infty A_k )^c$. This shows that $\cup_{k=1}^\infty A_k^c\subset (\cap_{k=1}^\infty A_k )^c$. Hopefully you can show the other way yourself, :).

And of course, as @Did pointed out, this does not at all depend on there being countably many sets.

share|improve this answer

Here's a proof, (counterexample) that De Morgan's law don't always apply to countable sets.

We can prove that every open set is the countable union of open intervals Bartle-Sherbert Theorem 11.1.9. We can also prove that not every closed set is the countable intersection of closed intervals e.g. Cantor's set (pg 316 Bartle-Sherbert). Hence, De Morgan's laws do not apply.

share|improve this answer
1  
and therefore, that induction does not work in the limit. –  UnadulteratedImagination Jan 23 '13 at 3:17
    
How does this disprove de Morgan's laws for countable sets? The complement of an open interval is not a closed interval: $\mathbb{R} \setminus (0,1) = ( - \infty , 0 ] \cup [ 1 , + \infty )$. (Note that the Cantor set is the countable intersection of finite unions of closed intervals.) –  Arthur Fischer Jan 23 '13 at 7:36
    
thank you. I had taken the complement of an open interval to be closed. –  UnadulteratedImagination Jan 23 '13 at 9:02

Your Answer

 
discard

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.