Характеристична функція

Характеристична функція (індикаторна функція, індикатор) підмножини ${\displaystyle A\subseteq X}$ — функція, визначена на множині ${\displaystyle X}$, яка визначає належність елемента ${\displaystyle x\in X}$ підмножині ${\displaystyle A}$.

Тривимірний графік індикаторної функції, який відображає серповидну двовимірну підмножину ${\displaystyle A}$ двовимірного квадрата — множина ${\displaystyle X}$, де точки ${\displaystyle x\in A}$ мають координату z=1 (колір охри), а точки ${\displaystyle x\notin A}$ квадрата мають координату z=0 (червоний' колір').

Означення

Нехай ${\displaystyle A\subseteq X}$ — деяка підмножина довільної множини ${\displaystyle X}$. Функцію ${\displaystyle \mathbf {1} _{A}:X\to \{0,1\}}$, означену таким чином:

${\displaystyle \mathbf {1} _{A}(x)=\left\{{\begin{matrix}1,&x\in A,\\0,&x\notin A,\end{matrix}}\right.}$

називають характеристичною функцією або індикатором множини ${\displaystyle A}$.

Альтернативними позначеннями індикатора множини ${\displaystyle A}$ є: ${\displaystyle \chi _{A}\,}$ або ${\displaystyle \mathbf {I} _{A}}$, а іноді навіть ${\displaystyle \ A(x)}$. Нотація Айверсона дозволяє позначення ${\displaystyle [x\in A]}$.

(Грецька літера ${\displaystyle \ \chi }$ походить від початкової букви грецького написання слова характеристика.)

Замітка. Позначення ${\displaystyle \mathbf {1} _{A}}$ може означати тотожну функцію.

Основні властивості

Відображення, яке пов'язує підмножину ${\displaystyle A\subseteq X}$ з її індикатором ${\displaystyle \mathbf {1} _{A}}$, є ін'єкцією. Якщо ${\displaystyle A}$ і ${\displaystyle B}$ — дві підмножини ${\displaystyle X\ }$, то

${\displaystyle \mathbf {1} _{A\cap B}=\min\{\mathbf {1} _{A},\mathbf {1} _{B}\}=\mathbf {1} _{A}\mathbf {1} _{B},}$

${\displaystyle \mathbf {1} _{A\cup B}=\max\{{\mathbf {1} _{A},\mathbf {1} _{B}}\}=\mathbf {1} _{A}+\mathbf {1} _{B}-\mathbf {1} _{A}\mathbf {1} _{B},}$

${\displaystyle \mathbf {1} _{A\triangle B}=\mathbf {1} _{A}+\mathbf {1} _{B}-2(\mathbf {1} _{A\cap B}),}$

${\displaystyle \mathbf {1} _{A^{c}}=1-\mathbf {1} _{A}.}$

Загальніше, нехай ${\displaystyle A_{1},\ldots ,A_{n}}$ — множина підмножин ${\displaystyle X}$. Тоді для довільного ${\displaystyle x\in X}$

${\displaystyle \prod _{k\in I}(1-\mathbf {1} _{A_{k}}(x))}$ — добуток нулів та одиниць. Цей добуток набуває значення 1 для тих ${\displaystyle x\in X}$, які не належать жодній множині ${\displaystyle A_{k}}$, і 0 в іншому разі. Тому

${\displaystyle \prod _{k\in I}(1-\mathbf {1} _{A_{k}})=\mathbf {1} _{X-\bigcup _{k}A_{k}}=1-\mathbf {1} _{\bigcup _{k}A_{k}}.}$

Розкладаючи ліву частину, отримуємо

${\displaystyle \mathbf {1} _{\bigcup _{k}A_{k}}=1-\sum _{F\subseteq \{1,2,\ldots ,n\}}(-1)^{|F|}\mathbf {1} _{\bigcap _{F}A_{k}}=\sum _{\emptyset \neq F\subseteq \{1,2,\ldots ,n\}}(-1)^{|F|+1}\mathbf {1} _{\bigcap _{F}A_{k}},}$

де ${\displaystyle |F|}$ — потужність ${\displaystyle F}$. Це — одна з форм запису принципу включення-виключення. Отже, індикатор — корисне позначення в комбінаториці, яке використовують також і в інших областях, наприклад в теорії ймовірностей: якщо ${\displaystyle X}$ — ймовірнісний простір з ймовірнісною мірою ${\displaystyle \mathbf {P} }$, а ${\displaystyle A}$ — вимірна множина, то індикатор ${\displaystyle \mathbf {1} _{A}}$ стає випадковою величиною, чиє математичне очікування дорівнює ймовірності ${\displaystyle A:}$

${\displaystyle E(\mathbf {1} _{A})=\int \limits _{X}\mathbf {1} _{A}(x)\,d\mathbf {P} =\int \limits _{A}d\mathbf {P} =\mathbf {P} (A).\quad }$

Дисперсія та коваріація для цієї випадкової змінної визначаються за формулами:

${\displaystyle \operatorname {Var} (\mathbf {1} _{A}(\omega ))=\operatorname {P} (A)(1-\operatorname {P} (A))}$

${\displaystyle \operatorname {Cov} (\mathbf {1} _{A}(\omega ),\mathbf {1} _{B}(\omega ))=\operatorname {P} (A\cap B)-\operatorname {P} (A)\operatorname {P} (B)}$

Зауваження щодо позначення та термінології

Позначення ${\displaystyle A}$ також використовують для позначення ${\displaystyle \mathbf {X} _{A}}$, ^[en] в (опуклому аналізі), яку означують як обернене до стандартного означення характеристичної функції.

Термін «характеристична функція» має незалежне значення в класичній теорії ймовірностей. З цієї причини ^[en] використовують термін індикаторна функція майже ексклюзивно, тоді як математики в інших областях для опису функції, що вказує на приналежність до множини, використовують скоріше термін характеристична функція.

У нечіткій логіці та сучасній багатозначній логіці предикати є характеристичними функціями розподілу ймовірності. Тобто, строгу істинну/хибну оцінку предикату замінюють величиною, що інтерпретують як степінь істинності.

Середнє значення, дисперсія та коваріація

Для заданого ймовірнісного простору ${\displaystyle \textstyle (\Omega ,{\mathcal {F}},\operatorname {P} )}$, та ${\displaystyle A\in {\mathcal {F}}}$, індикаторну випадкову змінну ${\displaystyle \mathbf {1} _{A}\colon \Omega \rightarrow \mathbb {R} }$ означують як ${\displaystyle \mathbf {1} _{A}(\omega )=1}$, якщо ${\displaystyle \omega \in A,}$, інакше ${\displaystyle \mathbf {1} _{A}(\omega )=0.}$

Середнє значення

${\displaystyle \operatorname {E} (\mathbf {1} _{A}(\omega ))=\operatorname {P} (A)}$.

Дисперсія

${\displaystyle \operatorname {Var} (\mathbf {1} _{A}(\omega ))=\operatorname {P} (A)(1-\operatorname {P} (A))}$.

Коваріація

${\displaystyle \operatorname {Cov} (\mathbf {1} _{A}(\omega ),\mathbf {1} _{B}(\omega ))=\operatorname {P} (A\cap B)-\operatorname {P} (A)\operatorname {P} (B)}$.

Характеристична функція в теорії рекурсії, представляльна функція Геделя та Кліні

Курт Гедель описав представляльну функцію (англ. representing function) у своїй праці 1934 року «Про нерозв'язні твердження формальних математичних систем» (цю працю опубліковано на стор. 41-74 книжки «Нерозв'язне», «The Undecidable», під редагуванням (Мартіна Девіса)):

