This level-5 vital article is ratedC-class on Wikipedia'scontent assessment scale. It is of interest to the followingWikiProjects:

MathematicsMid‑priority This article is within the scope ofWikiProject Mathematics, a collaborative effort to improve the coverage ofmathematics on Wikipedia. If you would like to participate, please visit the project page, where you can jointhe discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated asMid-priority on theproject's priority scale.

QUOTE

"... is an equation relating the sizes of two sets and their union. It states that if A and B are two (finite) sets, then

   |A \cup B| = |A| + |B| - |A \cap B|. \,

The meaning of the statement is that the number of elements in the union of the two sets is the sum of the elements in each set, respectively, minus the number of elements that are in both. Similarly, for three sets A, B and C,"ENDQUOTE

Sets don't have a size, they have a number of members - also known as cardinality, the cardinality of the union of two sets is NOT the sum of the elements in each set.... that would give another set, not a number. Mathematics is the area above all of human achievement where clarity of thought is most necessary and most refined. Who are the people who take it upon themselves to write articles about mathematical subjects, when they don't have the ability to distinguish the elements of the set from the number of those elements. Many many articles in the encyclopedia suffer from this kind of ineptness. If they stopped and left it to those better equipped the article count would increase more slowly, yet the readers would be more enlightened, there would be more silk purses and there would be fewer sows ears.

— Precedingunsigned comment added by82.0.89.176 (talk)23:30, 7 February 2013 (UTC)[reply]

This is very confusing. How about some examples.

agreed - examples of probability calculations would be very helpfulNew Thought (talk)13:43, 25 March 2009 (UTC)[reply]

I added an example for the overall principle of inclusion / exclusion based on a deck of cards. Someone might want to add internal links.Antares5245 (talk)02:22, 15 May 2009 (UTC)[reply]

The new section repeatedly had

${\displaystyle -1^p}$

where

${\displaystyle (-1{)}^p}$

appeared to be intended. Those are of course two different things. I hope I've fixed all of those.Michael Hardy (talk)02:41, 15 May 2009 (UTC)[reply]

You are correct, thank you.Antares5245 (talk)02:46, 15 May 2009 (UTC)[reply]

The way the formula is written at the moment, doesn't,${\displaystyle \sum _{i,j:i\ne j}\left|A_i\cap A_j\right|}$ count everything twice (and so on for the other terms)? Would it be correct to write it as ? I think I don't understand this well enough to change the article...

Note the sign changes --CSTAR 19:18, 5 Jun 2005 (UTC)

The notation${\displaystyle \sum _{i,j:i\ne j}\left|A_i\cap A_j\right|}$ in this context does not mean the set of allordered pairs (i,j). It does not say${\displaystyle \sum _i\sum _j}$, i.e. we don't havej running from 1 throughn separately for each fixed value ofi.Michael Hardy 01:48, 6 Jun 2005 (UTC)

Ah, I entirely missed the point of the reader's confusion.--CSTAR

This proof is horrifically obtuse - is there a more intuitive (but still algebraic) one?

Suppose the pointi is ink of the sets. The first term counts itk times, the second subtracts it${\displaystyle (\genfrac{}{}{0ex}{}{k}{2})}$ times, the third adds it${\displaystyle (\genfrac{}{}{0ex}{}{k}{3})}$ times, and so on. So the total number of times it is counted is

${\displaystyle k-(\genfrac{}{}{0ex}{}{k}{2})+(\genfrac{}{}{0ex}{}{k}{3})-\cdots }$

which is the binomial expansion for${\displaystyle 1-(1-1{)}^k=1}$. Thus, each point is counted exactly once. Is that clearer?McKay04:55, 30 May 2006 (UTC)[reply]

I would say that in the actual version of the article there is only a equivalent formulation of the problem but no proof. Above there is correctly given a proof for the inclusion-exclusion formula. Alternatively one can argue as follows.

