Disjoint Set Proof

325 Views Asked by At

Let A1, A2, ... be an arbitrary infinite sequence of events, and let B1, B2, ... be another infinite sequence of events defined as follows:

$B_1 = A_1, B_i = \frac {A_i}{\bigcup^{i-1}_{j=1} A_j}$ for i = 2, 3, ...

Prove that B1,B2,... is a disjoint collection of events:

I have no idea how to tackle this? I understand what a disjoint collection is, but I don't know where to begin with this one?

Any help is appreciated

1

There are 1 best solutions below

0
On

I'll sketch a proof. Use induction on $B_1,...,B_n$. $B_1$ by itself is obviously a family of disjoint sets so the base case is easy. Let $m=n+1$. If $B_1,...,B_n$ are disjoint, it shouldn't be too hard to show that $B_1,...,B_m$ are disjoint. Basically, $B_m$ is disjoint from the sets $A_1,...A_n$ which are supersets of $B_1,...B_n$. Then deduce for any $B_i$ and $B_j$ with $i \neq j$, $B_i$ and $B_j$ are disjoint. This means that $B_1,...$ are pairwise disjoint.

Upon further thought, induction is just overkill. If you have natural numbers $i,j$ with $i \neq j$, then just pick the larger number. WLOG, assume $j>i$. Then $B_j$ is disjoint from $A_i$ by construction. $A_i$ is a super set of $B_i$. So the family is pairwise disjoint.