# Indicator function

In mathematics, an **indicator function** or a **characteristic function** is a function defined on a set that indicates membership of an element in a subset of .

The indicator function of a subset of a set is a function

defined as

The Iverson bracket allows the notation .

The indicator function of is sometimes denoted

- or or even

(The Greek letter χ because it is the initial letter of the Greek etymon of the word *characteristic*.)

## Remark on notation and terminology

- The notation may signify the identity function.
- The notation may signify the characteristic function in convex analysis.

A related concept in statistics is that of a dummy variable (this must not be confused with "dummy variables" as that term is usually used in mathematics, also called a bound variable).

The term "characteristic function" has an unrelated meaning in probability theory. For this reason, probabilists use the term **indicator function** for the function defined here almost exclusively, while mathematicians in other fields are more likely to use the term **characteristic function** to describe the function which indicates membership in a set.

## Basic properties

Boolos, Burgess, and Jeffrey (2002) define the *characteristic function* as follows:

- "The
*characteristic function*of a k-place relation is the k-argument function that takes the value 1 for a k-tuple if the relation holds of the k-tuple, and the value 0 if it does not; and a relation is*effectively decidable*if its characteristic function is effectively computable, and is*(primitive) recursive*if its characteristic function is (primitive) recursive." (italics in original, p.73–74)

The mapping which associates a subset of to its *indicator function* is injective; its range is the set of functions .

In the following, the "dot" is a sign that represents algebraic multiplication i.e. 1*1 = 1, 1*0 = 0 etc, and likewise the "+" and "-" represent algebraic addition and subtraction. If and are two subsets of , then

and the "complement" of the indicator function of A i.e. A^{C} is:

If the functions A, B and C are Boolean in nature, i.e. they only take on values { 0, 1 } and evaluate to only { 0, 1 } then their indicator functions also evaluate to { 0, 1 }, and the above four formulas represent the logical AND, inclusive-OR, exclusive-OR, and NOT (i.e. logical inverse), respectively.

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.)

## Characteristic function in recursion theory, Gödel's and Kleene's *representing function*

Kurt Gödel described the *representing function* in his 1934 paper "On Undecidable Propositions of Formal Mathematical Systems". (The paper appears on pp. 41-74 in Martin Davis ed. *The Undecidable*):

- "There shall correspond to each class or relation R a representing function φ(x
_{1}, . . ., x_{n}) = 0 if R(x_{1}, . . ., x_{n}) and φ(x_{1}, . . ., x_{n})=1 if ~R(x_{1}, . . ., x_{n})." (p. 42; the "~" indicates logical inversion i.e. "NOT")

Stephen Kleene (1952) (p. 227) offers up the same definition in the context of the primitive recursive functions as a function φ of a predicate P, takes on values 0 if the predicate is true and 1 if the predicate is false.

For example, because the product of characteristic functions φ_{1}*φ_{2}* . . . *φ_{n} = 0 whenever any one of the functions equals 0, it plays the role of logical OR: IF φ_{1}=0 OR φ_{2}=0 OR . . . OR φ_{n}=0 THEN their product is 0. What appears to the modern reader as the representing function's logical-inversion, i.e. the representing function is 0 when the function R is "true" or satisfied", plays a useful role in Kleene's definition of the logical functions OR, AND, and IMPLY (p. 228), the bounded- (p. 228) and unbounded- (p. 279ff) mu operators (Kleene (1952)) and the CASE function (p. 229).

## Characteristic function in fuzzy set theory

In classical mathematics, characteristic functions of sets only take values 1 (members) or 0 (non-members). In fuzzy set theory, characteristic functions are generalized to take value in the real unit interval [0, 1], or more generally, in some algebra or structure (usually required to be at least a poset or lattice). Such generalized characteristic functions are more usually called membership functions, and the corresponding "sets" are called *fuzzy* sets. Fuzzy sets model the gradual change in the membership degree seen in many real-world predicates like "tall", "warm", etc.

## See also

## References

- Folland, G.B.;
*Real Analysis: Modern Techniques and Their Applications*, 2nd ed, John Wiley & Sons, Inc., 1999. - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
*Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 5.2: Indicator random variables, pp.94–99. - Martin Davis ed. (1965),
*The Undecidable*, Raven Press Books, Ltd., New York. - Stephen Kleene, (1952),
*Introduction to Metamathematics*, Wolters-Noordhoff Publishing and North Holland Publishing Company, Netherlands, Sixth Reprint with corrections 1971. - George Boolos, John P. Burgess, Richard C. Jeffrey (2002), Cambridge University Press, Cambridge UK, ISBN 0-521-00758-5.
- Lotfi A. Zadeh, 1965, "Fuzzy sets".
*Information and Control***8**: 338–353. [1] - Joseph Goguen, 1967, "
*L*-fuzzy sets".*Journal of Mathematical Analysis and Applications***18**: 145–174

cs:Charakteristická funkce de:Charakteristische Funktion (Mathematik) it:Funzione indicatrice he:פונקציה מציינת lmo:Funziú caraterístega nl:Indicatorfunctie fi:Indikaattorifunktio