Indicator function

Indicator function

Overview

In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, an indicator function or a characteristic function is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 defined on a set  that indicates membership of an element in a subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

  of , having the value 1 for all elements of A and the value 0 for all elements of X not in A.

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


defined as


The Iverson bracket allows the equivalent notation, , to be used instead of

The function is sometimes denoted or or even just .
Discussion
Ask a question about 'Indicator function'
Start a new discussion about 'Indicator function'
Answer questions from other users
Full Discussion Forum
 
Unanswered Questions
Encyclopedia

In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, an indicator function or a characteristic function is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 defined on a set  that indicates membership of an element in a subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

  of , having the value 1 for all elements of A and the value 0 for all elements of X not in A.

Definition


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


defined as


The Iverson bracket allows the equivalent notation, , to be used instead of

The function is sometimes denoted or or even just . (The Greek letter
Greek alphabet
The Greek alphabet is the script that has been used to write the Greek language since at least 730 BC . The alphabet in its classical and modern form consists of 24 letters ordered in sequence from alpha to omega...

 χ appears because it is the initial letter of the Greek word characteristic.)

Remark on notation and terminology

  • The notation may signify the identity function
    Identity function
    In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...

    .
  • The notation may signify the characteristic function
    Characteristic function (convex analysis)
    In the field of mathematics known as convex analysis, the characteristic function of a set is a convex function that indicates the membership of a given element in that set...

     in convex analysis
    Convex analysis
    Convex analysis is the branch of mathematics devoted to the study of properties of convex functions and convex sets, often with applications in convex minimization, a subdomain of optimization theory....

    .


A related concept in statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....

 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
Free variables and bound variables
In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place...

).

The term "characteristic function
Characteristic function
In mathematics, characteristic function can refer to any of several distinct concepts:* The most common and universal usage is as a synonym for indicator function, that is the function* In probability theory, the characteristic function of any probability distribution on the real line is given by...

" has an unrelated meaning in probability theory
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...

. 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


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
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 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
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

. The notation is used in other places as well, for instance in probability theory
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...

: if is a probability space
Probability space
In probability theory, a probability space or a probability triple is a mathematical construct that models a real-world process consisting of states that occur randomly. A probability space is constructed with a specific kind of situation or experiment in mind...

 with probability measure and is a measurable set
Measure (mathematics)
In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...

, then becomes a random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...

 whose expected value
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

 is equal to the probability of


This identity is used in a simple proof of Markov's inequality
Markov's inequality
In probability theory, Markov's inequality gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant...

.

In many cases, such as order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

, 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
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, the Möbius function
Möbius function
The classical Möbius function μ is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832...

. (See paragraph below about the use of the inverse in classical recursion theory.)

Mean, variance and covariance


Given a probability space
Probability space
In probability theory, a probability space or a probability triple is a mathematical construct that models a real-world process consisting of states that occur randomly. A probability space is constructed with a specific kind of situation or experiment in mind...

  with , the indicator random variable is defined by if otherwise
Mean
Mean
In statistics, mean has two related meanings:* the arithmetic mean .* the expected value of a random variable, which is also called the population mean....

:

Variance
Variance
In probability theory and statistics, the variance is a measure of how far a set of numbers is spread out. It is one of several descriptors of a probability distribution, describing how far the numbers lie from the mean . In particular, the variance is one of the moments of a distribution...

:

Covariance
Covariance
In probability theory and statistics, covariance is a measure of how much two variables change together. Variance is a special case of the covariance when the two variables are identical.- Definition :...

:

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


Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...

 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
Martin Davis
Martin David Davis, is an American mathematician, known for his work on Hilbert's tenth problem . He received his Ph.D. from Princeton University in 1950, where his adviser was Alonzo Church . He is Professor Emeritus at New York University. He is the co-inventor of the Davis-Putnam and the DPLL...

 ed. The Undecidable):
"There shall correspond to each class or relation R a representing function φ(x1, . . ., xn) = 0 if R(x1, . . ., xn) and φ(x1, . . ., xn)=1 if ~R(x1, . . ., xn)." (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 function
Primitive recursive function
The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...

s 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 φ12* . . . *φ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 operator
Mu operator
In computability theory, the μ operator, minimization operator, or unbounded search operator searches for the least natural number with a given property.- Definition :...

s (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
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....

 or structure
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....

 (usually required to be at least a poset
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...

 or lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...

). Such generalized characteristic functions are more usually called membership function
Membership function (mathematics)
The membership function of a fuzzy set is a generalization of the indicator function in classical sets. In fuzzy logic, it represents the degree of truth as an extension of valuation. Degrees of truth are often confused with probabilities, although they are conceptually distinct, because fuzzy...

s, 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

  • Dirac delta
  • Extension (predicate logic)
    Extension (predicate logic)
    The extension of a predicatea truth-valued functionis the set of tuples of values that, used as arguments, satisfy the predicate. Such a set of tuples is a relation.For example the statement "d2 is the weekday following d1"...

  • Free variables and bound variables
    Free variables and bound variables
    In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place...

  • Heaviside step function
    Heaviside step function
    The Heaviside step function, or the unit step function, usually denoted by H , is a discontinuous function whose value is zero for negative argument and one for positive argument....

  • Iverson bracket
  • Kronecker delta, a function that can be viewed as an indicator for the identity relation
  • Multiset
    Multiset
    In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...

  • Membership function
    Membership function (mathematics)
    The membership function of a fuzzy set is a generalization of the indicator function in classical sets. In fuzzy logic, it represents the degree of truth as an extension of valuation. Degrees of truth are often confused with probabilities, although they are conceptually distinct, because fuzzy...

  • Simple function
    Simple function
    In the mathematical field of real analysis, a simple function is a real-valued function over a subset of the real line which attains only a finite number of values...