Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Indicator function

From Wikipedia, the free encyclopedia
Mathematical function characterizing set membership
This article is about the 0–1 indicator function. For the 0–infinity indicator function, seecharacteristic function (convex analysis).
This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(December 2009) (Learn how and when to remove this message)

A three-dimensional plot of an indicator function, shown over a square two-dimensional domain (setX): the "raised" portion overlays those two-dimensional points which are members of the "indicated" subset (A).

Inmathematics, anindicator function or acharacteristic function of asubset of aset is afunction that maps elements of the subset to one, and all other elements to zero. That is, ifA is a subset of some setX, then the indicator function ofA is the function1A{\displaystyle \mathbf {1} _{A}} defined by1A(x)=1{\displaystyle \mathbf {1} _{A}\!(x)=1} ifx∈A,{\displaystyle x\in A,} and1A(x)=0{\displaystyle \mathbf {1} _{A}\!(x)=0} otherwise. Other common notations are𝟙A andχA.{\displaystyle \chi _{A}.}[a]

The indicator function ofA is theIverson bracket of the property of belonging toA; that is,

1A(x)=[ x∈A ].{\displaystyle \mathbf {1} _{A}(x)=\left[\ x\in A\ \right].}

For example, theDirichlet function is the indicator function of therational numbers as a subset of thereal numbers.

Definition

[edit]

Given an arbitrary setX, the indicator function of a subsetA ofX is the function1A:X→{0,1}{\displaystyle \mathbf {1} _{A}\colon X\rightarrow \{0,1\}}defined by1A(x)={1if x∈A0if x∉A.{\displaystyle \operatorname {\mathbf {1} } _{A}\!(x)={\begin{cases}1&{\text{if }}x\in A\\0&{\text{if }}x\notin A\,.\end{cases}}}

TheIverson bracket provides the equivalent notation[ x∈A ]{\displaystyle \left[\ x\in A\ \right]} or⟦ x ∈A ⟧, that can be used instead of1A(x).{\displaystyle \mathbf {1} _{A}\!(x).}

The function1A{\displaystyle \mathbf {1} _{A}} is sometimes denoted𝟙A,IA,χA[a] or even justA.[b]

Notation and terminology

[edit]

The notationχA{\displaystyle \chi _{A}} is also used to denote thecharacteristic function inconvex analysis, which is defined as if using thereciprocal of the standard definition of the indicator function.

A related concept instatistics is that of adummy variable. (This must not be confused with "dummy variables" as that term is usually used in mathematics, also called abound variable.)

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

Infuzzy logic andmodern many-valued logic, predicates are thecharacteristic functions of aprobability distribution. That is, the strict true/false valuation of the predicate is replaced by a quantity interpreted as the degree of truth.

Basic properties

[edit]

Theindicator orcharacteristicfunction of a subsetA of some setXmaps elements ofX to thecodomain{0,1}.{\displaystyle \{0,\,1\}.}

This mapping issurjective only whenA is a non-emptyproper subset ofX. IfA=X,{\displaystyle A=X,} then1A≡1.{\displaystyle \mathbf {1} _{A}\equiv 1.} By a similar argument, ifA=∅{\displaystyle A=\emptyset } then1A≡0.{\displaystyle \mathbf {1} _{A}\equiv 0.}

IfA{\displaystyle A} andB{\displaystyle B} are two subsets ofX,{\displaystyle X,} then1A∩B(x) = min{1A(x), 1B(x)}  = 1A(x)⋅1B(x),1A∪B(x) = max{1A(x), 1B(x)} = 1A(x)+1B(x)−1A(x)⋅1B(x),{\displaystyle {\begin{aligned}\mathbf {1} _{A\cap B}(x)~&=~\min {\bigl \{}\mathbf {1} _{A}(x),\ \mathbf {1} _{B}(x){\bigr \}}~~=~\mathbf {1} _{A}(x)\cdot \mathbf {1} _{B}(x),\\\mathbf {1} _{A\cup B}(x)~&=~\max {\bigl \{}\mathbf {1} _{A}(x),\ \mathbf {1} _{B}(x){\bigr \}}~=~\mathbf {1} _{A}(x)+\mathbf {1} _{B}(x)-\mathbf {1} _{A}(x)\cdot \mathbf {1} _{B}(x)\,,\end{aligned}}}

and the indicator function of thecomplement ofA{\displaystyle A} i.e.A∁{\displaystyle A^{\complement }} is:1A∁=1−1A.{\displaystyle \mathbf {1} _{A^{\complement }}=1-\mathbf {1} _{A}.}

More generally, supposeA1,…,An{\displaystyle A_{1},\dotsc ,A_{n}} is a collection of subsets ofX. For anyx∈X:{\displaystyle x\in X:}

∏k∈I( 1−1Ak(x) ){\displaystyle \prod _{k\in I}\left(\ 1-\mathbf {1} _{A_{k}}\!\left(x\right)\ \right)}

is a product of0s and1s. This product has the value1 at precisely thosex∈X{\displaystyle x\in X} that belong to none of the setsAk{\displaystyle A_{k}} and is 0 otherwise. That is

∏k∈I(1−1Ak)=1X−⋃kAk=1−1⋃kAk.{\displaystyle \prod _{k\in I}(1-\mathbf {1} _{A_{k}})=\mathbf {1} _{X-\bigcup _{k}A_{k}}=1-\mathbf {1} _{\bigcup _{k}A_{k}}.}

Expanding the product on the left hand side,

1⋃kAk=1−∑F⊆{1,2,…,n}(−1)|F|1⋂FAk=∑∅≠F⊆{1,2,…,n}(−1)|F|+11⋂FAk{\displaystyle \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}}}