«Кожному класові чи відношенню ${\displaystyle R}$ повинна відповідати представляльна функція ${\displaystyle \varphi (x_{1},\dots ,x_{n})=0}$ , якщо ${\displaystyle R(x_{1},\dots ,x_{n})}$ та ${\displaystyle \varphi (x_{1},\dots ,x_{n})=1}$, якщо ${\displaystyle \sim R(x_{1},\dots ,x_{n})}$.» (стор. 42; «~» позначує логічне обернення, тобто «НЕ»).

Стівен Кліні (1952) (стор. 227) запропонував таке саме означення в контексті (примітивно-рекурсивних функцій) як функції ${\displaystyle \varphi }$ від предикату ${\displaystyle R}$, що набуває значення ${\displaystyle 0}$, якщо предикат є істинним, та ${\displaystyle 1}$, якщо предикат є хибним.

Наприклад, оскільки добуток характеристичних функцій ${\displaystyle \varphi _{1}\varphi _{2}\cdots \varphi _{n}=0}$, якщо будь-яка з ціх функцій дорівнює ${\displaystyle 0}$, то вона відіграє роль логічного АБО: ЯКЩО ${\displaystyle \varphi _{1}=0}$ АБО ${\displaystyle \varphi _{2}=0}$ АБО . . . АБО ${\displaystyle \varphi _{n}=0}$ ТОДІ їх добуток дорівнює ${\displaystyle 0}$. Те, що видається сучасному читачеві як логічне обернення представляльної функції, тобто, що представляльна функція дорівнює ${\displaystyle 0}$, коли функція ${\displaystyle R}$ є «істинною» чи «вдоволеною», відіграє корисну роль в означенні Кліні логічних функцій «OR», «AND», та «IMPLY» (стор. 228), обмежених (стор. 228) та необмежених (стор. 279 і далі) (μ-операторів) (Кліні, 1952), та функції «CASE» (стор. 229).

