37
$\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$

3 Answers 3

45
$\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$
17
$\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
  • 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$ Jun 5, 2017 at 16:56
10
$\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$
2
  • $\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, 2011 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$ May 4, 2011 at 22:25

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.