# how many distinct sets can be formed

QUESTION

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.

EDIT: lol, I was wondering about the "n" number of sets case. I kinda missed the question there.

which I don't know if it is right.

This is my first answer and I found this question hard. It's wordy because I want to know if I'm thinking on it right.

I don't think $2^{2^n - 1}$ is right. This was a previous answer.

I think the use of "unions,intersections,complements and parentheses as desired" means distinct spaces on a venn diagram.

When I say 'space' I mean distinct set. On a venn diagram this is an area you can fill in on its own and is different from all other spaces.

1 set has 2 spaces, everything in it and the complement of it (ie. U). Total $2^{1}$ spaces

2 sets have 4 spaces, namely, $(A\cup B)', A\cap B, A\cap B', A'\cap B$ . Total $2^{2}$spaces

3 sets have ... Total $2^{3}$ spaces

n sets have ... Total $2^{n}$ spaces

The next thing to notice is that any combination of n things is also $2^{n}$. For example, when there is one set there are two spaces, (everything inside, everything outside.) how many ways can we combine these two spaces?

1)our set alone

2)everything outside our set

3)everything outside our set and our set

4) nothing inside or outside our set

So:

one set has 2 spaces, and 4 different combinations of spaces.

2 sets have 4 spaces, and 16 different combination of spaces.(you could draw a venn diagram)

3 sets have 8 spaces, and 256 different combinations of spaces.

All we need now is a formula that goes from our set number to our spaces number to our combinations number.

Spaces ---> combinations

2 ---> 4

4 ---> 16

8 ---> 256

After playing with it, if we let n=1,2,3,4... we can use $2^{2^{n}}$.

Number of sets-->Spaces ===> combinations

1---> 2 ===> 4 or $2^{2^{1}}$

2 ---> 4 ===> 16 or $2^{2^{2}}$

3 ---> 8 ===> 256 or $2^{2^{3}}$

n ---> 2^n ===> $2^{2^{n}}$

I would like to know if this is correct.

-
How do you know that all those sets you wrote down can be all different? –  Qiaochu Yuan Jun 21 '12 at 12:23
Your answer is full of $n$, but your question doesn't have any $n$ in it. Please edit one of them appropriately. –  Gerry Myerson Jun 21 '12 at 12:29
As your question is stated, there are up to sixteen distinct sets that can be formed, depending on how the sets relate to each other. It can also be any power of 2 between 2 and 16. (1 as well, if you allow the entire space to be empty) –  tomasz Jun 21 '12 at 12:40
Just draw the Venn diagrams. –  tomasz Jun 21 '12 at 12:42

The question you ask is specifically about two sets $A$ and $B$. Draw a general Venn diagram with a universe $U$ (the usual rectangle), and two intersecting sets $A$ and $B$, say disks. The Venn Diagram divides the universe into $4$ parts. The only subsets we can make using the allowed tools are a union of $0$ or more of these parts. By listing, we can see that there are $16$ such subsets.

But what about if we start with $3$ sets, $A$, $B$, and $C$? We go directly to the general case, where instead of starting with $2$ sets $A$ and $B$, we start with $n$ sets $A_1, A_2,\dots,A_n$. I believe you were solving the general case, without explicitly saying so. If that is so, the answer you got is correct.

Let the $A_i$ be subsets of a "universe" $U$. Imagine drawing the associated Venn Diagram. The diagram divides the universe into pairwise disjoint parts.

These parts are obtained by looking successively at $A_1$, $A_2$, $A_3$, and so on, and saying yes or no. There are $2^n$ ways to do this. For some choices of $A_1$ to $A_n$, some of the resulting sets will be empty. But (if our universe is large enough) we can find $A_i$ such that each of the $2^n$ subsets we obtain in this way is non-empty. Then the number of sets that can be constructed using allowed tools is as large as possible.

The $2^n$ parts of the Venn Diagram are the "atoms" from which our subsets are constructed by union. We cannot split $U$ into finer parts than these atoms by using a combination of allowed operations.

Now we can build all the achievable subsets by saying yes or no to each atom, and taking the union of the atoms we say yes to. If we have the full number $2^n$ of atoms, the number of ways to do this is $2^{(2^n)}$.

If $U$ is large enough, then by appropriate choice of the $A_i$ we can arrange to have exactly $k$ atoms, where $k$ is any number between $0$ and $2^n$. If we have $k$ atoms, then $2^k$ subsets can be constructed using allowed tools.

-
Thanks! This was really helpful. Just one question though. Don't we have to include the empty sets as they are included in the operations? (which is what I did). Isn't that okay just to say we need to count the empty ones? I'm sorry if I'm being slow here, I'm trying to learn some algebra before college. –  wavey Jun 21 '12 at 15:10
@Chris1: An annoying feature of the comment mode is that pressing Return sends the comment. I got caught by this several times. –  André Nicolas Jun 21 '12 at 15:12
lol.. i just saw! –  wavey Jun 21 '12 at 15:13
There is only one empty set. It is taken care of at the end. Remember we have $2^n$ "atoms" (basic regions) in the Venn diagram, and we build a set by taking a union of "some" of these. By "some" I mean $0$ or more of these. Deciding to use the union of none produces the emptyset. –  André Nicolas Jun 21 '12 at 15:16
so if I get this right the null set includes all empty sets so its only counted once? –  wavey Jun 21 '12 at 15:20