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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Функція вибору та аксіома вибору[ред.ред. код]

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

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

Застосування[ред.ред. код]

До кінця XIX століття аксіома вибору використовувалася беззастережно. Наприклад , після визначення безлічі X , що містить непорожнє безліч , математик міг сказати: « Нехай F ( s ) буде визначено для кожного s з X ». Загалом , неможливо довести , що F існує без аксіоми вибору , але це , здається , залишалося без уваги до Цермело . Не у всіх випадках потрібно аксіома вибору. Для кінцевого набору X аксіома вибору випливає з інших аксіом теорії множин. У цьому випадку це те ж саме , що говорити , якщо ми маємо кілька ( кінцеве число) коробок , кожна з яких містить в собі по одній однаковій речі , тоді ми можемо вибрати рівно одну річ з кожної коробки. Ясно , що ми можемо зробити це : ми почнемо з першої коробки , виберемо річ ; вирушимо до другої коробці , виберемо річ ; і т. д. Так як є кінцеве число коробок , то діючи нашої процедурою вибору , ми прийдемо до кінця . Результатом буде функція явного вибору: функція , яка першою коробці зіставляє перший елемент , який ми вибрали , другий коробці - другий елемент і т. д. (Для отримання формального докази для всіх кінцевих множин слід скористатися принципом математичної індукції . )

У випадку з нескінченним безліччю X іноді також можна обійти аксіому вибору. Наприклад , якщо елементи X - множини натуральних чисел. Кожен непорожній набір натуральних чисел має найменший елемент , таким чином , визначаючи нашу функцію вибору, ми можемо просто сказати , що кожному безлічі зіставляється найменший елемент набору . Це дозволяє нам зробити вибір елемента з кожного безлічі , тому ми можемо записати явний вираз , яке говорить нам , яке значення наша функція вибору приймає. Якщо можливо таким чином визначити функцію вибору , в аксіомі вибору немає необхідності.

Складнощі з'являються у разі , якщо неможливо здійснити природний вибір елементів з кожного безлічі . Якщо ми не можемо зробити явний вибір , то чому впевнені , що такий вибір можна здійснити в принципі? Наприклад , нехай X - це безліч непорожніх підмножин дійсних чисел. По-перше , ми могли б спробувати вступити як у випадку , якби X було кінцевим . Якщо ми спробуємо вибрати елемент з кожного безлічі , тоді , так як X нескінченно , наша процедура вибору ніколи не прийде до кінця , і внаслідок цього ми ніколи не отримаємо функції вибору для всього X. Так що це не спрацьовує. Далі, ми можемо спробувати визначити найменший елемент з кожного безлічі . Але деякі підмножини дійсних чисел не містять найменший елемент . Наприклад , таким підмножиною є відкритий інтервал ( 0 , \; 1 ) . Якщо x належить ( 0 , \; 1 ) , то x / 2 також належить йому , причому менше, ніж x . Отже, вибір найменшого елемента теж не працює.

Причина , яка дозволяє вибрати нам найменший елемент з підмножини натуральних чисел - це факт , що натуральні числа мають властивість вполнеупорядоченності . Кожна підмножина натуральних чисел має єдиний найменший елемент в силу природної впорядкованості. Можливо , якби ми були розумнішими , то могли б сказати: «Можливо , якщо звичайний порядок для дійсних чисел не дозволяє знайти особливу (найменше) число в кожному підмножині , ми могли б ввести інший порядок , який таки давав би властивість вполнеупорядоченності . Тоді наша функція зможе вибрати найменший елемент з кожного безлічі в силу нашого незвичайного упорядкування ». Проблема тоді виникає в цьому побудові вполнеупорядоченності , яка для свого рішення вимагає наявності аксіоми вибору. Іншими словами , кожне безліч може бути цілком впорядковано тоді і тільки тоді , коли аксіома вибору справедлива.

Докази , що вимагають аксіоми вибору , завжди неконструктивні : навіть якщо доказ створює об'єкт , неможливо сказати , що ж саме це за об'єкт. Отже , хоч аксіома вибору дозволяє цілком впорядкувати безліч дійсних чисел, це не дає нам ніякої наочності і конструктивізму в цілому. Сама причина , по якій наш вищевказаний вибір цілком впорядкування дійсних чисел був таким для кожного безлічі X , ми могли явно вибрати елемент з такої безлічі . Якщо ми не можемо вказати , що ми використовуємо цілком впорядкованість , тоді наш вибір не цілком явний . Це одна з причин , чому деякі математики не люблять аксіому вибору ( див. також Криза підстав математики) . Наприклад , конструктивістська установка що всі існуючі докази повинні бути повністю явними ; має бути можливим побудова чого б то не було що існує. Вони відкидають аксіому вибору тому , що вона заявляє існування об'єкта без опису . З іншого боку , факт - що для доказу існування використовується аксіома вибору - не означає , що ми не зможемо здійснити побудова іншим способом.

