# Ring of sets - Representation of elements

I want to prove: If $\mathcal R$ is a ring of subsets of some non-empty set $X$ and $A_1,\cdots,A_N \in \mathcal R$ then there is some $M \in \mathbb N$ and $B_1,\cdots,B_M$ such that $B_i \cap B_j = \emptyset$ if $i \neq j$ and for every $1 \leq n \leq N$ there exists a subset $I_n$ of $\{1,\cdots,M\}$ s.t. $A_n = \cup_{i \in I_n} B_i$.

I wanted to prove this by induction. Some tips here ?

Hint:

The question is asking you to decompose some sets $A_i$ into basic building blocks $B_j$, such that the $B_j$ are pairwise disjoint, and each $A_i$ is some finite union. Imagine drawing a Venn diagram with the $A_i$, and let the $B_j$ be the distinct regions of the diagram.

For example, with $N=2$, we get $B_1=A_1\setminus A_2$, $B_2=A_2\setminus A_1$, $B_3=A_1\cap A_2,$ and $B_4=X\setminus(A_1\cup A_2)$. $B_4$ can be discarded from the $B_j$'s, but we include it for purposes of the inductive step.

Now, suppose that we have $B_j$ for $A_1,\ldots, A_{N-1}$. Then, using $A_N$, we can split each $B_j$ into two smaller pieces. Can you see how we might do this?

• $B_j = (A_N \cap B_j) \cup (A_N \setminus B_j)$ where the union is disjoint. So I guess the new blocks are $A_N \cap B_j, A_N \setminus B_j$ and $A_N \setminus (\cup_{i=1}^{n-1} A_i )$
– user42761
Commented Sep 2, 2013 at 17:55
• Thanks, then. I will now work it out for myself but its quite evident that all new blocks are disjoint.
– user42761
Commented Sep 2, 2013 at 17:58
• But assume $i \neq j$ where $1 \leq i,j \leq N-1$. Then $A_N \cap B_i$ and $A_N \setminus B_j$ are some of these new blocks. But $(A_N \cap B_i) \cap (A_N \setminus B_j) = A_n \cap B_i \cap B_j^c = A_N \cap B_i$. This does not have to be the emptyset, which means that not alle new blocks have to be disjoint.
– user42761
Commented Sep 2, 2013 at 18:07
• @André: I'm sorry, I looked at your comment too quickly. The new blocks should have the form $B_j\cap A_N$ and $B_j\setminus A_N$, along with $A_N\setminus (\cup_{i=1}^{N-1}A_i)$. Commented Sep 2, 2013 at 18:12