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.)
Read more about this topic: Indicator Function
Famous quotes containing the words basic and/or properties:
“It is a strange fact that freedom and equality, the two basic ideas of democracy, are to some extent contradictory. Logically considered, freedom and equality are mutually exclusive, just as society and the individual are mutually exclusive.”
—Thomas Mann (1875–1955)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)