How can I show that the Dynkin system generated by $n$ subsets of a set has at most $2^{n+1}$ elements?
It's easy to show for pairwise disjoint subsets and intuitively I feel like that's when the cardinality is maximal, but I haven't found a proof yet.
I've tried showing it inductively by considering the following sets:
- the Dynkin system generated by n given subsets, let's call it $D_{n}$,
- for a given $(n+1)$st subset $A_{n+1}$, the set of all disjoint unions of it with elements of $D_{n}$: $\{A_{n+1} \cup B \vert B \in D_{n}, A_{n+1} \cap B = \emptyset \}$,
- the set of all complements of those sets: $\{(A_{n+1} \cup B)^{c} \vert B \in D_{n}, A_{n+1} \cap B = \emptyset \}$.
If I could show that the union of those three sets is a Dynkin system the proof would be done, because by induction hypothesis $D_{n}$ has at most $2^{n+1}$ elements and the other two sets have at most $2^{n}$ elements each, which would be $2^{n+2}$ at most in total. The problem is that I can't show closedness under disjoint unions, could anyone help me with that?
Thanks for any help!
If you are not only interested in a proof by induction,you could try to show that $D(\mathcal{J})$ cardinality is lower than $\#P(n+1)$ for $\#\mathcal{J}=n$ ,to do so you can WLOG assume that $\mathcal{J} $ is linearly ordered set by $ \subseteq $ ,then you can prove that $$ \#P((\Omega )\cup \mathcal{J})\geq\#D(\mathcal{J})$$ since there is a surjective function $$f:P((\Omega )\cup \mathcal{J})\ \rightarrow D(\mathcal{J})$$ $f(\{A_k,...,A_j\})=A_j\backslash ....\backslash A_k$