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

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

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

Означення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\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}},$

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

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

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

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

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

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

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

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

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

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

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

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

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

Дисперсія

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

Коваріація

$\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», під редагуванням Мартіна Девіса):

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

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

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

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

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

Див. також

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

Джерела

• Folland, G.B. (1999). Real Analysis: Modern Techniques and Their Applications (вид. Second). John Wiley & Sons, Inc. ISBN 978-0-471-31716-6. (англ.)
• Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2001) [1990]. Section 5.2: Indicator random variables. Вступ до алгоритмів (вид. 2nd). MIT Press і McGraw-Hill. ISBN 0-262-03293-7.
• 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. (англ.)