0
$\begingroup$

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 ?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ $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 )$ $\endgroup$
    – user42761
    Commented Sep 2, 2013 at 17:55
  • $\begingroup$ Thanks, then. I will now work it out for myself but its quite evident that all new blocks are disjoint. $\endgroup$
    – user42761
    Commented Sep 2, 2013 at 17:58
  • $\begingroup$ 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. $\endgroup$
    – user42761
    Commented Sep 2, 2013 at 18:07
  • $\begingroup$ @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)$. $\endgroup$
    – Jared
    Commented Sep 2, 2013 at 18:12

You must log in to answer this question.