where|F|{\displaystyle |F|} is thecardinality ofF. This is one form of the principle ofinclusion-exclusion.

As suggested by the previous example, the indicator function is a useful notational device incombinatorics. The notation is used in other places as well, for instance inprobability theory: ifX is aprobability space with probability measureP{\displaystyle \mathbb {P} } andA is ameasurable set, then1A{\displaystyle \mathbf {1} _{A}} becomes arandom variable whoseexpected value is equal to the probability ofA:

EX⁡{ 1A(x) } = ∫X1A(x) d P⁡(x)=∫Ad P⁡(x)=P⁡(A).{\displaystyle \operatorname {\mathbb {E} } _{X}\left\{\ \mathbf {1} _{A}(x)\ \right\}\ =\ \int _{X}\mathbf {1} _{A}(x)\ \operatorname {d\ \mathbb {P} } (x)=\int _{A}\operatorname {d\ \mathbb {P} } (x)=\operatorname {\mathbb {P} } (A).}

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

In many cases, such asorder theory, the inverse of the indicator function may be defined. This is commonly called thegeneralized Möbius function, as a generalization of the inverse of the indicator function in elementarynumber theory, theMöbius function. (See paragraph below about the use of the inverse in classical recursion theory.)

Mean, variance and covariance

[edit]

Given aprobability space(Ω,F,P){\displaystyle \textstyle (\Omega ,{\mathcal {F}},\operatorname {P} )} withA∈F,{\displaystyle A\in {\mathcal {F}},} the indicator random variable1A:Ω→R{\displaystyle \mathbf {1} _{A}\colon \Omega \rightarrow \mathbb {R} } is defined by1A(ω)=1{\displaystyle \mathbf {1} _{A}(\omega )=1} ifω∈A,{\displaystyle \omega \in A,} otherwise1A(ω)=0.{\displaystyle \mathbf {1} _{A}(\omega )=0.}

Mean
 E⁡(1A(ω))=P⁡(A) {\displaystyle \ \operatorname {\mathbb {E} } (\mathbf {1} _{A}(\omega ))=\operatorname {\mathbb {P} } (A)\ } (also called "Fundamental Bridge").
