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

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

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

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

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

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

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

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

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

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

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

$X \setminus C(X) \subseteq X \setminus \bigcup_{i \in J} C(X_i)$

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

Посилання

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