7
$\begingroup$

I understand Venn diagram equations of 2 sets. It has been perhaps 3 years since I have done Venn diagram so I have gotten really rusty at this.

I don't understand in the equation for 3 sets why in the end they add the intersection of 3 sets...

I have such a hard time visualising these diagrams and knowing what to subtract from intersection etc...

enter image description here

I know this is a super easy question but it is one of those questions you either get or you don't and right now I cant figure out why they add the intersection at the end.. shouldn't it be subtract the intersection?

This is how I looked at the problem to solve it. You look at the commonality between A and B at first so you look at the part where A = B or A and B...You subtract that because of overlay. Same concept as 2 set Venn diagram. Then you look at commonality between B and C or simply when B = C, subtract overlay. C and A or C=A subtract overlay...Now you have a hole left in the center which you can fill by adding A and B and C or simply the commonality between A and B and C or A = B = C

enter image description here

I'm lost once more...

this time its 4 sets or 5 or 6 or 7 or 8.... I don't understand the general formula given below.

enter image description here

3 Answers 3

2

Take a point in the intersection and see how many times it gets counted on the left side, and how many times on the right - then you'll see why it has to be added.

  • 0
    But my explanation succeeds. You want to count each element in the union exactly once. If an element is in, say, $A_1$ only, it just gets counted once, as an element of $A_1$. If it's in just $A_1$ and $A_2$, it gets counted twice, but then subtracted as an element of the intersection, so the net effect is to count it once. If it's in just $A_1,A_2,A_3$, it gets counted 3 times, then subtracted three times, then added back in; the net effect is to count it once. If it's in $A_i$, $i=1,2,3,4$, it gets counted 4 times, subtracted 6 times, added back 4 times, subtracted once; net, counted once.2012-03-20
18

The numbers in the diagram indicate how many times the given formula counts that particular portion of the Venn Diagram. In the first picture, for example, an element in the intersection of A, B, and C will be counted 3 times. Each term of the inclusion-exclusion formula gradually refines these numbers until each portion of the Venn Diagram is counted exactly once.

  • 2
    thank you that helps a lot in understand now!!! +12012-03-21
7

Let us assume one wants to evade Venn diagrams, then indicator functions are an alternative.

Recall that for every set $A$ and every element $x$, $\mathbf 1_A(x)$ is $1$ if $x\in A$ and $0$ if $x\notin A$. Then, for every subset $A$ of a given set $E$, this defines a function $\mathbf 1_A:E\to\mathbb R$, called the indicator function of $A$ (in $E$), such that $ |A|=\sum\limits_{x\in E}\mathrm 1_A(x).\tag{1} $ This formulation might seem to only complicate things. Let us show the opposite is true, for the reason that now one deals with sums on a fixed set $E$.

It happens that indicator functions are especially well suited to intersections. To wit, for every collection of sets $A_k$ with intersection $C$, $ \mathbf 1_C=\prod\limits_k\mathbf 1_{A_k}. $ Let us now put indicator functions and intersections of sets together.

First consider two sets $A$ and $B$. Then one might remember that $\mathbf 1_{A\cup B}=\mathbf 1_A+\mathbf 1_B-\mathbf 1_{A\cap B}$ and proceed. So far so good, except this is not a new formula at all. To see this, consider that unions of complementary sets are complementary sets of intersections so let us find the intersection hidden here. One gets $ E\setminus(A\cup B)=(E\setminus A)\cap(E\setminus B), $ hence $ \mathbf 1_{E\setminus(A\cup B)}=\mathbf 1_{E\setminus A}\cdot\mathbf 1_{E\setminus B}.\tag{2} $ One last tool before we proceed. To enumerate a complementary set is easy, since $ \mathbf 1_{E\setminus A}=1-\mathbf 1_A.\tag{3} $ Note that, using (1), (3) yields $ |E\setminus A|=\sum\limits_{x\in E}(1-\mathrm 1_A(x))=\sum\limits_{x\in E}1-\sum\limits_{x\in E}\mathrm 1_A(x)=|E|-|A|. $ Coming back to the union, (2) and (3) yield $ 1-\mathbf 1_{A\cup B}=(1-\mathbf 1_{A})\cdot(1-\mathbf 1_{B})=1-\mathbf 1_A-\mathbf 1_B+\mathbf 1_{A\cap B}, $ which can be rewritten as $ \mathbf 1_{A\cup B}=\mathbf 1_A+\mathbf 1_B-\mathbf 1_{A\cap B}. $ For two sets, this was complicating well known arguments for nothing but now, let us consider $n$ subsets $A_k$ of $E$ and let us try to imitate the arguments above.

Calling $A$ the union of the sets $A_k$, $B_k=E\setminus A_k$ and $B$ the intersection of the sets $B_k$, one gets $ E\setminus A=B,\quad \mathbf 1_B=\prod\limits_{k=1}^n\mathbf 1_{B_k}, \quad \mathbf 1_B=1-\mathbf 1_A, \quad \mathbf 1_{B_k}=1-\mathbf 1_{A_k}. $ To summarize, the key formula here is $ 1-\mathbf 1_A=\prod\limits_{k=1}^n(1-\mathbf 1_{A_k}).\tag{4} $ The rest is algebra. Expanding the RHS of (4) yields a sum over every sequence of choices of $1$ or $(-\mathbf 1_{A_k})$, from $k=1$ to $n$. One can choose $(-\mathbf 1_{A_k})$ for every $k$ in $K$ and $1$ for every $k$ not in $K$, and the product is the sum of the results over every possible subset $K$ of $\{1,2,\ldots,n\}$, that is, $ \prod\limits_{k=1}^n(1-\mathbf 1_{A_k})=\sum\limits_K\prod\limits_{k\in K}(-\mathbf 1_{A_k})=\sum\limits_K(-1)^{|K|}\mathbf 1_{A_K}, \qquad A_K=\bigcap\limits_{k\in K}A_k. $ The $K=\varnothing$ term is $1$, which can be cancelled with $1$ on the LHS of (4), hence, changing the signs, one is left with

$ \mathbf 1_A=\sum\limits_{K\ne\varnothing}(-1)^{|K|+1}\mathbf 1_{A_K}, \quad\text{with}\quad A=\bigcup\limits_{k=1}^nA_k, \quad A_K=\bigcap\limits_{k\in K}A_k. $

This yields finally the size of $A$ by summation over $x$ in $E$, namely,

$ |A|=\sum\limits_{K\ne\varnothing}(-1)^{|K|+1}|A_K|. $

Note that these identities are valid for every number $n$ of sets $A_k$.

Example When $n=3$, the sum over the sets $K$ such that $|K|=1$ is $|A_1|+|A_2|+|A_3|$, the sum over the sets $K$ such that $|K|=2$ is $-1$ times $|A_1\cap A_2|+|A_2\cap A_3|+|A_3\cap A_1|$, and the sum over the sets $K$ such that $|K|=3$ is $|A_1\cap A_2\cap A_3|$, which is the formula in your post.