Let A and B be subsets of M and let S(0)={A,B}. for i>= 0 define S(i+1) inductively to be the collection of subsets X of M that are of the form CUD , C inter D , MC, where C, D are in S(i). let S be the union of all the S(i). What is the largest number of elements of S(i)?
A)4 B)8 C) 15 D)16 E)infinity
I tryed to solve this question by counting the sets and I always get 14 elements :
A,
B,
empty set,
MA,
MB,
M,
AUB,
A inter B,
AU(MB),
Aint(MB),
(MA)UB,
(MA)interB,
(MA)U(MB),
(MA)inter(MB)
The right answer happened to be D. What are the remaining uncounted set?
GRE 9367 #60
Re: GRE 9367 #60
I think there are two sets that are omitted:
(AB)U(BA)
(complement(A)complement(B))U(complement(B)complement(A))
(AB)U(BA)
(complement(A)complement(B))U(complement(B)complement(A))
Re: GRE 9367 #60
Draw a Venn diagram of A, B and M. You'll notice there are four disjoint regions which cover the entire picture: the things in M outside of both A and B, the things in A alone, the things in B alone and the things in both A and B. Every element of the algebra over {A, B} either includes or excludes each of these four regions. Thus there are 2^4 = 16 elements of the algebra.

 Posts: 16
 Joined: Sun Jul 19, 2009 12:29 pm
Re: GRE 9367 #60
cool!mag487 wrote:Draw a Venn diagram of A, B and M. You'll notice there are four disjoint regions which cover the entire picture: the things in M outside of both A and B, the things in A alone, the things in B alone and the things in both A and B. Every element of the algebra over {A, B} either includes or excludes each of these four regions. Thus there are 2^4 = 16 elements of the algebra.