subtraction rule and inclusion-exclusion principle

the subtraction rule

the subtraction rule is like the sum rule, but where some of the ways to do the task in the sets are the same

subtraction rule for 2 sets

the cardinality of the union of 2 sets is the sum of their individual cardinalities, with the cardinality of their intersection subtracted

(A1 ∪ A2) = #A1 + #A2 − #(A1 ∩ A2)

subtraction rule for 3 sets

the cardinality is:

A + #B + #C - (#(A ∩ B) + #(A ∩ C) + #(B ∩ C)) + #(A ∩ B ∩ C)

(all elements) - (repeated elements) + (repeated elements, only once per element)

generalising the subtraction rule (inclusion-exclusion principle)

for the cardinality of the union of n sets -include the cardinalities of the individual sets -exclude the cardinalities of the pairwise intersections -include the cardinalities of three-way intersections -exclude the cardinalities of the four-way intersections … -include the cardinality of the n-way intersection (if n is odd) or exclude it (if n is even)

inclusion-exclusion principle formula