# Number of elements in a finitely generated Dynkin system

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!

## 1 Answer

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$

• 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. – user45564556 May 14 '18 at 9:26
• 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})$ – scathingtres May 14 '18 at 9:54
• 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}$ – scathingtres May 14 '18 at 10:08