Variance
 Var⁡(1A(ω))=P⁡(A)(1−P⁡(A)).{\displaystyle \ \operatorname {Var} (\mathbf {1} _{A}(\omega ))=\operatorname {\mathbb {P} } (A)(1-\operatorname {\mathbb {P} } (A)).}
Covariance
 Cov⁡(1A(ω),1B(ω))=P⁡(A∩B)−P⁡(A)P⁡(B).{\displaystyle \ \operatorname {Cov} (\mathbf {1} _{A}(\omega ),\mathbf {1} _{B}(\omega ))=\operatorname {\mathbb {P} } (A\cap B)-\operatorname {\mathbb {P} } (A)\operatorname {\mathbb {P} } (B).}

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

[edit]

Kurt Gödel described therepresenting function in his 1934 paper "On undecidable propositions of formal mathematical systems" (the symbol "¬" indicates logical inversion, i.e. "NOT"):[1]: 42 

There shall correspond to each class or relationR a representing functionϕ(x1,…xn)=0{\displaystyle \phi (x_{1},\ldots x_{n})=0} ifR(x1,…xn){\displaystyle R(x_{1},\ldots x_{n})} andϕ(x1,…xn)=1{\displaystyle \phi (x_{1},\ldots x_{n})=1} if¬R(x1,…xn).{\displaystyle \neg R(x_{1},\ldots x_{n}).}

Kleene offers up the same definition in the context of theprimitive recursive functions as a functionφ of a predicateP takes on values0 if the predicate is true and1 if the predicate is false.[2]

For example, because the product of characteristic functionsϕ1∗ϕ2∗⋯∗ϕn=0{\displaystyle \phi _{1}*\phi _{2}*\cdots *\phi _{n}=0} whenever any one of the functions equals0, it plays the role of logical OR: IFϕ1=0 {\displaystyle \phi _{1}=0\ } OR ϕ2=0{\displaystyle \ \phi _{2}=0} OR ... ORϕn=0{\displaystyle \phi _{n}=0} THEN their product is0. What appears to the modern reader as the representing function's logical inversion, i.e. the representing function is0 when the functionR is "true" or satisfied", plays a useful role in Kleene's definition of the logical functions OR, AND, and IMPLY,[2]: 228  the bounded-[2]: 228  and unbounded-[2]: 279 ff mu operators and the CASE function.[2]: 229 

Characteristic function in fuzzy set theory

[edit]

In classical mathematics, characteristic functions of sets only take values1 (members) or0 (non-members). Infuzzy set theory, characteristic functions are generalized to take value in the real unit interval[0, 1], or more generally, in somealgebra orstructure (usually required to be at least aposet orlattice). Such generalized characteristic functions are more usually calledmembership functions, and the corresponding "sets" are calledfuzzy sets. Fuzzy sets model the gradual change in the membershipdegree seen in many real-worldpredicates like "tall", "warm", etc.

Smoothness

[edit]
See also:Laplacian of the indicator

In general, the indicator function of a set is not smooth; it is continuous if and only if itssupport is aconnected component. In thealgebraic geometry offinite fields, however, everyaffine variety admits a (Zariski) continuous indicator function.[3] Given afinite set of functionsfα∈Fq[ x1,…,xn]{\displaystyle f_{\alpha }\in \mathbb {F} _{q}\left[\ x_{1},\ldots ,x_{n}\right]} letV={ x∈Fqn:fα(x)=0 }{\displaystyle V={\bigl \{}\ x\in \mathbb {F} _{q}^{n}:f_{\alpha }(x)=0\ {\bigr \}}} be their vanishing locus. Then, the functionP(x)=∏( 1−fα(x)q−1){\textstyle \mathbb {P} (x)=\prod \left(\ 1-f_{\alpha }(x)^{q-1}\right)} acts as an indicator function forV.{\displaystyle V.} Ifx∈V{\displaystyle x\in V} thenP(x)=1,{\displaystyle \mathbb {P} (x)=1,} otherwise, for somefα,{\displaystyle f_{\alpha },} we havefα(x)≠0{\displaystyle f_{\alpha }(x)\neq 0} which implies thatfα(x)q−1=1,{\displaystyle f_{\alpha }(x)^{q-1}=1,} henceP(x)=0.{\displaystyle \mathbb {P} (x)=0.}

