The principle of inclusion and exclusion is essentially a sheaf condition for measures; it allows one to calculate the total measure of a space in terms of a cover. It applies also to cardinality, that is to counting measure?.
Let be a measure space with measure . Typical examples are a probability space or subprobability space, or an arbitrary set with counting measure?. (In the latter case, we may let the measure take values in all cardinal numbers, so that the measure of a subset is its cardinality.)
Now let be a measurable finite cover? of . (That is, we have a finite index set and a function mapping an index in to a measurable subspace of , such that the union of all of these subspaces is all of .) Then given any natural number and any -combination? from (a subset of of cardinality ), let the measure of be , the measure of the intersection of the subspaces assigned to the indexes in . We will call the size of the -combination . Note that for (so ), .
The sum of the measures of the combinations of even size equals the sum of the measures of the combinations of odd size.
If we drop the requirement that be a cover of (that the union of be ), we simply have that is a cover of the actual union of ; the only difference is that the measure of the -combination is now the measure of this union instead of the measure of all of . Then the principle for small values of looks like this:
If subtraction is available (as when is a finite measure), we may solve for the first term on the left (the term from the -combination, that is the measure of the union):
This explains the term ‘inclusion-exclusion’; we are alternately adding (including) and subtracting (excluding) various intersections.
The proof is for all subspaces of a given measure space, by induction on the cardinality of the index set . Although it is atypical, one may take, as one of the basic axioms of a measure, the formula (*), that is the inclusion-exclusion formula (on all measurable subspaces) for ; in any case, this is easy to prove. Then the formula for may be proved by induction. (The formula for is the axiom that the measure of the empty set is zero, and the formula for is trivial.)
The principle applies perfectly well to finitely additive measures (charges) taking values in any abelian monoid. On the other hand, the statement of inclusion-exclusion makes sense even when the cover is not finite; and if we require it whenever is countable, then we force the measure to be countably additive. If we require inclusion-exclusion for arbitrary (even uncountable) , then we get the definition of a normal measure?.
In constructive mathematics, the inclusion-exclusion principle fails in that may satisfy when and are disjoint but (*) fails. On the other hand, we may adopt (*) as the proper clause in the definition of measure. For measures on a Cheng space (which is what we need to employ the usual concepts of measure theory), inclusion-exclusion follows from finite additivity (in the usual sense, for disjoint sets) and the principle that intersection with full sets (which are specified for a Cheng space before any measure is given) preserves measure, so in that sense it makes no difference. But (*) is not valid constructively for cardinality in general; counting measure is a measure constructively only on sets with decidable equality.
In both cases, we see that we can adopt the principle of inclusion-exclusion (which ultimately is motivated by cardinality of finite sets) as the only principle necessary to define what we mean by a measure (although we must already have a measurable space to define it on).