On the characteristic function of a collection of sets

Abstract

The union of a collection of $n$ sets is generally expressed in terms of a characteristic (indicator) function that contains $2^n-1$ terms. In this article, a much simpler expression is found that requires the evaluation of $n$ terms only. This leads to a major simplification of any normal form involving characteristic functions of sets. The formula can be useful in recognizing inclusion-exclusion patterns of combinatorial problems.

11 pages, 1 figure