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:
“Southerners, whose ancestors a hundred years ago knew the horrors of a homeland devastated by war, are particularly determined that war shall never come to us again. All Americans understand the basic lessons of history: that we need to be resolute and able to protect ourselves, to prevent threats and domination by others.”
—Jimmy Carter (James Earl Carter, Jr.)
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)