Альтернативні формулювання[ред.ред. код]

Аксіома вибору стверджує:

   Нехай X - безліч непорожніх попарно непересічних множин . Тоді ми можемо вибрати єдиний елемент з кожного безлічі в X.
   Функція вибору - функція на безлічі множин X така , що для кожного безлічі s в X , f ( s ) є елементом з s .

З використанням поняття функції вибору аксіома стверджує:

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

Або альтернативно :

   Довільний декартовій твір непорожніх множин непорожньо .

Або найбільш стисло :

   Кожне безліч непорожніх множин має функцію вибору.
   Звідси негайно слід компактна формулювання заперечення аксіоми вибору:
   Існує безліч непорожніх множин , яке не має жодної функції вибору.

Друга версія аксіоми вибору стверджує:

  Для даного довільного безлічі попарно непересічних непорожніх 
  множин існує принаймні одне безліч , яке містить точно один елемент. 

Деякі автори використовують іншу версію , яка ефективно стверджує:

   Для будь-якого безлічі A , його булеан за вирахуванням порожнього підмножини
\ mathcal P (A ) \ setminus \ {\ varnothing \} має функцію вибору.

Автори , які використовують це формулювання, часто також говорять про «функції вибору на A » , але обумовлюють, що мають на увазі трохи інше поняття функції вибору . Її область визначення - булеан (мінус пусте підмножина ) , тоді як в інших місцях цієї статті , область визначення функції вибору - « безліч множин ». З цим додатковим поняттям функції вибору , аксіома вибору може бути стисло сформульована так : .

Способи задання[ред.ред. код]

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

Теорема: функції вибору 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, не є обраним хоча б у одній множині з покриваючого сімейства.

Принцип цілком упорядкування ( теорема Цермело )[ред.ред. код]

Дуже поширена і зручна формулювання використовує поняття цілком упорядкованої множини. Нам потрібно кілька визначень , і ми почнемо зі суворого визначення лінійного порядку , що виражає знайому нам ідею мовою теорії множин. Нагадаємо , що впорядкована пара елементів позначається ( x , \; y ) і що декартовій твір множин X \ times Y складається з усіх можливих впорядкованих пар ( x , \; y ), де x \ in X , \; y \ in Y. Лінійним порядком на безлічі A називається підмножина декартова твори R \ subseteq A \ times A , має такі властивості:

       Повне: \ forall x , \; y \ in A \ ; ( ( x , \; y ) \ in R \ lor ( y , \; x ) \ in R ) .
       Антисиметричною : \ forall x , \; y \ in A \ ; ( ( x , \; y ) \ in R \ wedge ( y , \; x ) \ in R \ to y = x ) .
       Транзитивне : \ forall x , \; y , \; z \ in A \ ; ( ( x , \; y ) \ in R \ wedge ( y , \; z ) \ in R \ to ( x , \; z ) \ in R ) .

Повним порядком на безлічі A називається такий лінійний порядок , що кожна підмножина X \ subseteq A має найменший елемент . Принцип повного порядку полягає в тому , що будь-яке безліч може бути цілком впорядковано . Наприклад , безліч натуральних чисел може бути цілком впорядковано звичайним відношенням «менше або дорівнює чим». З тим же відношенням безліч цілих чисел не має найменшого елемента . У цьому випадку ми можемо зібрати цілі числа в послідовність ( 0 , \; -1 , \; 1 , \; -2 , \; 2 , \; \ ldots , \; - n , \; n , \; \ ldots ) і сказати , що молодші члени менше , ніж старші . Очевидно , таке ставлення буде повним порядком на цілих числах.

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

Лемма Цорна[ред.ред. код]

Якщо в частково впорядкованій множині будь ланцюг (тобто лінійно впорядкована підмножина ) має верхню грань , то все безліч має хоча б один максимальний елемент . Більш формально : Нехай ( P , \; \ leqslant ) - частково упорядкований безліч , тобто , відношення \ leqslant - рефлексивно , антисиметричного і транзитивно :

       \ forall x \ in P \ quad x \ leqslant x ;
       \ forall x , \; y \ in P \ ; x \ leqslant y \ and y \ leqslant x \ to x = y ;
       \ forall x , \; y , \; z \ in P \ ; x \ leqslant y \ and y \ leqslant z \ to x \ leqslant z .

Підмножина S \ subset P називається лінійно впорядкованим , якщо \ forall x , \; y \ in S \ ; x \ leqslant y \ or y \ leqslant x . Елемент u \ in S називається верхньою межею , якщо \ forall x \ in S \ ; x \ leqslant u . Припустимо , що будь-яке лінійно впорядкована підмножина безлічі P має верхню грань. Тоді \ exists m \ in P \ ; \ nexists x \ in P \ ; x > m , тобто m - максимальний елемент .

Посилання[ред.ред. код]

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