23
$\begingroup$

While going through Probability: Theory and Examples by Rick Durrett (4th edition, 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.

$\endgroup$
25
$\begingroup$

The result holds for every family, countable or not, of sets A(i) and it is a simple matter of logic.

To wit, 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)". We are done.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think it's more helpful to write the idea in the following. $$x \in \cup_{i= 1}^{\infty}A_i^c \leftrightarrow \exists j, s.t. a \in A_j^c \leftrightarrow x \notin A_j \leftrightarrow x \notin \cap_{i=1}^{\infty} A_j \leftrightarrow x \in (\cap_{i=1}^{\infty} A_j)^c $$ $\endgroup$ – Albert Chen Jun 5 '17 at 16:56
7
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ How scary does it get if ZFC is invoked? (confession, outside of having seen ZFC on wikipedia, I know nothing about it) $\endgroup$ – JasonMond May 4 '11 at 22:17
  • $\begingroup$ @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. $\endgroup$ – André Nicolas May 4 '11 at 22:25
-5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ and therefore, that induction does not work in the limit. $\endgroup$ – UnadulteratedImagination Jan 23 '13 at 3:17
  • 1
    $\begingroup$ 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.) $\endgroup$ – user642796 Jan 23 '13 at 7:36
  • $\begingroup$ thank you. I had taken the complement of an open interval to be closed. $\endgroup$ – UnadulteratedImagination Jan 23 '13 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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