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

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

Приклад

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

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

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

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

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

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

• Блокування $C^R(X)=\{x\in X|\mathrm{\forall }y\in Xy\bar{R}x\}$ - множина мажорант на множині X. ($\bar{R}$ - доповнення до відношення).
• Перевага $C_R(X)=\{x\in X|\mathrm{\forall }y\in XxRy\}$ - множина максимумів на множині 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 \mathrm{\Omega }$, і для будь-якого покриваючого її сімейства $\{X_i{\}}_{i\in J}$ виконується:

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

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

Посилання

1. Шаблон:Cite book