4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.