# How many different sets can be formed by two nonempty sets

If A and B are two different nonempty sets, how many distinct sets can be formed with these sets using as many unions,intersections,complements and parentheses as desired.

Four sets are fundamental:$A$,$B$,$A \cup B$,$A \cap B$.

Other sets are $A \cup B'$,$A' \cup B$,$A \cap B'$,$A' \cap B$,$A' \cup B'$,$A' \cap B'$. Any other sets are possible.

-
You could look at cartesian products and power sets. – PEV Jan 17 '11 at 15:27
@Trevor:Sorry,cartesian products and power sets are not allowed. – Vinod Jan 17 '11 at 15:30
To get a clear answer, you have to assume that A and B are not just distinct but also "as independent as possible" in some sense. Otherwise, it could be the case that A = {1} and B = {1,2}, and you only get 8 possible sets. – Rahul Jan 17 '11 at 16:02

$16$. The corresponding Venn diagram has four parts, and you can get any combination of those four parts.
@Vinod $2^{2^n - 1}$ to be accurate. – Sergey Filkin Apr 8 '12 at 8:30