# Prove that F is in $\sigma$-algebra iff it equals to a specific sum of intersected sets or their complements

Let $$X = \bigcup_{j=1}^{n}A_j$$, where $$A_j \neq \emptyset$$. Let $$\mathcal{F}$$ be a $$\sigma$$-algebra generated by $$A_1,\dots, A_n$$. Show that $$F \in \mathcal{F}$$ if and only if $$F = \bigcup_{(\epsilon_1,\dots,\epsilon_n)\in J} A_1^{\epsilon_1} \cap \dots \cap A_n^{\epsilon_n}$$ where J is some set of zero-one sequences of length n, and $$A_j^0 = A_j$$ and $$A_j^1 = A_j^C$$. Estimate from below and above cardinality of $$\mathcal{F}$$.

My attempt (only $$\implies$$):

Let $$F \in \mathcal{F}$$ and $$x \in F$$ and $$M_x$$ to be an interesection of all sets $$A_1, \dots, A_m$$ such that $$x \in A_n$$(what I mean is $$M_x = \bigcap A\in \bigcup_{j=1}^nA_j, A_j \ni x$$). Then for arbitrary: $$\{x\} \subset \left( A_1 \cap \dots \cap A_m \right) = M_x$$ but if we denote those sets A which contain x with indexes $$1, \dots, m$$ (this is not strictly formal as we don't really rearrange sets here) then: $$\{x\} \subset \left( A_1 \cap \dots \cap A_m \cap A_{m+1}^C \cap \dots \cap A_n^C \right) \subset \left( A_1 \cap \dots \cap A_m \right) = M_x$$ because $$x \notin A_{m+1}, \dots, A_n$$.

We may now take $$\bigcup_{x\in F}$$, and create a zero-one sequences in the process:

• if $$x \in A_j$$ then $$\epsilon_j = 0$$
• if $$x \notin A_j$$ then $$\epsilon_j = 1$$ (we take a complement)

$$F = \bigcup_{x\in F}x \subset \bigcup_{(\epsilon_1,\dots,\epsilon_n)\in J} A_1^{\epsilon_1} \cap \dots \cap A_n^{\epsilon_n}$$

But that is just a half of proof $$\implies$$. I need to show: $$F \supset \bigcup_{(\epsilon_1,\dots,\epsilon_n)\in J} A_1^{\epsilon_1} \cap \dots \cap A_n^{\epsilon_n}$$ As well as $$\impliedby$$ and also estimate cardinalities. Could I get some hints? Thanks.

Hints:

1) Sets of the form $$A^{\epsilon_1} \cap A^{\epsilon_1}\cap...\cap A^{\epsilon_n}$$ form a partition of $$X$$ (which means they are pair-wise disjoint and their union is $$X$$).

2) Each $$A_i$$ is a union of sets from this partition; for example $$A_1$$ is simply the union of all sets of the form $$A^{\epsilon_1} \cap A^{\epsilon_1}\cap...\cap A^{\epsilon_n}$$ where $$\epsilon_1=1$$.

3) Using 2) show that sigma algebra generated by $$A_i$$'s is same as those generated by the sets of this partition.

4) For any finite partition $$\{B_1,B_2,...,B_m\}$$ the sigma algebra generated is nothing but all possible unions of the sets $$B_i$$.