# Why is the following collection of sets equals the following?

Suppose $(A_n)$ is a sequence of events, For any $I \subset \{1,2,\ldots \}$, set

$$C_I = \bigg( \bigcap_{n \in I} A_n \bigg) \cap \bigg( \bigcap_{n \notin I } A_n^c \bigg)$$

I am trying to show that for any $n \geq 1$ we have

$$\bigcup_{|I| < \infty,\ n \in I} C_I = A_n$$

I find kind of hard to understand this identity. For example, if I take $I = \{1,2,3 \}$, then

$$C_I = ( A_1 \cap A_2 \cap A_3) \cap ( A_4^c \cap A_5^c \cap \cdots)$$

But, then how can I understand and compute $\bigcup_{n \in I } C_I$ in this situation?

• What you’ve stated is not true. In order for it to be true, either you must allow infinite subsets in $\bigcup_{n\in I}C_I$, or you must assume that each point is in only finitely many of the sets $A_n$. – Brian M. Scott Mar 19 '15 at 1:20

$C_I$ is the set of points that belong to every $A_n$ with $n\in I$ and to no $A_n$ with $n\notin I$. For instance, $C_{\{2\}}$ is the set of points that are in $A_2$ but not in any other $A_n$. $C_{\{1,5\}}$ is the set of points that are in $A_1\cap A_5$ but not in any other $A_n$.

To show that

$$A_n=\bigcup_{|I|<\infty,n\in I}C_I\;,\tag{1}$$

you can try to show that each side of $(1)$ is a subset of the other.

• Show that if $I$ is finite, and $n\in I$, then $C_I\subseteq A_n$. (This is very straightforward.) Conclude that $$\bigcup_{|I|<\infty,n\in I}C_I\subseteq A_n\;.$$

• Then try to show that if $a\in A_n$, there is a finite $I\subseteq\Bbb Z^+$ such that $a\in C_I$.

This, however, need not be the case. If $a\in A_n$ for all $n$, for instance, then $a\notin C_I$ for any finite $I$. You will be able to prove this only if you have the additional hypothesis that each point is in only finitely many of the sets $A_n$.

What you can prove, even without that extra hypothesis, is that

$$A_n=\bigcup_{n\in I\subseteq\Bbb Z^+}C_I\;,$$

without any restriction on the size of $I$. The first inclusion above is still fine, and it is true that if $a\in A_n$, there is a (not necessarily finite) $I\subseteq\Bbb Z^+$ such that $a\in C_I$. Can you find it?

• I was getting the feeling that we needed either $I$ to be unbounded in size or elements to appear in only finite many $A's$ when I typed up my answer, but I wasn't confident enough to add that note. Glad you put this more detailed version up :) – Alan Mar 19 '15 at 3:05

Look at how something gets into a given $C_I$. Let $I$ be a finite index set and $a\in C_I$ then we have $\forall k\in I,a\in A_k$. We also have $a\in A_j^C$ for $j\notin I$, or in other words, $a\notin A_j$ Therefore, for a given index set, we're collecting all the events which are in every one of those index sets, and in NO other ones. Now, fix $n$ and let $I$ range over every finite index set that includes $n$. How does something get into one of these sets? Well, it has to be in $A_n$, since we are only taking index sets that include n, so we have your union is a subset of $A_n$ So, the only question is, does it miss anything from $A_n$? The answer is no, because if $a\in A_n$, there will be some index set $I$ that $a\in C_I$.

In all honestly, the reason for that last step is evading me, but I started typing before I had the final answer! Hopefully it'll come to you, me, or someone else shortly.
The general proof method though is to try and show both sets are subsets of each other when trying to show a complicated set equality, and thus look at how things get into each one.

But, then how can I understand and compute $\bigcup_{n\in I} C_I$ in this situation?

No, $n$ is a free variable in the required union sequence; it is not bound as a 'dummy variable'.   The interval $I$ is the dummy variable in this case.

You want the union of all $C_I$, for all finite intervals $I$ that contain a particular $n$.

$$\bigcup_{I\ni n: |I|<\infty} C_I \quad=\quad C_{\{n\}} \cup C_{\{1, n\}} \cup C_{\{2,n\}} \cup\cdots\cup C_{\{1, 2, n\}}\cup\cdots$$

Show that for that $n$ this is equal to $A_n$.