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$

  • $\begingroup$ Why can I assume WLOG that $\mathcal{J}$ is linearly ordered by $\subseteq$? I mean, how to I then show it when it isn't linearly ordered? Also I don't understand your last sentence. $\endgroup$ – user45564556 May 14 '18 at 9:26
  • $\begingroup$ If it is not then, you dont have to take all $A_j\backslash...\backslash A_k $ since if $A_j \nsubseteq A_k $ and $ A_k \nsubseteq A_j$ then $A_j \backslash A_k \notin D(\mathcal{J})$ and then $\#D(\mathcal{J}) <\# P((\Omega)\cup \mathcal{J})$ $\endgroup$ – scathingtres May 14 '18 at 9:54
  • $\begingroup$ Every element of $ D(\mathcal{J}) $could be expressed in form $A_j\backslash ....\backslash A_k$ where $A_j,...,A_k \in (\Omega)\cup \mathcal{J}$ $\endgroup$ – scathingtres May 14 '18 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.