For anyi in the union we have that the number of terms involving${\displaystyle A_i}$ which are even is one less to the number of terms involving${\displaystyle A_i}$ which are odd. The combinatorial proof just says that the numbers of even and odd subesets of any set is the same. So this is in principle exactly the above calculation where the term for the empty set (i.e.${\displaystyle (\genfrac{}{}{0ex}{}{k}{0})}$) is not there.

Maybe one can write it formaly as follows

${\displaystyle \sum _{J\subseteq \{1,...n\}}(-1{)}^{|J|+1}\left|\bigcap _{j\in J}{A}_j\right|=\sum _{J\subseteq \{1,...n\}}(-1{)}^{|J|+1}\sum _{x\in \bigcup A_i:x\in A_j,\mathrm{\forall }j\in J}1=\sum _{x\in \bigcup A_i}\sum _{J\subseteq \{1,...n\}:x\in A_j,\mathrm{\forall }j\in J}(-1{)}^{|J|+1}=0.}$

The inclusion-exclusion formula follows by solving for the term${\displaystyle J=\mathrm{\varnothing }}$

Well maybe it's a little bit complicated to write it in such a manner. At least one should see now the double-counting.

--Zuphilip15:20, 18 April 2007 (UTC)[reply]

Indeed, the definition as given, scares the reader momentarily away from the article. Introducing the topicwith elemantary math, examples, and illustrations is the better approach, in line withMcKay above but with more detailed explanations and examples starting with 2 and 3 sets.Lantonov14:33, 23 October 2007 (UTC)[reply]

I added the parenthesis with the synonym 'sieve principle'; and didn't notice until after saving that I was auto-logged out. Just so that you know whom to blame...JoergenB14:25, 27 September 2006 (UTC)[reply]

I've actually never heard it referred to as the sieve principle, but I am not a combinatorist. I usually associate "sieve" with thesieve of eratosthenes or other number theoretic sieves. Of course these are applications of the inclusion-exclusion principle.--CSTAR15:31, 27 September 2006 (UTC)[reply]

I never heard of it being called the "sieve principle" either. I reverted for now, perhaps the contributor who added that can come up with some references.Oleg Alexandrov (talk)01:39, 28 September 2006 (UTC)[reply]

Combinatorics folks call it the sieve formula quite often. The first example that came up in a search was K. Dohmen, Some remarks on the sieve formula, the Tutte polynomial and Crapo's beta invariant,Aequationes Mathematicae, Volume 60, Numbers 1-2 / August, 2000. Searching for "sieve formula" at scholar.google.com finds other examples too (but not all hits are to inclusion-exclusion).McKay04:01, 4 October 2006 (UTC)[reply]

Another example is in Stanley'sEnumerative Combinatorics, where it is called a sieve method, although it seems to be considered only one of many.Cheeser123:46, 1 April 2007 (UTC)[reply]

Combinatorics people quite often don't call it a sieve method. I find the connection rather strained. Opinions differ as you can see. I edited the language from "is" to "can be viewed as".Zaslav (talk)23:15, 12 May 2022 (UTC)[reply]

The diagram currently for n=4 appears to depict a special case where - labelling the 4 sets going clockwise around the diagram say, A,B,C,D - the number of elements in the intersection of A & C which are not in B or D is zero, and the number of elements in the intersection of B & D not in A or C is also zero. This could lead students to derive alternativeincorrect formulae, such as:

I think the special case diagram is likely to lead to faulty reasoning, and would be better either removed or replaced with something catering for the general case.Stumps (talk)03:35, 27 June 2008 (UTC)[reply]

Maybe using something like? Anyone a better artist?Stumps (talk)05:18, 27 June 2008 (UTC)[reply]

My brain just exploded. I was always told that no "Venn Diagram" could be drawn for n > 3, and yet your picture seems to accomplish it. Perhaps my over-zealous school teachers meant it couldn't be done using only circles, which is indeed true.Austinmohr (talk)04:47, 14 March 2010 (UTC)[reply]

Hi, do you see a particular reason to bound the discussion to probability? It seems to me that a half-way level of generality is not so convenient here after all.In fact, it only forces to repeat everything with a different notation ( P(A) instead of |A|).

