Inclusion-exclusion principle: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Josy Shewell Brockway
No edit summary
imported>Todd Coles
(subpages)
Line 1: Line 1:
{{subpages}}
The '''inclusion-exclusion principle''' is a [[theorem]] of [[set theory]] relating to the [[cardinality]] of a set defined as the [[union (mathematics)]] of a finite, or at most [[countable]], collection of sets. The general form of the theorem for a collection <math>{A_1,\cdots,A_n}</math> is <math>|A_1\cup\cdots\cup A_n|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\sum_{1\leq i<j<k\leq n}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|</math>. This may be explained intuitively by stating that if we simply take as the cardinality of the union the sum of the cardinalities of the constituent sets, then we have counted those elements that lie in more than one of those sets more than once, so we subtract the sum of the cardinalities of two-way intersections. However, now we have subtracted those elements contained in three or more sets too many times, so we have to add back the sum of the three-way intersections. This creates an overcount once again, and so we continue, alternating sign as we go, until we reach the intersection of all of the sets in the collection. In the case of a countably infinite collection of sets, we never actually reach this final stage; rather, it is a [[limit (mathematics)|limiting]] case.
The '''inclusion-exclusion principle''' is a [[theorem]] of [[set theory]] relating to the [[cardinality]] of a set defined as the [[union (mathematics)]] of a finite, or at most [[countable]], collection of sets. The general form of the theorem for a collection <math>{A_1,\cdots,A_n}</math> is <math>|A_1\cup\cdots\cup A_n|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\sum_{1\leq i<j<k\leq n}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|</math>. This may be explained intuitively by stating that if we simply take as the cardinality of the union the sum of the cardinalities of the constituent sets, then we have counted those elements that lie in more than one of those sets more than once, so we subtract the sum of the cardinalities of two-way intersections. However, now we have subtracted those elements contained in three or more sets too many times, so we have to add back the sum of the three-way intersections. This creates an overcount once again, and so we continue, alternating sign as we go, until we reach the intersection of all of the sets in the collection. In the case of a countably infinite collection of sets, we never actually reach this final stage; rather, it is a [[limit (mathematics)|limiting]] case.
[[Category:CZ Live]]
[[Category:Stub Articles]]
[[Category:Mathematics Workgroup]]

Revision as of 19:41, 7 April 2009

This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

The inclusion-exclusion principle is a theorem of set theory relating to the cardinality of a set defined as the union (mathematics) of a finite, or at most countable, collection of sets. The general form of the theorem for a collection is . This may be explained intuitively by stating that if we simply take as the cardinality of the union the sum of the cardinalities of the constituent sets, then we have counted those elements that lie in more than one of those sets more than once, so we subtract the sum of the cardinalities of two-way intersections. However, now we have subtracted those elements contained in three or more sets too many times, so we have to add back the sum of the three-way intersections. This creates an overcount once again, and so we continue, alternating sign as we go, until we reach the intersection of all of the sets in the collection. In the case of a countably infinite collection of sets, we never actually reach this final stage; rather, it is a limiting case.