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.

The question is from the following multiple choice problem:

Let $A$ and $B$ be subsets of a set $M$ and let $S_0=\{A,B\}$. For $i\geq 0$, define $S_{i+1}$ inductively to be the collection of subsets $X$ of $M$ that are of the form $C\cup D$, $C\cap D$, or $M-C$ (the complement of $C$ in $M$), where $C,D\in S_i$. Let $S=\cup_{i=0}^{\infty}S_i$. What is the larest possible number of elements of $S$?

A. 4
B. 8
C. 15
D. 16
E. $S$ may be infinite.

It seems that this might be related to the "$\sigma$-algebra". But I have no idea what technique one needs to solve this problem. I tried some finite set, e.g., $\{0,1,2,3,4,5\}$ and let $A=\{0\}$, $B=\{1\}$. But I cannot find any pattern in the example. Any ideas how to solve it?

Also, I have a question:

Is this just a trivial exercise for testing some knowledge? Or is there a big picture behind the problem?

Edit: As the answer suggested, I draw the picture. However, unless I finally enumerate all the 16 possibilities and cannot get more, I cannot convince myself that the answer is D. Any quick way to do this?

enter image description here

share|improve this question
    
This is a good question, but definitely not [set-theory]. I'm not sure about [combinatorics] or so. –  Asaf Karagila Jul 1 '11 at 18:46

1 Answer 1

up vote 7 down vote accepted

Draw a Venn Diagram. For "general" $A$ and $B$, the world $M$ will be divided into $4$ parts. It is fairly easy to see that using the allowed operations, we can get any set that is the union of $0$ or more of these parts. So before each part, stop and decide whether to include it. For each of the parts, there are $2$ choices, for a total of $2^4$.

The idea can be generalized to situations in which we start with $3$ sets, $4$ sets, and so on. When we start with $n$ sets, the maximum total generated is $2^{(2^n)}$, and this vaue is in general assumed.

We could think of this as an exercise in combinatorics, or as a way of making people think about what kinds of sets can be generated using the important set-theoretic operations of the problem. We could also think of it as partly an exercise in reading and understanding the rather formal language used in formulating the problem.

Added: We could use the Venn diagram as the intuitive basis behind a diagram-free approach. We will say that $X$ is a basic set if $X$ is one of $A\cap B$, $A\cap B^c$, $A^c \cap B$, or $A^c \cap B^c$, where in general $U^c$ denotes the complement of $U$ in $M$. These basic sets are pairwise disjoint. Obviously some could be empty, but for any $M$ with at least $4$ elements, it is easy to come up with $A$ and $B$ such that there are exactly $4$ non-empty basic sets.

For the formal construction, note first that in general $S_i \subseteq S_{i+1}$, since by definition if $X\in S_i$ then $X\cap X \in S_{i+1}$. It is obvious that the basic sets are constructible using our operations, and that so is any union of $0$ or more basic sets. In the generic case there are $2^4$ distinct such unions. This does not quite end things. For completeness we need to prove the intuitively obvious fact that no other subsets of $M$ are constructible.

In principle this is done by induction on the number of steps in the construction. For the base step, we observe that $A$ and $B$ are unions (possibly empty) of basic sets. For the induction step, we need to show that if any of the three fundamental operations is applied to a union of basic sets, the result is a union of basic sets. This is very easy for each of $\cup$, $\cap$, and relative complement.

share|improve this answer
    
What confused me is already put into the original question. (Edited text) Thanks. –  Jack Jul 6 '11 at 18:35
    
I can understand that according to your answer, there can not be more than 16 subsets. However, it seems for me that one needs to construct $S_i$ step by step to finally say the number is 16. Correct? –  Jack Jul 7 '11 at 21:27
    
@Jack: Please note that if $M$ is infinite (or large enough finite), then there are $n$ sets such that if we start with these, we can obtain $2^{(2^n)}$ sets through the procedure you described, but never more. Yours was the case $n=2$. Basically similar idea for the proof. –  André Nicolas Jul 8 '11 at 1:59
    
Thanks for your patience. I don't think I explained my confusion well. Using the notation of my diagram, let $A=I\cup II$ and $B=II\cup III$, then $S_0=\{I\cup II,II\cup III\}$, and $S_1=\{I\cup II\cup III,II,III\cup IV,I\cup IV\}$. One can find that $S_1$ does not contain the sets which are in $S_0$. Since the construction of $S_{i+1}$ only relies on $S_i$, I cannot convince myself that one can finally make $S=\bigcup S_i$ contain all the combination of the "basic sets", i.e., I,II,III,IV, unless I go on to construct $S_2$, $S_3$, ... –  Jack Jul 8 '11 at 3:29
    
Fair enough. So finally, one needs to "check" it until the nesting appears. No quick way. –  Jack Jul 8 '11 at 4:28

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.