2
$\begingroup$

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.

MY ANSWER,

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.

  • 0
    How do you know that all those sets you wrote down can be all different?2012-06-21
  • 1
    Your answer is full of $n$, but your question doesn't have any $n$ in it. Please edit one of them appropriately.2012-06-21
  • 0
    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)2012-06-21
  • 0
    Just draw the Venn diagrams.2012-06-21

1 Answers 1

3

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.

  • 0
    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.2012-06-21
  • 0
    @Chris1: An annoying feature of the comment mode is that pressing Return sends the comment. I got caught by this several times.2012-06-21
  • 0
    lol.. i just saw!2012-06-21
  • 0
    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.2012-06-21
  • 0
    so if I get this right the null set includes all empty sets so its only counted once?2012-06-21
  • 0
    @Chris1: Formally, two sets $P$ and $Q$ are defined to be equal if for all $x$, we have $x\in P$ if and only if $x\in Q$. By that criterion, if $P$ and $Q$ are empty sets, then $P=Q$, or more informally there is only one empty set, usually denoted by $\emptyset$. And *any* set can only be counted once.2012-06-21
  • 0
    http://imageshack.us/photo/my-images/641/dscf2084c.jpg/ Thanks a lot. I think I follow you. The empty pictures that I get on this image are when I choose no parts giving the null set. But if I take the case for one set, the empty picture is counted as one combination. Wen I have say two sets, the empty picture from when I had only one set is now part of a combination that isn't empty when I am counting 2 sets. In this way as I add more and more sets there is only ever one null set, as more empty combinations further on are part of non-empty combinations when there are more sets. (i think!)2012-06-21
  • 0
    http://imageshack.us/photo/my-images/641/dscf2084c.jpg/ Thanks a lot. I think I follow you. This is what is confusing me. I counted all the empty combinations to arrive at my answer in the beginning. If they all add to one, why aren't we short at the end of n sets?2012-06-21
  • 0
    this the most hardcore posting/comment site i have ever used!2012-06-21
  • 0
    sorry, was away chairing a thesis oral. any set, no matter how you arrived at it, can only be counted once. If you take $U$ the numbers from $1$ to $10$, $A=\{3,4,5,6\}$, $B=\{567\}$ and list the subsets, you will find there are $16$. The "atoms" are $\{3,4\}$, $\{5,6\}$, $\{7\}$, and $\{1,2,8,9\}$.2012-06-21
  • 0
    Right I have it now. The mistake I was making was thinking of the combinations of the nth set as a sum of the combinations of the previous sets. The reason I find this hard is because I keep thinking of it as a sequence rather than a sequence of combinations. I'm wondering now if there is a way to write this as a sum but I'll leave that for another day. Thanks again for your replies it is terrific that you take the time to help people out like this.2012-06-22