Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
thank you that helps a lot in understand now!!! +1 –  Raynos Mar 21 '12 at 16:43
add comment

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.

share|improve this answer
    
thank you gary. I think I understand where the intersection at the end is coming from. I can do each set and its intersection with the other set separately and then I have a hold left in the center and to cover for that hole I can do intersection of the 3 sets....so its kind of like saying A or B or C is equal to the commonality between A and B, B and C C and A, then you also want to add the commonality that all 3 are the same so you do it like the above equation for that reason –  Raynos Mar 20 '12 at 5:26
    
I edited my post. The new diagram represents what I just said in comments. I hope this helps other people confused, there are ways to solve complex problems in many ways, you can solve them in complex methods or with super simple and easy methods. How you look at the problem is what determines whether you will find a simple easy solution or a complex one. This I have now learned. It is much easier I find to visualize the hole in center as oppose to overlay of the 3 sets intersection. –  Raynos Mar 20 '12 at 5:31
    
darn my "trick" fails if you go for 4 venn diagrams... –  Raynos Mar 20 '12 at 5:42
    
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. –  Gerry Myerson Mar 20 '12 at 6:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.