# How many new subsets may be created?

I've got a following problem.

We have got 10 subsets of X. How many new ( max. number ) subsets may be created using 4 operations : union, intersection, complement, symetric difference?

The first answer is $4^9$, but what if some set happened to be empty? But on the other hand I have to consider possible maximum number. What do you think?

Suppose we are given a system of $k$ distinct sets $$A_1,A_2,...,A_k\subset X$$ such that no pair of sets intersect and $A_1\cup A_2\cup...\cup A_k=X$. Such a system is simple in the way that using union, intersection, complement and symmetric difference, we always end up with the union of some of the $A_i$'s. For a system of $k$ distinct subsets there will be $2^k$ such unions (one of them being empty), namely form a $k$-bit string, $01001...0$ telling at position $i$ whether $A_i$ should be included (if the bit is $1$) or excluded (the bit is $0$) from the union. There are $2^k$ such strings each pointing to a unique union.
Then if we consider another subset $B\subset X$, we can form the subsets \begin{align} B_{2i-1}&=A_i\cap B\\ B_{2i}&=A_i\cap B^c \end{align} dividing each $A_i$ into the part lying within $B$ and the part lying outside of $B$ respectively. Now since $A_i=B_{2i-1}\cup B_{2i}$ which is a disjoint union, we see that $$B_1,B_2,...,B_{2k}$$ forms a new system of $2k$ distinct sets whose union is $X$. This was done only using intersection and complement. Now, any set that can be formed using $A_1,A_2,...,A_k$ and $B$ and the four given operations must be the union of some of the $B_i$'s. Note that some of the $B_i$'s may be empty, but in the extreme case all $B_i$'s are non-empty.
So you start with the system $X$ containing a single set. We have $2^1$ subsets using the four operations. When adding the first set $A$, the system $X$ is (at most) broken into two smaller parts $A_1=X\cap A,A_2=X\cap A^c$. When adding another set we obtain up to $2\cdot 2$ parts. Repeating this up to having added 10 sets, we have divided $X$ into at most $2^{10}$ distinct subsets. Thus we can form at most $2^{2^{10}}$ different unions from those, which answers your question.
Whatever $X$ you pick, and whatever 10 subsets, there's an order-preserving map from the free boolean algebra on 10 generators to the lattice formed by all the subsets you create. So the size of that free boolean algebra ($2^{2^{10}}$) gives you an upper bound. That upper bound will be realized (say) if X consists of 10-element vectors, and the $i$-th subset is defined by fixing the $i$-th coordinate value, for in this case the properties of "being in the $i$-th subset" are fully independent.