7
$\begingroup$

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

  • 0
    This is a good question, but definitely not [set-theory]. I'm not sure about [combinatorics] or so.2011-07-01

1 Answers 1

7

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.

  • 0
    What confused me is already put into the original question. (Edited text) Thanks.2011-07-06
  • 0
    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?2011-07-07
  • 0
    @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.2011-07-08
  • 0
    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$, ...2011-07-08
  • 0
    Fair enough. So finally, one needs to "check" it until the nesting appears. No quick way.2011-07-08
  • 0
    Aha, that's the point! It is clear now.2011-07-08