Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.