|
[[Image:Indicator function illustration.png|right|thumb|A three-dimensional plot of an indicator function, shown over a square two-dimensional ___domain (set {{mvar|X}}): the "raised" portion overlays those two-dimensional points which are members of the "indicated" subset ({{mvar|A}}).]]
In [[mathematics]], an '''indicator function''' or a '''characteristic function''' of a [[subset]] of a [[Set (mathematics)|set]] is a [[Function (mathematics)|function]] that maps elements of the subset to one, and all other elements of the set to zero. The indicator function of a subset
{{mvar|A}} of a set {{mvar|X}} maps {{mvar|X}} to the two-element set <math>\{ 0, 1 \}\,;</math>; <math>\mathbf{1}_{A}(x)=1</math> if an element <math>x</math> in {{mvar|X}} belongs to {{mvar|A}}, and <math>\mathbf{1}_{A}(x)=0</math> if <math>x</math> does not belong to {{mvar|A}}. It may be denoteed as <math>\mathbf{1}_A,</math>, by <math>I_A,</math>, or by <math>\chi_A.</math>
The [[Dirichlet function]], the indicator function of the [[rational number]]s as a subset of the [[real number]]s, is an example of an indicator function.
The indicator function of a subset {{mvar|A}} of a set {{mvar|X}} is a function
:<math display=block>\mathbf{1}_A \colon X \to \{ 0, 1 \} </math>
defined as
:<math display=block>\mathbf{1}_A(x) :=
\begin{cases}
1 ~&\text{ if }~ x \in A~, \\
</math>
The [[Iverson bracket]] provides the equivalent notation, <math>[x\in A]</math> or {{nowrap|{{math|⧙ ''x'' ϵ ''A'' ⧘}},}} to be used instead of <math>\mathbf{1}_{A}(x)\,.</math>.
The function <math>\mathbf{1}_A</math> is sometimes denoted {{mvar|I<mathsub>I_AA</mathsub>}}, {{mvar|χ<mathsub>\chi_AA</mathsub>}}, {{mvar|K}}<sub>{{mvar|A}}</sub>}}, or even just <math>{{mvar|A</math>}}.{{efn|name=χαρακτήρ|The [[Greek alphabet|Greek letter]] <math>\{{mvar|&chi</math>;}} appears because it is the initial letter of the Greek word ''{{lang|grc|χαρακτήρ''}}, which is the ultimate origin of the word ''characteristic''.}}{{efn|The set of all indicator functions on {{mvar|X}} can be identified with <math>\mathcal{P}(X),</math>, the [[power set]] of {{mvar|X}}. Consequently, both sets are sometimes denoted by <math>2^X.</math>. This is a special case (<math>Y = \{0,1\} = 2</math>) of the notation <math>Y^X</math> for the set of all functions <math>f:X \to Y .</math>.}}
==Notation and terminology==
==Basic properties==
The ''indicator'' or ''characteristic'' [[function (mathematics)|function]] of a subset {{mvar|A}} of some set {{mvar|X}} [[Map (mathematics)|maps]] elements of {{mvar|X}} to the [[Range of a function|range]] {{closed-closed|0, 1}}.
This mapping is [[surjective]] only when {{mvar|A}} is a non-empty [[proper subset]] of {{mvar|X}}. If {{mvar|<math>A}} ≡\equiv {{mvar|X}},</math> then '''1'''<submath>\mathbf{{mvar|A}1}_A=1.</submath> = 1. By a similar argument, if {{mvar|<math>A}}\equiv\emptyset</math> ≡then ∅ then '''1'''<submath>\mathbf{{mvar|A}1}_A=0.</submath> = 0.
In the following, the dot represents multiplication, <math>1·1\cdot1 = 1,</math> <math>1·0\cdot0 = 0,</math> etc. "+" and "−−" represent addition and subtraction. "<math>\cap </math>" and "<math>\cup </math>" is intersection and union, respectively.
If <math>A</math> and <math>B</math> are two subsets of <math>X ,</math> , then ▼<math display=block>\begin{align}
:<math>\mathbf{1}_{A\cap B} = \min\{\mathbf{1}_A,\mathbf{1}_B\} = \mathbf{1}_A \cdot\mathbf{1}_B, </math> \\▼:<math>\mathbf{1}_{A\cup B} = \max\{{\mathbf{1}_A,\mathbf{1}_B}\} = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \cdot\mathbf{1}_B, </math>▼\end{align}</math>
▲If <math>A</math> and <math>B</math> are two subsets of <math>X</math>, then
▲:<math>\mathbf{1}_{A\cap B} = \min\{\mathbf{1}_A,\mathbf{1}_B\} = \mathbf{1}_A \cdot\mathbf{1}_B,</math>
▲:<math>\mathbf{1}_{A\cup B} = \max\{{\mathbf{1}_A,\mathbf{1}_B}\} = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \cdot\mathbf{1}_B,</math>
and the indicator function of the [[Complement (set theory)|complement]] of <math>A</math> i.e. <math>A^C</math> is:
:<math display=block>\mathbf{1}_{A^\complement} = 1-\mathbf{1}_A.</math>.
More generally, suppose <math>A_1, \dotsc, A_n</math> is a collection of subsets of {{mvar|X}}. For any <math>x \in X:</math>:
:<math display=block> \prod_{k \in I} ( 1 - \mathbf{1}_{A_k}(x))</math>
is clearly a product of 0s{{math|0}}s and 1s{{math|1}}s. This product has the value 1 at precisely those <math>x \in X</math> that belong to none of the sets <math>A_k</math> and is 0 otherwise. That is
:<math display=block> \prod_{k \in I} ( 1 - \mathbf{1}_{A_k}) = \mathbf{1}_{X - \bigcup_{k} A_k} = 1 - \mathbf{1}_{\bigcup_{k} A_k}.</math>
Expanding the product on the left hand side,
: <math display=block> \mathbf{1}_{\bigcup_{k} A_k}= 1 - \sum_{F \subseteq \{1, 2, \dotsc, n\}} (-1)^{|F|} \mathbf{1}_{\bigcap_F A_k} = \sum_{\emptyset \neq F \subseteq \{1, 2, \dotsc, n\}} (-1)^{|F|+1} \mathbf{1}_{\bigcap_F A_k} </math>
where <math>|F|</math> is the [[cardinality]] of {{mvar|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 {{mvar|X}} is a [[probability space]] with probability measure <math>\operatorname{P}</math> and {{mvar|A}} is a [[Measure (mathematics)|measurable set]], then <math>\mathbf{1}_A</math> becomes a [[random variable]] whose [[expected value]] is equal to the probability of {{mvar|A}}:
:<math display=block>\operatorname{E}(\mathbf{1}_A)= \int_{X} \mathbf{1}_A(x)\,d\operatorname{P} = \int_{A} d\operatorname{P} = \operatorname{P}(A).</math>.
This identity is used in a simple proof of [[Markov's inequality]].
==Mean, variance and covariance==
Given a [[probability space]] <math>\textstyle (\Omega, \mathcal F, \operatorname{P})</math> with <math>A \in \mathcal F,</math>, the indicator random variable <math>\mathbf{1}_A \colon \Omega \rightarrow \mathbb{R}</math> is defined by <math>\mathbf{1}_A (\omega) = 1 </math> if <math> \omega \in A,</math> otherwise <math>\mathbf{1}_A (\omega) = 0.</math>
;[[Mean]]: <math>\operatorname{E}(\mathbf{1}_A (\omega)) = \operatorname{P}(A) </math> (also called "Fundamental Bridge").
==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 "¬" indicates logical inversion, i.e. "NOT"):<ref name=Martin-1965>{{cite book |pages=41–74 |editor-link=Martin Davis (mathematician) |editor-first=Martin |editor-last=Davis |year=1965 |title=The Undecidable |publisher=Raven Press Books |place=New York, NY}}</ref>{{rp|page=42}}
:"There shall correspond to each class or relation {{mvar|R}} a representing function φ({{mvar|x}}<sub>1</sub>, ... {{mvar|x}}<sub>n</sub>) = 0 if {{mvar|R}}({{mvar|x}}<sub>1</sub>, ... {{mvar|x}}<sub>n</sub>) and φ({{mvar|x}}<sub>1</sub>, ... {{mvar|x}}<sub>n</sub>) = 1 if ¬{{mvar|R}}({{mvar|x}}<sub>1</sub>, ... {{mvar|x}}<sub>n</sub>)."<ref name=Martin-1965/>{{rp|page= 42}}(the "¬" indicates logical inversion, i.e. "NOT")
{{blockquote|1=There shall correspond to each class or relation {{mvar|R}} a representing function <math>\phi(x_1, \ldots x_n) = 0</math> if <math>R(x_1,\ldots x_n)</math> and <math>\phi(x_1,\ldots x_n) = 1</math> if <math>\neg R(x_1,\ldots x_n).</math>}}
[[Stephen Kleene|Kleene]] (1952)offers up the same definition in the context of the [[primitive recursive function]]s as a function {{mvar|φ}} of a predicate {{mvar|P}} takes on values {{math|0}} if the predicate is true and {{math|1}} if the predicate is false.<ref name=Kleene1952>{{cite book |last=Kleene |first=Stephen |author-link=Stephen Kleene |year=1971 |orig-year=1952 |title=Introduction to Metamathematics |page=227 |publisher=Wolters-Noordhoff Publishing and North Holland Publishing Company |___location=Netherlands |edition=Sixth reprint, with corrections}}</ref> offers up the same definition in the context of the [[primitive recursive function]]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 φ<sub>1</submath>\phi_1 *φ<sub>2</sub> \phi_2 * ...\cdots *φ<sub>n</sub> \phi_n = 0</math> whenever any one of the functions equals {{math|0}}, it plays the role of logical OR: IF φ<sub>1</submath>\phi_1 = 0</math> OR φ<sub>2</submath>\phi_2 = 0</math> OR ... OR φ<sub>n</submath>\phi_n = 0</math> THEN their product is {{math|0}}. What appears to the modern reader as the representing function's logical inversion, i.e. the representing function is {{math|0}} when the function {{mvar|R}} is "true" or satisfied", plays a useful role in Kleene's definition of the logical functions OR, AND, and IMPLY,<ref (p.name=Kleene1952 />{{rp|228),}} the bounded-<ref (p.name=Kleene1952 />{{rp|228)}} and unbounded-<ref (p.name=Kleene1952 />{{rp|279 ff)}} [[mu operator]]s (Kleene (1952)) and the CASE function (p. <ref name=Kleene1952 />{{rp|229).}}
==Characteristic function in fuzzy set theory==
In classical mathematics, characteristic functions of sets only take values {{math|1}} (members) or {{math|0}} (non-members). In ''[[fuzzy set theory]]'', characteristic functions are generalized to take value in the real unit interval [{{closed-closed|0, 1]}}, or more generally, in some [[universal algebra|algebra]] or [[structure (mathematical logic)|structure]] (usually required to be at least a [[partially ordered set|poset]] or [[lattice (order)|lattice]]). Such generalized characteristic functions are more usually called [[membership function (mathematics)|membership function]]s, and the corresponding "sets" are called ''fuzzy'' sets. Fuzzy sets model the gradual change in the membership [[degree of truth|degree]] seen in many real-world [[predicate (mathematics)|predicate]]s like "tall", "warm", etc.
==Derivatives of the indicator function==
{{Main|Laplacian of the indicator}}
A particular indicator function is the [[Heaviside step function]]. The Heaviside step function {{mvarmath|''H}}''({{mvar|''x'')}}) is the indicator function of the one-dimensional positive half-line, i.e. the ___domain {{closed-open|0, ∞}}. The [[distributional derivative]] of the Heaviside step function is equal to the [[Dirac delta function]], i.e.
:<math display=block>\delta(x)=\tfrac{d H(x)}{dx}</math>
with the following property:
:<math display=block>\int_{-\infty}^\infty f(x) \, \delta(x) dx = f(0).</math>
The derivative of the Heaviside step function can be seen as the ''inward normal derivative'' at the ''boundary'' of the ___domain given by the positive half-line. In higher dimensions, the derivative naturally generalises to the inward normal derivative, while the Heaviside step function naturally generalises to the indicator function of some ___domain {{mvar|D}}. The surface of {{mvar|D}} will be denoted by {{mvar|S}}. Proceeding, it can be derived that the [[Laplacian of the indicator#Dirac surface delta function|inward normal derivative of the indicator]] gives rise to a 'surface delta function', which can be indicated by {{<math|''δ''<sub>''S''</sub>\delta_S('''''\mathbf{x'''''})}}:</math>
:<math display=block>\delta_S(\mathbf{x}) = -\mathbf{n}_x \cdot \nabla_x\mathbf{1}_{\mathbf{x}\in D}</math>
where ''{{mvar|n''}} is the outward [[Normal (geometry)|normal]] of the surface ''{{mvar|S''}}. This 'surface delta function' has the following property:<ref>{{cite journal |last=Lange |first=Rutger-Jan |year=2012 |title=Potential theory, path integrals and the Laplacian of the indicator |journal=Journal of High Energy Physics |volume=2012 |issue=11 |pages=29–30 |arxiv=1302.0864 |bibcode=2012JHEP...11..032L |doi=10.1007/JHEP11(2012)032|s2cid=56188533 }}</ref>
:<math display=block>-\int_{\R^n}f(\mathbf{x})\,\mathbf{n}_x\cdot\nabla_x\mathbf{1}_{\mathbf{x}\in D}\;d^{n}\mathbf{x} = \oint_{S}\,f(\mathbf{\beta})\;d^{n-1}\mathbf{\beta}.</math>
By setting the function ''{{mvar|f''}} equal to one, it follows that the [[Laplacian of the indicator#Dirac surface delta function|inward normal derivative of the indicator]] integrates to the numerical value of the [[surface area]] ''{{mvar|S''}}.
==See also==
| 