Функция выбора

Функция выбора ( селектор , выбор ) — это математическая функция f , которая определена в некоторой коллекции X непустых множеств некоторый элемент каждого набора S в этой коллекции и присваивает S с помощью f ( S ); f ( S ) отображает S некоторый элемент S. в Другими словами, f является функцией выбора для тогда когда она принадлежит прямому произведению X. X и только тогда ,

Пример

Пусть X = { {1,4,7}, {9}, {2,7} }. Тогда функция f, определенная формулами f({1, 4, 7}) = 7, f({9}) = 9 и f({2, 7}) = 2, является функцией выбора на X .

История и значение

Эрнст Цермело (1904) ввел функции выбора, а также аксиому выбора (AC) и доказал теорему о хорошем порядке : ^{[ 1 ]} который утверждает, что любое множество может быть хорошо упорядочено . AC утверждает, что каждое множество непустых множеств имеет функцию выбора. Более слабая форма AC, аксиома счетного выбора (AC _ω ) утверждает, что каждое счетное множество непустых множеств имеет функцию выбора. Однако в отсутствие AC или AC _ω можно показать, что некоторые множества имеют функцию выбора.

Если $X$ — конечное множество непустых множеств, то можно построить функцию выбора для $X$ выбирая по одному элементу от каждого члена $X.$ Для этого требуется лишь конечное число вариантов, поэтому ни AC, ни AC _ω не нужны.
Если каждый член $X$ — непустое множество, а объединение $\bigcup X$ хорошо упорядочен, то можно выбрать наименьший элемент каждого члена $X$ . В этом случае можно было одновременно хорошо упорядочить каждого члена $X$ сделав только один выбор полного порядка объединения, так что ни AC, ни AC _ω не нужны. (Этот пример показывает, что из теоремы о хорошем порядке следует AC. Обратное также верно, но менее тривиально.)

Функция выбора многозначного отображения

Для двух множеств и Y пусть F — многозначное отображение X X в Y (эквивалентно: $F:X\rightarrow {\mathcal {P}}(Y)$ является функцией от X до степеней набора Y ).

Функция $f:X\rightarrow Y$ называется выбором F : , если

$\forall x\in X\,(f(x)\in F(x))\,.$

Существование более регулярных функций выбора, а именно непрерывных или измеримых выборов, важно в теории дифференциальных включений , оптимального управления и математической экономики . ^{[ 2 ]} См. Теорему выбора .

Тау-функция Бурбаки

Николя Бурбаки использовал эпсилон-исчисление для своих основ, имевших $\tau$ символ, который можно интерпретировать как выбор объекта (если таковой существует), удовлетворяющего данному предложению. Итак, если $P(x)$ является предикатом, то $\tau _{x}(P)$ это один конкретный объект, который удовлетворяет $P$ (если он существует, в противном случае возвращается произвольный объект). Следовательно, мы можем получить кванторы из функции выбора, например $P(\tau _{x}(P))$ был эквивалентен $(\exists x)(P(x))$ . ^{[ 3 ]}

Однако оператор выбора Бурбаки сильнее обычного: это оператор глобального выбора. То есть отсюда следует аксиома глобального выбора . ^{[ 4 ]} Гильберт понял это, когда ввел эпсилон-исчисление. ^{[ 5 ]}

См. также

Примечания

^ Цермело, Эрнст (1904). «Доказательство того, что любое множество может быть упорядочено» . Математические летописи . 59 (4): 514–16. дои : 10.1007/BF01445300 .
^ Бордер, Ким К. (1989). Теоремы о неподвижной точке с приложениями к экономике и теории игр . Издательство Кембриджского университета. ISBN 0-521-26564-9 .
^ Бурбаки, Николя. Элементы математики: теория множеств . ISBN 0-201-00634-0 .
^ «Взгляд на Бурбаки» Джон Харрисон, электронная распечатка .
^ «Более того, здесь мы сталкиваемся с очень примечательным обстоятельством, а именно с тем, что все эти трансфинитные аксиомы выводятся из одной аксиомы, которая также содержит ядро одной из наиболее подвергаемых нападкам аксиом в математической литературе, а именно: аксиома выбора: $A(a)\to A(\varepsilon (A))$ , где $\varepsilon$ — это трансфинитная функция логического выбора». Гильберт (1925), «О бесконечном», отрывок из книги Жана ван Хейеноорта, От Фреге до Гёделя , стр. 382. Из nCatLab .

Ссылки

Эта статья включает в себя материал из функции Choice на PlanetMath , которая распространяется по лицензии Creative Commons Attribution/Share-Alike License .

[Zermelo,_1904-1] Цермело, Эрнст (1904). «Доказательство того, что любое множество может быть упорядочено» . Математические летописи . 59 (4): 514–16. дои : 10.1007/BF01445300 .

[2] Бордер, Ким К. (1989). Теоремы о неподвижной точке с приложениями к экономике и теории игр . Издательство Кембриджского университета. ISBN 0-521-26564-9 .

[3] Бурбаки, Николя. Элементы математики: теория множеств . ISBN 0-201-00634-0 .

[4] «Взгляд на Бурбаки» Джон Харрисон, электронная распечатка .

[5] «Более того, здесь мы сталкиваемся с очень примечательным обстоятельством, а именно с тем, что все эти трансфинитные аксиомы выводятся из одной аксиомы, которая также содержит ядро одной из наиболее подвергаемых нападкам аксиом в математической литературе, а именно: аксиома выбора: $A(a)\to A(\varepsilon (A))$ , где $\varepsilon$ — это трансфинитная функция логического выбора». Гильберт (1925), «О бесконечном», отрывок из книги Жана ван Хейеноорта, От Фреге до Гёделя , стр. 382. Из nCatLab .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]