# How to prove that $n$ sets have maximum of $2^n-1$ disjoint subsets when you have operations $\cup , \cap , \setminus$?

I just found out that you can have $2^{2^n-1}$ different subsets, made from $n$ sets, using operations $\cup , \cap , \setminus$.

That is because when $n=2$, for example, you have 3 disjoint subsets: $A\setminus B, B\setminus A,A\cap B$ and then you can union those things together in $2^3-1$ different ways (plus the empty set) to get $8$ different unequal sets.

My question is, how to prove that the number of those disjoint subsets is $2^n-1$.

Pictorial definition of what disjoint subsets are: In the picture above I have enumerated disjoint subsets of $2$ and $3$ sets. As you can see their number is $2^n-1$.

First of all, your question is not really well-defined, or put differently, the claim is incorrect in general. Consider for example $A = B = \emptyset$, in which there is only one set which you can get, namely $\emptyset$.

There are at least two ways in which we can address this problem. The first is to assume that the starting sets are "generic", that is, they don't enjoy any "special" properties. This is a vague description, but it can be formalized by saying that in the "Venn diagram" of the sets (which I describe below), all regions are non-empty.

The second way is to do everything formally. We think of $A$ or $A \setminus B$ not as a set but as a formal expression defined in an appropriate language. We then make two expressions equal if they are equal whenever you substitute actual sets. For example, $A = A \cap A$ and $A \setminus (A \setminus B) = A \cap B$. You can also define equality syntactically if you prefer.

Another problem with your claim is that it's not clear what you mean by "the sets have $2^n-1$ non-overlapping subsets". For example, $A \cap B$ and $A \setminus B$ are non-overlapping, and this is a maximal collection of non-overlapping subsets (in general). You mean something else, and again there are several possible interpretations. This time all interpretations I can think of only serve to complicate things and make them less intuitive, so I'll just explain what is meant by the claim, and you think of an appropriate interpretation.

The Venn diagram of the sets $A_1,\ldots,A_n$ consists of the $2^n$ regions which you can get by intersecting either $A_i$ or $\overline{A_i}$ for each $i$. That is, for each $i = 1,\ldots,n$ we choose $A_i$ or $\overline{A_i}$, and then compute the intersection of these $n$ sets. You can web-search "Venn diagram" to see pictorial representations.

You can prove by induction (exercise) that any set that you can obtain from (possibly multiple copies of) $A_1,\ldots,A_n$ using $\setminus$, $\cup$ and $\cap$ is a union of regions of the Venn diagram; indeed, a union which doesn't include the region $\overline{A_1} \cap \cdots \cap \overline{A_n}$. Moreover, you can easily get any of these $2^n-1$ regions individually (exercise), and these are your "$2^n-1$ non-overlapping subsets". In total, you can get any union of these $2^n-1$ regions (exercise), and so you can "reach" $2^{2^n-1}$ different expressions.

One possible formulation of your two claims are as follows. First, the maximal number of disjoint sets that can be formed from $A_1,\ldots,A_n$ is $2^n-1$ (under the caveats described in the second paragraph); this can be proved using the exercises mentioned above. Second, the number of different sets that can be formed (again, under the same caveats) is $2^{2^n-1}$, which again follows from these exercises.

• Suppose every 2 sets among n sets have at least 1 element in common and 1 element not in common, is what I meant. I'm reading a book and it also doesn't define anything properly and I have to keep guessing what the authors mean.. But I'm amazed by how some people still understand what they mean. – Pavel Apr 15 '16 at 20:58
• That's not enough. You have to assume that all regions (other than the outside region) in the Venn diagram are non-empty. – Yuval Filmus Apr 15 '16 at 21:03
• I don't exactly understand what you mean by that, what do you mean by "regions"? – Pavel Apr 15 '16 at 21:06
• You mean that all non-overlapping subsets have 1 element in common with the new set in my proof? – Pavel Apr 15 '16 at 21:07
• The "regions" are the intersections of $A_i/\overline{A_i}$. You can think of them as the actual regions in the Venn diagram. There are $2^n$ of them, but the outside one $\overline{A_1} \cap \cdots \cap \overline{A_n}$ doesn't come into play here. – Yuval Filmus Apr 15 '16 at 21:08

Proof by induction.

Suppose for $n=2$ it's true. (Obvious from Venn diagram with 2 sets).

Let's prove for $n=k+1$:

Suppose we have k sets, then we have $2^k-1$ disjoint subsets. Now we add another set. Then that set is supposed to be in intersection with $2^k-1$ of previous subsets and have a part that doesn't intersect with anything, hence we get $2*(2^k-1)+1=2^{k+1}-1$ subsets. From picture above you can see how C is added to A and B.