My suggestion is to keep the first part with statement and proofs in thefinite cardinality case, and then in a last sectionInclusion–exclusion principle in measure theory just observe that everything holds in general measure spaces (so in particular for probability measures): this way we don't either need to change notation,because |A| for a general measure is standard.

Notice also that the measure theoretic setting also includes cases with a somehow more direct visual appeal (subsets in R^2 etc), than examples in Probability.

Another thing:

I would like the case ofregular intersections,

${\displaystyle |\bigcup _{i=1}^n{A}_i|=\sum _{k=1}^n(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k})a_k.}$

to be also stated in this form

${\displaystyle |S\setminus \bigcup _{i=1}^n{A}_i|=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})a_k.}$

which is of common use in combinatorics and somehow nicer. --PMajer (talk)12:51, 30 October 2008 (UTC)[reply]

Of course, the inclusion-exclusion principle could be stated right away as a result from measure theory. The combinatorics formula follows by using the counting measure, the probability version by using a probability measure. However, counting is a very easy concept, so the article should start this way. Next, every element of the sets can be given a weight, which easily leads to the concept of probability (in the case of a countable probability space). Often, introductory courses in probability are taught without using measure theory. Therefore, these readers can understand the formula in this case. For those familiar with measure theory - well, they don't really need this article anyway. In conclusion, I prefer the repetition for easy reading. Note that there is a common, joint proof for all the cases.

On the other hand, you have a point by mentioning the direct visual appeal concerning area in the plane. If you can rewrite the article accordingly without scaring away those unfamiliar with measurable spaces and measurable sets, go ahead!

If you like the other representation in the case of regular intersections, feel free to mention it in the article.Schmock (talk)22:52, 30 October 2008 (UTC)[reply]

You might want to take a look at the approach given inInclusion-Exclusion Principle inProofWiki (a fast-growing baby sibling of this one).

The emphasis here is on thegeneral additive function, which automatically takes on board the counting function and the probability measure (in fact, any measure you care to consider).

The proof itself is inductive and purely algebraic, in that it does not use anything more complicated than an (admittedly) intuitive appeal to "all subsets of order${\displaystyle s}$ out of${\displaystyle \left\{1,2,\dots ,r\right\}}$" in order to get the correct sum of the contributions of the intersections of${\displaystyle s}$ subsets of${\displaystyle r}$.

IMO it's easier to follow (well I would think that, I wrote it). --WestwoodMatt (talk)07:46, 3 March 2010 (UTC)[reply]

This article illustrates the principle and gives an example, but to be honest I don't think your average wikipedia reader will understand it. Is it possible to illustrate a principle like this in a purely written format using examples? I'm not saying remove the mathematics, just that some sort of written explanation would make it an awful lot more readable for a general audience.

At present this is as close to a written explanation as we are given:

"The meaning of the statement is that the number of elements in the union of the two sets is the sum of the elements in each set, respectively, minus the number of elements that are in both."

What this statement is saying appears quite simple to me, it's just written in a way that is likely to promote confusion amongst those without a background in mathematics. It would also help immensely if it were followed up with an example (I know there is an example further down, but this is an example of a calculation, not a simple example of what the above statement actually means). I know this seems like dumbing down the article, but surely the key goal should be to communicate the information to as many people as possible.

Personally, I don't have the writing ability nor knowledge to do a good job of this. I'm commenting here in the hope someone else can furnish a solution.Blankfrackis (talk)14:10, 15 December 2010 (UTC)[reply]

How about the following: To find the probability of the union of several events,

i.include the probability of the events,

ii.exclude the probabilities of the pairwise intersections,

iii.include the probabilities of the triplewise intersections,

iv.exclude the probabilities of the 4×wise intersections,

v.include the probabilities of the 5×wise intersections,

vi.and continue.

Ijon Tichy x2 (talk)07:47, 30 March 2013 (UTC)[reply]

I am almost finished with my refactoring of this article. I've expanded the lead to make it readable, clarified the statement of the principle, talked about special cases and generalizations and vastly expanded the list of applications. I am now moving on to improve some of the mathematical writing. Before tackling the proofs (which I have moved to the end of the article, where they belong) I want to redo the section on Möbius inversion (titled "Other forms" - that will be changed!). My usual modus operandi is to leave as much of what previous editors have contributed alone and build up the section with small corrections and changes. I especially don't like to touch referenced material that I don't have access to. In this section however, I feel that I need to make some major changes. The statement of the result is not accurate, the presentation leaves much to be desired and the emphasis seems a bit skewed. This may not be the fault of the editor, but rather the reference that was used. I am planning on replacing the reference with something a bit more mainstream as I redo the section and I am afraid that not much of what is currently there will survive. Any comments before I do this?Bill Cherowitzo (talk)03:25, 1 April 2013 (UTC)[reply]

The "Alternative proof" at the end is essentially exactly the same as the "First possibility" under "Proof". I could redo this, but might be better if someone familiar with the page did.Thanks!Natkuhn (talk)02:56, 22 December 2014 (UTC)[reply]

Sorry, I meant to do this last year but it kinda fell off my radar. I'll put the algebraic proof back in a few days after I polish it up a bit.Bill Cherowitzo (talk)19:38, 22 December 2014 (UTC)[reply]

The text (in the introductory part) says "This concept is attributed to Abraham de Moivre (1718);[1] but it first appears in a paper of Daniel da Silva (1854),[2] and later in a paper by J. J. Sylvester (1883).[3]"

But 1718 is long before 1854, so what does this text mean? Did de Moivre not actually write about the principle but people cite him anyway for some reason? Or is it just a mistake with the dates? It's hard to tell because de Moivre (1718) isn't actually listed in the references.Nathaniel Virgo (talk)09:17, 2 July 2018 (UTC)[reply]

The statement in Roberts and Tesman is that de Moivre wrote the principle in another form. They then reference this to his book,The Doctrine of Chances, privately printed in London in 1718. The form of the principle as stated in this article can be traced back to da Silva and Sylvester. --Bill Cherowitzo (talk)17:23, 2 July 2018 (UTC)[reply]

To count the number of elements in exactly${\displaystyle k}$ sets, the coefficient for the intersection of${\displaystyle m}$ sets is${\displaystyle (-1{)}^{m+k}(\genfrac{}{}{0ex}{}{m}{k})}$

In the normal case this results in coefficients 1, -1, 1, -1, ...

For elements in exactly 1 set this is 0, 1, -2, 3, -4, ...

For elements in exactly 2 sets this is 0, 0, 1, -3, 6, -10, ...

I believe this result is in textbooks but it's strangely hard to find it on the internet. I don't have a proof though so this result and the proof should be added to the article.Wqwt (talk)06:47, 20 August 2018 (UTC)[reply]

I just found it here with referencehttps://math.stackexchange.com/questions/1808129/generalised-inclusion-exclusion-principleWqwt (talk)—Precedingundated comment added07:07, 20 August 2018 (UTC)[reply]

By Samuel Monnier - Own work (low res file), CC BY-SA 3.0,https://commons.wikimedia.org/w/index.php?curid=8481291— Precedingunsigned comment added byNoosphericus (talk •contribs)19:55, 28 December 2018 (UTC)[reply]

"where the last sum runs over all subsets I of the indices 1, ..., n which contain exactly k elements, and .."

no: I runs over all n-uples.. etc. Please amend--Federicolo (talk)13:37, 1 January 2021 (UTC)[reply]

I don't have a reference for this, but it consistently works in Excel. p(at least one of 5 independent events) = p on each trial*5 - pr(event occurs 2 times) - 2pr(3 times) - 3pr(4 times) - 4pr(5 times). Etc. for any number of events.This works by correcting for double counting. It clearly works for exactly 2 events but I had to play with it to get it to work for more than 2.Does somebody have a reference and is this worth adding to this page?Ed Gracely (talk)Ed Gracely (talk)14:43, 14 June 2024 (UTC)[reply]

• C-Class level-5 vital articles
• Wikipedia level-5 vital articles in Mathematics
• C-Class vital articles in Mathematics
• C-Class mathematics articles
• Mid-priority mathematics articles

• All Wikipedia vital articles