Indicator function

From Example Problems
Jump to navigation Jump to search

In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X.

Remark. The term "characteristic function" has an unrelated meaning in probability theory; see characteristic function.

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_A : X \to \lbrace 0,1 \rbrace}

defined as

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_A(x) = \left\{\begin{matrix} 1 &\mbox{if}\ x \in A \\ 0 &\mbox{if}\ x \notin A \end{matrix}\right. }

The indicator function of A is sometimes denoted

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \chi_A(x)} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ I_A(x)} or even Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A(x).}

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

The Iverson bracket allows the notation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [x \in A]} .

Warning. The notation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_A } may signify the identity function.

Basic properties

The mapping which associates a subset A of X to its indicator function 1A is injective; its range is the set of functions f:X →{0,1}.

If A and B are two subsets of X, then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_{A\cap B} = \min\{1_A,1_B\} = 1_A 1_B,\,}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_{A\cup B} = \max\{{1_A,1_B}\} = 1_A + 1_B - 1_A 1_B,}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_{A\triangle B} = 1_A + 1_B - 2(1_{A\cap B}),}

and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_{A^\complement} = 1-1_A. }

More generally, suppose A1, ..., An is a collection of subsets of X. For any xX,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{k \in I} ( 1 - 1_{A_k}(x))}

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{k \in I} ( 1 - 1_{A_k}) = 1_{X - \bigcup_{k} A_k} = 1 - 1_{\bigcup_{k} A_k}}

Expanding the product on the left hand side,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_{\bigcup_{k} A_k}= 1 - \sum_{F \subseteq \{1, 2, \ldots, n\}} (-1)^{|F|} 1_{\bigcap_F A_k} = \sum_{\emptyset \neq F \subseteq \{1, 2, \ldots, n\}} (-1)^{|F|+1} 1_{\bigcap_F A_k} }

where |F| is the cardinality of F. 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 X is a probability space with probability measure P and A is a measurable set, then 1A becomes a random variable whose expected value is equal to the probability of A:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(1_A)= \int_{X} 1_A(x)\,dP = \int_{A} dP = P(A).\quad }

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

References

  • Folland, G.B.; Real Analysis: Modern Techniques and Their Applications, 2nd ed, John Wiley & Sons, Inc., 1999.

See also


This article incorporates material from Characteristic function on PlanetMath, which is licensed under the GFDL.

de:Charakteristische Funktion (Mathematik) it:Funzione indicatrice zh:指示函数