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 definite$l$y not [set-theory]. I'$m$ $n$ot 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
    Aha, that's the point! It is clear now.2011-07-08