Функція вибору

Функція вибору (чи селектор) для множини ${\displaystyle ~\Omega }$ це функція ${\displaystyle \ C:2^{\Omega }\to 2^{\Omega }}$ (${\displaystyle 2^{\Omega }}$ - булеан ${\displaystyle \Omega }$), яка кожній множині ${\displaystyle X\subseteq \Omega }$ ставить у відповідність деяку її підмножину ${\displaystyle C(X)\subseteq X}$.

Приклад

Нехай X = { {1,4,7}, {9}, {2,7} }. Тоді функція, що призначає 7 множині {1,4,7}, 9 множині {9} і 2 множині {2,7} — це функція вибору.

Функція вибору та аксіома вибору

Ернст Цермело ввів поняття функції вибору разом з аксіомою вибору в 1904 році в доведенні теореми про цілком впорядковану множину. Як було вказано ним, деякі множини можуть мати функцію вибору і без застосування аксіоми вибору:

• Для скінченного сімейства множин.
• Якщо кожна множина сімейства є цілком упорядкованою.
• Коли об'єднання всіх множин сімейства є цілком упорядковуваним.

Способи задання

Вибір зручно здійснювати порівнюючи дві альтернативи, тобто задавати на ${\displaystyle \Omega }$ деяке бінарне відношення ${\displaystyle R}$. Тоді, функцію вибору за цим бінарним відношенням можна задати двома способами:

• Блокування ${\displaystyle C^{R}(X)=\{x\in X|\;\forall y\in X\quad y{\overline {R}}x\}}$ - множина мажорант на множині X. (${\displaystyle {\overline {R}}}$ - доповнення до відношення).
• Перевага ${\displaystyle C_{R}(X)=\{x\in X|\;\forall y\in X\quad xRy\}}$ - множина максимумів на множині X.

Теорема: функції вибору ${\displaystyle C^{R}}$ і ${\displaystyle C_{R}}$ зв'язані співвідношеннями ${\displaystyle C^{R}=C_{R^{d}},C_{R}=C^{R^{d}}}$, де ${\displaystyle R^{d}}$ - двоїсте відношення до R.

Покриваюче сімейство для множини X - це ${\displaystyle \{X_{i}\},i\in J:X\subseteq \bigcup _{i\in J}X_{i}}$.

Функція вибору є нормальною, тоді і лише тоді, коли для будь-якої множини ${\displaystyle X\subseteq \Omega }$, і для будь-якого покриваючого її сімейства ${\displaystyle \{X_{i}\}_{i\in J}}$ виконується:

${\displaystyle X\setminus C(X)\subseteq X\setminus \bigcup _{i\in J}C(X_{i})}$

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

Посилання

1. Волошин О.Ф.; Мащенко С.О. (2006). Теорія прийняття рішень (укр) . К: ВПЦ "Київський університет". ISBN 966-594-742-7.