Введение

Математическая функция, комбинаторная функция выбора C(n, k).

Функция выбора (селектор, функция отбора) — это математическая функция f, которая определена на некотором наборе X непустых множеств и присваивает каждому множеству S из этого набора элемент из S посредством f(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) и доказал теорему о хорошем упорядочении, которая утверждает, что любое множество может быть хорошо упорядочено. Аксиома выбора (AC) утверждает, что любое множество непустых множеств имеет функцию выбора. Более слабая форма AC, аксиома счётного выбора (ACω), утверждает, что любое счётное множество непустых множеств имеет функцию выбора. Однако, даже при отсутствии AC или ACω, некоторые множества всё ещё могут иметь функцию выбора. Если – конечное множество непустых множеств, то можно построить функцию выбора для , выбирая по одному элементу из каждого множества из . Это требует лишь конечного числа выборов, поэтому ни AC, ни ACω не нужны. Если каждое множество из является непустым, и объединение хорошо упорядочено, то можно выбрать наименьший элемент из каждого множества из . В этом случае можно одновременно хорошо упорядочить каждое множество из , сделав лишь один выбор хорошего упорядочения объединения, поэтому ни AC, ни ACω не требуются. (Этот пример показывает, что теорема о хорошем упорядочении влечёт за собой AC. Обратное также верно, но менее очевидно.)

Функция Бурбаки тау

Николас Бурбаки использовал эпсилон-исчисление в качестве основы своих работ, которое содержало символ, интерпретируемый как выбор объекта (если такой существует), удовлетворяющего заданному утверждению. Таким образом, если P – это предикат, то εP – это один конкретный объект, удовлетворяющий P (если он существует, иначе возвращается произвольный объект). Следовательно, кванторы можно получить из функции выбора, например, ∀x P(x) эквивалентно ¬∃x ¬P(x). Однако оператор выбора Бурбаки сильнее обычного: это глобальный оператор выбора. То есть, он подразумевает аксиому глобального выбора. Гильберт осознал это, когда вводил эпсилон-исчисление.