Indicator Function - Basic Properties

Basic Properties

The indicator or characteristic function of a subset of some set, maps elements of to the range .

This mapping is surjective only when is a non-empty proper subset of . If, then . By a similar argument, if then .

In the following, the dot represents multiplication, 1·1 = 1, 1·0 = 0 etc. "+" and "−" represent addition and subtraction. "" and "" is intersection and union, respectively.

If and are two subsets of, then

and the indicator function of the complement of A i.e. AC is:

More generally, suppose is a collection of subsets of . For any ,

is clearly a product of s and s. This product has the value 1 at precisely those which belong to none of the sets and is otherwise. That is

Expanding the product on the left hand side,

where is the cardinality of . This is one form of the principle of inclusion-exclusion.

As suggested by the previous example, the indicator function is a useful notational device in combinatorics. The notation is used in other places as well, for instance in probability theory: if is a probability space with probability measure and is a measurable set, then becomes a random variable whose expected value is equal to the probability of

This identity is used in a simple proof of Markov's inequality.

In many cases, such as order theory, the inverse of the indicator function may be defined. This is commonly called the generalized Möbius function, as a generalization of the inverse of the indicator function in elementary number theory, the Möbius function. (See paragraph below about the use of the inverse in classical recursion theory.)