Характеристична функція в теорії нечітких множин

В класичній математиці характеристичні функції множин набувають лише значень 1 (елемент) та 0 (не елемент). В (теорії нечітких множин) характеристичні функції узагальнюють до набування значень з дійсного одиничного проміжку [0, 1], або, загальніше, з деякої алгебри або ^[en] (яка зазвичай повинна бути щонайменше частково впорядкованою множиною або ґраткою). Такі узагальнені характеристичні функції частіше називають функціями належності, а відповідні «множини» називаються нечіткими множинами. Нечіткі множини моделюють поступову зміну ^[en], що спостерігається у багатьох предикатів реального світу, таких як «високий», «теплий» тощо.

Примітки

1. representing // Англійсько-український словник з математики та інформатики / уклад. Є. Мейнарович, М. Кратко. — 2010.
2. representing // Англійсько-українсько-англійський словник наукової мови (фізика та споріднені науки). Частина І англійсько-українська / уклад. О. Кочерга, Є. Мейнарович. — 2010.
3. представляльний // Англійсько-українсько-англійський словник наукової мови (фізика та споріднені науки). Частина ІІ українсько-англійська / уклад. О. Кочерга, Є. Мейнарович. — 2010.

Див. також

• Характеристична функція випадкової величини
• (Характеристична функція (теорія ігор))
• Вільні і зв'язані змінні
• Функція належності
• Проста функція
• ^[en]
• ^[en]
• Дельта-функція Дірака
• Функція Гевісайда
• Дужка Айверсона
• Символ Кронекера, функція, яку можна розглядати як індикатор для відношення рівності
• ^[en]
• Мультимножина
• ^[en]
• Задача класифікації
• (Функція втрат 0-1)

Джерела

• Folland, G.B. (1999). Real Analysis: Modern Techniques and Their Applications (вид. Second). John Wiley & Sons, Inc. ISBN . (англ.)
• Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. Section 5.2: Indicator random variables. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
• (Davis, Martin), ред. (1965). The Undecidable. New York: Raven Press Books, Ltd. (англ.)
• Kleene, Stephen (1971) [1952]. Introduction to Metamathematics (Sixth Reprint with corrections). Netherlands: Wolters-Noordhoff Publishing and North Holland Publishing Company. (англ.)