# 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 '13 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 '13 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.

-

The answer to this exact question would be: "it depends...". If for instance all the Ai were disjoint, the answer would be 2^n. If on the other hand Ai would be a set {xi, y} with all the xi distinct (that is: any Ai and Aj have one point y in common, the same for any i and j), then the answer would be 2 * 2^n. So it seems to me that the problem is incompletely stated...

-

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}$.

-