# What is the number of all possible relations/intersections of n sets?

If n defines number of sets, what is the number of all possible relations between them? For example, when n = 2: 1) A can intersect with B 2) A and B can be disjoint 3) A can be subset of B 4) B can be subset of A

that leaves us with 4 possible relations. Now with the n = 3 it gets tricker (A can intersect with B, but not C or B can be subsect of C and intersect with A there etc). Wondering if there's any formula that can be made to calculate such possible relations. Working on this problem for last couple of days, read about Venn diagrams, Karnaugh map, but still can't figure that one out. Any help is appreciated!

-

Let $[n]=\{1,\dots,n\}$, and consider sets $A_1,\dots,A_n$. For each non-empty $S\subseteq[n]$ let

$$U_S=\bigcap_{k\in S}A_k\setminus\bigcup_{k\in[n]\setminus S}A_k\;;$$

$U_S$ is the set of $x$ that belong to $A_k$ if and only if $k\in S$.

To get a clearer picture of this, consider first the case $n=2$. Then $U_{\{1\}}=A_1\setminus A_2$, $U_{\{2\}}=A_2\setminus A_1$, and $A_{\{1,2\}}=A_1\cap A_2$. These are the three regions of a Venn diagram for two sets that are inside at least one of the two sets. A Venn diagram for three sets has eight regions, and you should check that the seven that are in at least one of the three sets are precisely the seven sets $U_S$ such that $\varnothing\ne S\subseteq[3]$.

The relationships amongst the sets $A_1,\dots,A_n$ are completely determined by which of the sets $U_S$ are empty and which are not. Some of these are pretty uninteresting: for instance, if $U_S=\varnothing$ for every non-empty $S\subseteq[n]$, then $A_1=\ldots=A_n=\varnothing$. However, if you’re willing to accept that the emptiness or not of each of the sets $A_k$ is part of their relationship, then we can count the possibilities quite easily: $[n]$ has $2^n-1$ non-empty subsets $S$, so $\{U_S:\varnothing\ne S\subseteq[n]\}$ is a family of $2^n-1$ sets. This family has $2^{2^n-1}$ subfamilies, so there are $2^{2^n-1}$ different ways to choose which of the sets $U_S$ are to be empty. In this sense, then, there are $2^{2^n-1}$ possible relationships amongst $n$ sets.

-
That would do 8 for n=2? What am I missing? –  mathguy Oct 12 '12 at 15:14
@mathguy: If you actually write them out and draw Venn diagrams, you’ll see, but I’d just about bet that you’re missing the ones like $A_1=A_2=\varnothing$. If you don’t accept the emptiness or not of each of the sets $A_k$, counting the possibilities gets a lot stickier. –  Brian M. Scott Oct 12 '12 at 15:26

I am not sure how you would count it. But here is one approach: There are $2^n$ possible intersections to consider between all $n$ sets and their complements. Each one may be empty or not, independently of the others. This yields a total of $2^{2^n}$ possible relations. (In which case you have omitted some, admittedely trivial, relations from your example when $n=2$.)

Edit: If we are working within a standard set theory, in which no set can have an empty complement (in fact, the complement of a set is not itself a set), this answer needs to be divided by two. But it is correct if we imagine working in a universe which is itself a set, containing all the given sets, as one commonly does in applications.

-
You're saying there are $16$ relations possible for $n=2$? That seems a bit off. –  EuYu Oct 12 '12 at 13:30
@EuYu: If $A=B=\emptyset$, 2,3,and 4 are all true –  Ross Millikan Oct 12 '12 at 13:35
@EuYu: Yes. But it all depends exactly what you call a “relation”. –  Harald Hanche-Olsen Oct 12 '12 at 13:37
Maybe one should subtract one relation, if we do not admit the possibility of working inside an empty universe. Or more appropriately, we should subtract one in the exponent, i.e., divide my answer by 2, to account for the impossibility of having the intersection of all $n$ complements being empty. –  Harald Hanche-Olsen Oct 12 '12 at 13:39
Thank you for clearing that up. –  EuYu Oct 12 '12 at 13:47

I'd like to think about this problem not as sets, but as elements in a partial order. Suppose all sets are different. Define $\mathscr{P} = \langle\mathscr{P}(\bigcup_n A_n), \subseteq\rangle$ as the partial order generated bay subset relation on all "interesting" sets.

Define the operation $\cap$ on $\mathscr{P}$ as

$$C = A\cap B \iff C = \sup_\subseteq \{D: D\subseteq A \wedge D\subseteq B\}$$

which is well defined because of, well, set theory....

The question could be then stated as:

Given the sets $A_n$, let $\mathscr{G}$ the subgraph of $\mathscr{P}$ generated by the $A_n$ and closed under the $\cap$ operation. How many non-isomoprhic graph can we get?

-