# How many sets can be created?

We have 10 sets $A_1, A_2, \ldots ,A_{10}$. It is also given that $A_i = A_j \Leftrightarrow i=j$. How many new sets can be generated using union $(\cup)$ and difference $(\setminus)$ any number of times?

-
I'm a bit confused. Are you assuming that the sets are mutually disjoint? In this case the problem solution is straightforward. –  Lepidopterist Mar 20 at 22:33
@Lepidopterist Sorry about that. I was thinking about the original problem and the idea about disjoint sets came only while typing. It definitely makes things too easy. Let's stick to the original thing. –  Pranasas Mar 20 at 22:36

We get the Boolean set algebra $\le \mathcal P(X)$ generated by $A_i$ where $X:=\bigcup_{i=1}^{10}A_i$.

For this, note that $A\cap B=A\setminus(A\setminus B)$ and that $A^\complement=X\setminus A)$.

The free Boolean algebra on $10$ generators contains ($2^{10}$ atoms, of the form $\cap_iA_i^\epsilon$ where $\epsilon$ is either nothing or complement, and therefore) $2^{2^{10}}$ elements. This is the maximum available number, so it means $$2^{2^{10}}-10$$ new sets. But, as you said before, this indeed highly depends on the correlation of the given sets to each other, e.g. if they are mutually disjoint, or if $A_1\subset A_2\subset ..\subset A_{10}$, and so on. But even in these cases we can state that the number of new sets is $2^k-10$ for some $k$, as they generate a Boolean algebra.

-
Note that you can get intersections: $A \cap B = A \backslash (A \backslash B)$. So you can get any of the (up to) $2^{10}-1$ disjoint sets of the form $B_1 \cap \ldots \cap B_{10}$ where each $B_i$ is either $A_i$ or $A_i^c$ but not all are $A_i^c$. And then you can get arbitrary unions of those (including the empty set which is $A_1 \backslash A_1$), so that makes $2^{2^{10}-1}$.