4
$\begingroup$

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!

3 Answers 3

4

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.

  • 0
    @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.2012-10-12
1

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.

  • 0
    But if one then works in a universe having fewer than $2^n$ members, this is suddenly getting a lot more challenging.2012-10-12
0

Disclaimer: Not an answer®

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?