Although indicator functions are not smooth, they admitweak derivatives. For example, considerHeaviside step functionH(x)≡I(x>0){\displaystyle H(x)\equiv \operatorname {\mathbb {I} } \!{\bigl (}x>0{\bigr )}} Thedistributional derivative of the Heaviside step function is equal to theDirac delta function, i.e.dH(x)dx=δ(x){\displaystyle {\frac {\mathrm {d} H(x)}{\mathrm {d} x}}=\delta (x)}and similarly the distributional derivative ofG(x):=I(x<0){\displaystyle G(x):=\operatorname {\mathbb {I} } \!{\bigl (}x<0{\bigr )}} isdG(x)dx=−δ(x).{\displaystyle {\frac {\mathrm {d} G(x)}{\mathrm {d} x}}=-\delta (x).}

Thus the derivative of the Heaviside step function can be seen as theinward normal derivative at theboundary 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 domainD. The surface ofD will be denoted byS. Proceeding, it can be derived that the inwardnormal derivative of the indicator gives rise to asurface delta function, which can be indicated byδS(x){\displaystyle \delta _{S}(\mathbf {x} )}:δS(x)=−nx⋅∇xI( x∈D ) {\displaystyle \delta _{S}(\mathbf {x} )=-\mathbf {n} _{x}\cdot \nabla _{x}\operatorname {\mathbb {I} } \!{\bigl (}\ \mathbf {x} \in D\ {\bigr )}\ }wheren is the outwardnormal of the surfaceS. This 'surface delta function' has the following property:[4]−∫Rnf(x)nx⋅∇xI( x∈D )dn⁡x=∮Sf(β)dn−1⁡β.{\displaystyle -\int _{\mathbb {R} ^{n}}f(\mathbf {x} )\,\mathbf {n} _{x}\cdot \nabla _{x}\operatorname {\mathbb {I} } \!{\bigl (}\ \mathbf {x} \in D\ {\bigr )}\;\operatorname {d} ^{n}\mathbf {x} =\oint _{S}\,f(\mathbf {\beta } )\;\operatorname {d} ^{n-1}\mathbf {\beta } .}

By setting the functionf equal to one, it follows that theinward normal derivative of the indicator integrates to the numerical value of thesurface areaS.

See also

[edit]

Notes

[edit]
  1. ^abTheGreek letterχ appears because it is the initial letter of the Greek wordχαρακτήρ, which is the ultimate origin of the wordcharacteristic.
  2. ^The set of all indicator functions onX can be identified with the set operatorP(X),{\displaystyle {\mathcal {P}}(X),} thepower set ofX. Consequently, both sets are denoted by the conventionalabuse of notation as2X,{\displaystyle 2^{X},} in analogy to the relation for the count of elements in the powerset and the original set. This is a special case(Y={0,1}){\displaystyle \left(Y=\{0,\,1\}\right)} of the notationYX{\displaystyle Y^{X}} for the set of all functionsf{\displaystyle f} such thatf:X↦Y.{\displaystyle f:X\mapsto Y\,.}

References

[edit]
  1. ^Davis, Martin, ed. (1965).The Undecidable. New York, NY: Raven Press Books. pp. 41–74.
  2. ^abcdeKleene, Stephen (1971) [1952].Introduction to Metamathematics (Sixth reprint, with corrections ed.). Netherlands: Wolters-Noordhoff Publishing and North Holland Publishing Company. p. 227.
  3. ^Serre.Course in Arithmetic. p. 5.
  4. ^Lange, Rutger-Jan (2012). "Potential theory, path integrals and the Laplacian of the indicator".Journal of High Energy Physics.2012 (11):29–30.arXiv:1302.0864.Bibcode:2012JHEP...11..032L.doi:10.1007/JHEP11(2012)032.S2CID 56188533.

Sources

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Indicator_function&oldid=1310691750"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp