Аксиома выбора - Axiom of choice

Эта статья о математической концепции. Для группы см. Аксиома выбора (группа).

Иллюстрация аксиомы выбора, где каждый S_я и Икс_я представлены в виде кувшина и цветного мрамора соответственно

(S_я) является бесконечным семья наборов, проиндексированных по действительные числа р; то есть существует множество S_я для каждого реального числа я, с небольшим образцом, показанным выше. Каждый набор содержит по крайней мере один, а возможно и бесконечно много элементов. Аксиома выбора позволяет нам произвольно выбирать один элемент из каждого набора, образуя соответствующее семейство элементов (Икс_я) также индексируется по действительным числам, с Икс_я взято из S_я. Как правило, коллекции можно индексировать по любому набору. я, не просто р.

В математика, то аксиома выбора, или же AC, является аксиома из теория множеств эквивалентно утверждению, что а Декартово произведение набора непустых множеств непусто. Неформально говоря, аксиома выбора гласит, что для любой коллекции бункеров, каждая из которых содержит хотя бы один объект, можно выбрать ровно один объект из каждой ячейки, даже если коллекция бесконечный. Формально он гласит, что для каждого индексированная семья ${displaystyle (S_{i})_{iin I}}$ из непустой устанавливает, что существует индексированное семейство ${displaystyle (x_{i})_{iin I}}$ таких элементов, что ${displaystyle x_{i}in S_{i}}$ для каждого ${displaystyle iin I}$. Аксиома выбора была сформулирована в 1904 г. Эрнст Цермело чтобы формализовать его доказательство теорема о хорошем порядке.^[1]

Во многих случаях такой выбор может быть сделан без применения аксиомы выбора; это, в частности, имеет место, если количество наборов конечно, или если доступно правило выбора - какое-то отличительное свойство, которое имеет место ровно для одного элемента в каждом наборе. Наглядный пример - наборы, взятые из натуральных чисел. Из таких наборов всегда можно выбрать наименьшее число, например для наборов {{4, 5, 6}, {10, 12}, {1, 400, 617, 8000}} набор, содержащий каждый наименьший элемент, равен {4, 10, 1}. В этом случае «выберите наименьшее число» - это функция выбора. Даже если из натуральных чисел было собрано бесконечно много наборов, всегда можно будет выбрать наименьший элемент из каждого набора для создания набора. То есть функция выбора предоставляет набор выбранных элементов. Однако неизвестна функция выбора для набора всех непустых подмножеств действительных чисел (если есть неконструктивные реалы ). В этом случае необходимо применить аксиому выбора.

Бертран Рассел придумал аналогию: для любой (даже бесконечной) коллекции пар обуви можно выделить левую обувь из каждой пары, чтобы получить соответствующий выбор; это позволяет напрямую определять функцию выбора. Для бесконечный набор пар носков (предполагается, что они не имеют отличительных черт), нет очевидного способа создать функцию, которая выбирает по одному носку из каждой пары, без применения аксиомы выбора.^[2]

Хотя первоначально спорный, аксиома выбора теперь используется без оговорки большинства математиков,^[3] и входит в стандартную форму аксиоматическая теория множеств, Теория множеств Цермело – Френкеля с аксиомой выбора (ZFC ). Одной из причин такого использования является то, что ряд общепринятых математических результатов, таких как Теорема Тихонова, требуют аксиомы выбора для своих доказательств. Современные теоретики множеств также изучают аксиомы, несовместимые с аксиомой выбора, такие как аксиома детерминированности. Аксиома выбора избегается в некоторых разновидностях конструктивная математика, хотя существуют разновидности конструктивной математики, в которых принята аксиома выбора.

Заявление

А функция выбора это функция ж, определенный в коллекции Икс непустых наборов, таких что для каждого набора А в Икс, ж(А) является элементом А. С помощью этой концепции можно сформулировать аксиому:

Аксиома — Для любого набора Икс непустых множеств существует функция выбора ж определено на Икс.

Формально это можно выразить так:

${displaystyle forall Xleft[varnothing otin Ximplies exists fcolon Xightarrow igcup Xquad forall Ain X,(f(A)in A)ight],.}$

Таким образом, отрицание аксиомы выбора утверждает, что существует набор непустых множеств, у которого нет функции выбора.

Каждая функция выбора в коллекции Икс непустых множеств является элементом Декартово произведение наборов в Икс. Это не самая общая ситуация с декартовым произведением семья наборов, где данный набор может встречаться более одного раза как фактор; однако можно сосредоточиться на элементах такого продукта, которые выбирают один и тот же элемент каждый раз, когда данный набор появляется как фактор, и такие элементы соответствуют элементу декартова произведения всех отчетливый наборы в семье. Аксиома выбора утверждает существование таких элементов; поэтому это эквивалентно:

Для любого семейства непустых множеств их декартово произведение - непустое множество.

Номенклатура ZF, AC и ZFC

В этой статье и других обсуждениях Аксиомы Выбора используются следующие сокращения:

• AC - Аксиома выбора.
• ZF - Теория множеств Цермело – Френкеля опуская аксиому выбора.
• ZFC - теория множеств Цермело – Френкеля, расширенная за счет включения аксиомы выбора.

Варианты

Есть много других эквивалентных утверждений аксиомы выбора. Они эквивалентны в том смысле, что в присутствии других основных аксиом теории множеств они подразумевают аксиому выбора и подразумеваются ею.

Один из вариантов позволяет избежать использования функций выбора, фактически заменяя каждую функцию выбора ее диапазоном.

Учитывая любой набор Икс из попарно непересекающиеся непустые множества, существует хотя бы один набор C который содержит ровно один элемент, общий с каждым из множеств в Икс.^[4]

Это гарантирует любой раздел набора Икс существование подмножества C из Икс содержащий ровно один элемент из каждой части раздела.

Другая эквивалентная аксиома рассматривает только коллекции Икс которые по сути являются наборами мощности других наборов:

Для любого множества A набор мощности из A (с удаленным пустым множеством) имеет функцию выбора.

Авторы, использующие эту формулировку, часто говорят о функция выбора на A, но это немного другое понятие функции выбора. Его домен - это набор мощности А (с удаленным пустым набором), и поэтому имеет смысл для любого набора А, тогда как с определением, используемым в другом месте в этой статье, область определения функции выбора на коллекция наборов является той коллекцией, и поэтому имеет смысл только для наборов множеств. Используя это альтернативное понятие функции выбора, аксиома выбора может быть компактно сформулирована как

У каждого набора есть функция выбора.^[5]

что эквивалентно

Для любого множества A существует функция ж такое, что для любого непустого подмножества B из А, ж(B) лежит в B.

Таким образом, отрицание аксиомы можно выразить следующим образом:

Есть набор А так что для всех функций ж (на множестве непустых подмножеств А), Существует B такой, что ж(B) не лежит в B.

Ограничение на конечные множества

Формулировка аксиомы выбора не указывает, является ли набор непустых множеств конечным или бесконечным, и, таким образом, подразумевает, что каждое конечный набор непустых множеств имеет функцию выбора. Однако этот частный случай является теоремой теории множеств Цермело – Френкеля без аксиомы выбора (ZF); это легко доказывается математическая индукция.^[6] В еще более простом случае сбора один set, функция выбора просто соответствует элементу, поэтому этот пример аксиомы выбора говорит, что каждое непустое множество имеет элемент; это выполняется тривиально. Выбранная аксиома может рассматриваться как утверждение обобщения этого свойства, уже очевидного для конечных коллекций, на произвольные коллекции.

использование

До конца XIX века аксиома выбора часто использовалась неявно, хотя формально она еще не была сформулирована. Например, установив, что набор Икс содержит только непустые множества, математик мог бы сказать "пусть F (s) быть одним из членов s для всех s в Икс"определить функцию F. В общем, доказать, что F существует без аксиомы выбора, но, похоже, это осталось незамеченным, пока Цермело.

Не в каждой ситуации требуется аксиома выбора. Для конечных множеств Икс, аксиома выбора следует из других аксиом теории множеств. В этом случае это эквивалентно тому, что если у нас есть несколько (конечное число) ящиков, каждый из которых содержит хотя бы один элемент, то мы можем выбрать ровно один элемент из каждого ящика. Ясно, что мы можем это сделать: мы начинаем с первого поля, выбираем элемент; перейдите ко второму окну, выберите товар; и так далее. Количество ящиков конечно, так что в конце концов наша процедура выбора подходит к концу. Результатом является функция явного выбора: функция, которая переводит первое поле к первому выбранному нами элементу, второе поле - ко второму выбранному нами элементу и так далее. (Формальное доказательство для всех конечных множеств будет использовать принцип математическая индукция доказать "для каждого натурального числа k, каждая семья k непустые множества имеют функцию выбора. ") Этот метод, однако, нельзя использовать, чтобы показать, что каждое счетное семейство непустых множеств имеет функцию выбора, как утверждается аксиома счетного выбора. Если метод применяется к бесконечной последовательности (Икс_я : я∈ω) непустых множеств, функция получается на каждом конечном этапе, но нет этапа, на котором строится функция выбора для всего семейства, и никакая "предельная" функция выбора, вообще говоря, не может быть построена в ZF без аксиома выбора.

Примеры

Природа отдельных непустых множеств в коллекции может позволить избежать аксиомы выбора даже для некоторых бесконечных наборов. Например, предположим, что каждый член коллекции Икс - непустое подмножество натуральных чисел. Каждое такое подмножество имеет наименьший элемент, поэтому, чтобы указать нашу функцию выбора, мы можем просто сказать, что она отображает каждый набор на наименьший элемент этого набора. Это дает нам определенный выбор элемента из каждого набора и избавляет от необходимости применять аксиому выбора.

Сложность возникает тогда, когда нет естественного выбора элементов из каждого набора. Если мы не можем сделать явный выбор, как мы узнаем, что наш набор существует? Например, предположим, что Икс - это множество всех непустых подмножеств действительные числа. Сначала мы могли бы попытаться действовать, как если бы Икс были конечными. Если мы попытаемся выбрать элемент из каждого набора, то, поскольку Икс бесконечно, наша процедура выбора никогда не закончится, и, следовательно, мы никогда не сможем создать функцию выбора для всех Икс. Затем мы можем попытаться указать наименьшее количество элементов из каждого набора. Но некоторые подмножества действительных чисел не имеют наименьших элементов. Например, открытый интервал (0,1) не имеет наименьшего элемента: если Икс находится в (0,1), то и Икс/ 2 и Икс/ 2 всегда строго меньше, чем Икс. Так что и эта попытка не удалась.

Кроме того, рассмотрим, например, единичный круг S, и действие на S группой грамм состоящий из всех рациональных поворотов. А именно, это повороты на углы, рациональные кратныеπ. Здесь грамм счетно, пока S бесчисленное множество. Следовательно S разбивается на бесчисленное множество орбит подграмм. Используя аксиому выбора, мы могли бы выбрать одну точку на каждой орбите, получив несчетное подмножество Икс из S со свойством, что все его переводы G не пересекаются сИкс. Набор из них переводит разбиение круга на счетный набор непересекающихся множеств, которые все попарно конгруэнтны. С Икс не измерима ни для какой счетно-аддитивной конечной меры, инвариантной относительно вращения, на S, поиск алгоритма для выбора точки на каждой орбите требует аксиомы выбора. Видеть неизмеримое множество Больше подробностей.

Причина того, что мы можем выбирать наименьшее количество элементов из подмножеств натуральных чисел, заключается в том, что натуральные числа хорошо организованный: каждое непустое подмножество натуральных чисел имеет уникальный наименьший элемент в естественном порядке. Можно сказать: «Даже если обычное упорядочение действительных чисел не работает, возможно, удастся найти другое упорядочение действительных чисел, которое является правильным. Тогда наша функция выбора может выбрать наименьший элемент из каждого набора. по нашему необычному заказу ". Тогда проблема заключается в построении хорошего упорядочения, которое, как оказывается, требует аксиомы выбора для своего существования; каждый набор может быть хорошо упорядочен тогда и только тогда, когда выполняется аксиома выбора.

Критика и принятие

Доказательство, требующее аксиомы выбора, может установить существование объекта без явного определение объект на языке теории множеств. Например, в то время как аксиома выбора подразумевает, что существует хороший порядок Из действительных чисел существуют модели теории множеств с аксиомой выбора, в которых нельзя определить четкий порядок вещественных чисел. Точно так же, хотя подмножество реальных чисел, не Измеримый по Лебегу можно доказать, что существует аксиома выбора, это последовательный что такой набор не определим.^[7]

Аксиома выбора доказывает существование этих нематериальных активов (объектов, существование которых доказано, но которые не могут быть явно сконструированы), что может противоречить некоторым философским принципам.^[8] Потому что нет канонический упорядочение всех наборов, конструкция, основанная на правильном упорядочивании, может не дать канонического результата, даже если канонический результат желателен (как это часто бывает в теория категорий ). Это использовалось в качестве аргумента против использования аксиомы выбора.

Еще один аргумент против аксиомы выбора состоит в том, что она подразумевает существование объектов, которые могут показаться нелогичными.^[9] Одним из примеров является Парадокс Банаха – Тарского в котором говорится, что можно разбить трехмерный твердый единичный шар на конечное число частей и, используя только вращения и перемещения, собрать эти части в два твердых шара, каждый с таким же объемом, что и исходный. Фрагменты этого разложения, построенные с использованием выбранной аксиомы, являются неизмеримые множества.

Несмотря на эти, казалось бы, парадоксальный Факты, большинство математиков принимают аксиому выбора как действительный принцип для доказательства новых результатов в математике. Тем не менее, дискуссия достаточно интересна, так что она считается заметной, когда теорема в ZFC (ZF плюс AC) логически эквивалентный (только с аксиомами ZF) к аксиоме выбора, и математики ищут результаты, которые требуют, чтобы выбранная аксиома была ложной, хотя этот тип вывода менее распространен, чем тип, который требует, чтобы аксиома выбора была истинной.

Многие теоремы можно доказать, не используя ни аксиомы выбора, ни ее отрицания; такие утверждения будут верны в любом модель ZF, независимо от истинности или ложности аксиомы выбора в данной конкретной модели. Ограничение ZF делает недоказанным любое утверждение, основанное либо на аксиоме выбора, либо на ее отрицании. Например, парадокс Банаха – Тарского нельзя доказать или опровергнуть только с помощью ZF: невозможно построить требуемое разложение единичного шара в ZF, но также невозможно доказать, что такого разложения нет. Точно так же все утверждения, перечисленные ниже^{[требуется разъяснение ]} которые требуют выбора или какой-либо более слабой версии для их доказательства, недоказуемы в ZF, но поскольку каждая из них доказуема в ZF плюс аксиома выбора, существуют модели ZF, в которых каждое утверждение истинно. Такие утверждения, как парадокс Банаха – Тарского, можно перефразировать как условные утверждения, например: «Если AC выполняется, то существует разложение в парадоксе Банаха – Тарского». Такие условные утверждения доказуемы в ZF, если исходные утверждения доказуемы из ZF и выбранной аксиомы.

В конструктивной математике

Как обсуждалось выше, в ZFC аксиома выбора может обеспечить "неконструктивные доказательства ", в котором доказывается существование объекта, хотя явный пример не строится. ZFC, однако, все еще формализована в классической логике. Аксиома выбора также была тщательно изучена в контексте конструктивной математики, где неклассическая логика Статус избранной аксиомы варьируется в зависимости от разновидностей конструктивной математики.

В Теория типа Мартина-Лёфа и более высокого порядка Арифметика Гейтинга соответствующая формулировка выбранной аксиомы (в зависимости от подхода) включается как аксиома или доказывается как теорема.^[10] Эрретт Бишоп утверждал, что аксиома выбора была конструктивно приемлемой, говоря

Функция выбора существует в конструктивной математике, потому что выбор подразумевается самим смыслом существования.^[11]

В конструктивная теория множеств, тем не мение, Теорема Диаконеску показывает, что из выбранной аксиомы следует закон исключенного среднего (в отличие от теории типов Мартина-Лёфа, где это не так). Таким образом, аксиома выбора обычно недоступна в конструктивной теории множеств. Причина этого различия в том, что аксиома выбора в теории типов не имеет протяженность свойства, которые делает аксиома выбора в конструктивной теории множеств.^[12]

Некоторые результаты в конструктивной теории множеств используют аксиома счетного выбора или аксиома зависимого выбора, которые не подразумевают закон исключенного третьего в конструктивной теории множеств. Хотя аксиома счетного выбора, в частности, обычно используется в конструктивной математике, ее использование также подвергается сомнению.^[13]

Независимость

Смотрите также: Список операторов, независимых от ZFC

В 1938 г.^[14] Курт Гёдель показал, что отрицание аксиомы выбора не является теоремой ZF путем построения внутренняя модель (в конструируемая вселенная ), который удовлетворяет ZFC и, таким образом, показывает, что ZFC согласован, если сам ZF согласован. В 1963 г. Пол Коэн использовал технику принуждение, разработанный для этой цели, чтобы показать, что в предположении непротиворечивости ZF сама аксиома выбора не является теоремой ZF. Он сделал это, построив гораздо более сложную модель, которая удовлетворяет ZF¬C (ZF с отрицанием AC, добавленным в качестве аксиомы) и, таким образом, показав, что ZF¬C непротиворечива.^[15]

Вместе эти результаты показывают, что аксиома выбора логически независимый ZF. Предположение, что ZF непротиворечиво, безвредно, потому что добавление еще одной аксиомы к уже несовместимой системе не может ухудшить ситуацию. Из-за независимости решение об использовании аксиомы выбора (или ее отрицания) в доказательстве не может быть принято путем обращения к другим аксиомам теории множеств. Решение должно быть принято на других основаниях.

Один аргумент в пользу использования аксиомы выбора состоит в том, что ее удобно использовать, потому что она позволяет доказать некоторые упрощающие предложения, которые иначе не могли бы быть доказаны. Многие теоремы, которые можно доказать с помощью выбора, носят элегантный общий характер: каждая идеальный в кольце содержится в максимальный идеал, каждый векторное пространство имеет основа, и каждый товар из компактные пространства компактный. Без выбранной аксиомы эти теоремы могут не выполняться для математических объектов большой мощности.

Доказательство результата независимости также показывает, что широкий класс математических утверждений, включая все утверждения, которые можно сформулировать на языке Арифметика Пеано, доказуемы в ZF тогда и только тогда, когда они доказуемы в ZFC.^[16] Заявления в этом классе включают утверждение, что P = NP, то Гипотеза Римана, и многие другие нерешенные математические задачи. Когда кто-то пытается решить проблемы этого класса, не имеет значения, используется ли ZF или ZFC, если единственный вопрос - это наличие доказательства. Однако возможно, что существует более короткое доказательство теоремы из ZFC, чем из ZF.

Избранная аксиома - не единственное важное утверждение, не зависящее от ZF. Например, гипотеза обобщенного континуума (GCH) не только не зависит от ZF, но и от ZFC. Однако ZF плюс GCH подразумевает AC, что делает GCH более сильным заявлением, чем AC, даже если они оба независимы от ZF.

Более сильные аксиомы

В аксиома конструктивности и гипотеза обобщенного континуума каждая из них подразумевает аксиому выбора и поэтому строго сильнее ее. В классовых теориях, таких как Теория множеств фон Неймана – Бернейса – Гёделя. и Теория множеств Морса – Келли, существует аксиома, называемая аксиома глобального выбора это сильнее, чем аксиома выбора для множеств, потому что она также применима к собственным классам. Аксиома глобального выбора следует из аксиома ограничения размера.

Эквиваленты

Есть важные утверждения, которые, исходя из аксиом ZF но ни AC, ни ¬AC не эквивалентны аксиоме выбора.^[17] Наиболее важные из них: Лемма Цорна и теорема о хорошем порядке. Фактически, Цермело изначально ввел аксиому выбора, чтобы формализовать свое доказательство теоремы о хорошем порядке.

• Теория множеств
  • Теорема о хорошем порядке: Каждый набор можно хорошо заказать. Следовательно, каждый кардинал имеет начальный порядковый номер.
  • Теорема Тарского о выборе: Для каждого бесконечного множества А, Существует биективная карта между наборами А и А×А.
  • Трихотомия: Если даны два набора, то либо они имеют одинаковую мощность, либо один имеет меньшую мощность, чем другой.
  • Учитывая два непустых множества, одно имеет сюръекцию к другому.
  • В Декартово произведение любого семейства непустых множеств непусто.
  • Теорема Кенига: Говоря простым языком, сумма последовательности кардиналов строго меньше, чем произведение последовательности более крупных кардиналов. (Причина использования термина «в просторечии» заключается в том, что сумма или произведение «последовательности» кардиналов не может быть определена без какого-либо аспекта аксиомы выбора.)
  • Каждый сюръективная функция имеет правый обратный.
• Теория порядка
  • Лемма Цорна: Каждый непустой частично упорядоченный набор, в котором каждая цепочка (т.е., полностью упорядоченное подмножество) имеет верхнюю границу, содержащую хотя бы один максимальный элемент.
  • Принцип максимума Хаусдорфа: В любом частично упорядоченном множестве каждое полностью упорядоченное подмножество содержится в максимальном полностью упорядоченном подмножестве. Ограниченный принцип «Каждое частично упорядоченное множество имеет максимальное полностью упорядоченное подмножество» также эквивалентно AC над ZF.
  • Лемма Тьюки: Каждая непустая коллекция конечный характер имеет максимальный элемент по включению.
  • Античейн принцип: каждый частично упорядоченный набор имеет максимальное антицепь.
• Абстрактная алгебра
  • Каждый векторное пространство имеет основа.^[18]
  • Теорема Крулля: Каждый единичный звенеть кроме тривиального кольца содержит максимальный идеал.
  • Для каждого непустого множества S Существует бинарная операция определено на S это дает ему структура группы.^[19] (А отменяющий бинарной операции достаточно, см. структура группы и аксиома выбора.)
  • Каждый набор представляет собой проективный объект в категория Набор наборов.^[20][21]
• Функциональный анализ
  • Замкнутый единичный шар двойственного к нормированное векторное пространство над реалами есть крайняя точка.
• Топология точек
  • Теорема Тихонова: Каждый товар из компактный топологические пространства компактный.
  • В топологии продукта закрытие произведения подмножеств равно произведению замыканий.
• Математическая логика
  • Если S это набор предложений логика первого порядка и B является последовательным подмножеством S, тогда B входит в набор, который является максимальным среди согласованных подмножеств S. Частный случай, когда S это набор все предложения первого порядка в данном подпись слабее, эквивалентно Теорема о булевом простом идеале; см. раздел «Более слабые формы» ниже.
• Теория графов
  • Каждый связный граф имеет остовное дерево.^[22]

Теория категорий

Есть несколько результатов в теория категорий которые используют аксиому выбора для своего доказательства. Эти результаты могут быть слабее, эквивалентны или сильнее, чем выбранная аксиома, в зависимости от прочности технических основ. Например, если кто-то определяет категории в терминах множеств, то есть как множества объектов и морфизмов (обычно называемых малая категория ), или даже локально малых категорий, гом-объектами которых являются множества, то нет категория всех наборов, поэтому теоретико-категориальную формулировку трудно применить ко всем множествам. С другой стороны, другие основополагающие описания теории категорий значительно сильнее, и идентичное теоретико-категориальное утверждение выбора может быть сильнее, чем стандартная формулировка а-ля теория классов, упомянутая выше.

Примеры теоретико-категориальных утверждений, требующих выбора, включают:

• Каждый маленький категория имеет скелет.
• Если две небольшие категории слабо эквивалентны, то они эквивалент.
• Каждый непрерывный функтор на малой полной категории, удовлетворяющий соответствующему условию множества решений, имеет левосопряженный (теорема Фрейда о присоединенном функторе).

Более слабые формы

Есть несколько более слабых утверждений, которые не эквивалентны аксиоме выбора, но тесно связаны между собой. Одним из примеров является аксиома зависимого выбора (ОКРУГ КОЛУМБИЯ). Еще более слабым примером является аксиома счетного выбора (AC_ω или CC), в котором говорится, что функция выбора существует для любого счетного множества непустых множеств. Этих аксиом достаточно для многих элементарных доказательств. математический анализ, и согласуются с некоторыми принципами, такими как измеримость по Лебегу всех множеств действительных чисел, которые нельзя доказать с помощью полной аксиомы выбора.

Другие аксиомы выбора, более слабые, чем аксиома выбора, включают Теорема о булевом простом идеале и аксиома униформизации. Первое эквивалентно в ZF существованию ультрафильтр содержащий каждый заданный фильтр, доказанный Тарским в 1930 году.

Результаты, требующие AC (или более слабые формы), но более слабые, чем он

Один из самых интересных аспектов аксиомы выбора - большое количество мест в математике, которые она занимает. Вот некоторые утверждения, которые требуют аксиомы выбора в том смысле, что они не доказуемы из ZF, но доказуемы из ZFC (ZF плюс AC). Равным образом эти утверждения верны для всех моделей ZFC, но неверны для некоторых моделей ZF.

• Теория множеств
  • Любой союз бесчисленного множества счетные множества само по себе счетно (потому что необходимо выбрать конкретный порядок для каждого из счетного множества множеств).
  • Если набор А является бесконечный, то существует инъекция от натуральные числа N к А (видеть Дедекинд бесконечный ).^[23]
  • Восемь определений конечный набор эквивалентны.^[24]
  • Каждый бесконечный игра ${displaystyle G_{S}}$ в котором ${displaystyle S}$ это Борель подмножество Пространство Бэра является определенный.
• Теория меры
  • В Теорема Витали о существовании неизмеримые множества который утверждает, что существует подмножество действительные числа это не Измеримый по Лебегу.
  • В Парадокс Хаусдорфа.
  • В Парадокс Банаха – Тарского.
  • В Мера Лебега счетного несвязный союз измеримых множеств равна сумме мер отдельных множеств.
• Алгебра
  • Каждый поле имеет алгебраическое замыкание.
  • Каждый расширение поля имеет основа трансцендентности.
  • Теорема Стоуна о представлении булевых алгебр нуждается в Теорема о булевом простом идеале.
  • В Теорема Нильсена – Шрайера, что каждая подгруппа свободной группы свободна.
  • Аддитивные группы р и C изоморфны.^[25][26]
• Функциональный анализ
  • В Теорема Хана – Банаха в функциональный анализ, позволяя продлить линейные функционалы
  • Теорема о том, что каждый Гильбертово пространство имеет ортонормированный базис.
  • В Теорема Банаха – Алаоглу о компактность наборов функционалов.
  • В Теорема Бэра о категории о полный метрические пространства, и его последствия, такие как теорема об открытом отображении и теорема о замкнутом графике.
  • На всяком бесконечномерном топологическом векторном пространстве существует разрывная линейная карта.
• Общая топология
  • Равномерное пространство компактно тогда и только тогда, когда оно полно и вполне ограничено.
  • Каждый Тихоновское пространство имеет Каменно-чешская компактификация.
• Математическая логика
  • Теорема Гёделя о полноте для логики первого порядка: каждый последовательный набор предложений первого порядка имеет завершение. То есть каждый непротиворечивый набор предложений первого порядка может быть расширен до максимального непротиворечивого набора.

Возможные эквивалентные значения AC

Есть несколько исторически важных теоретико-множественных утверждений, подразумеваемых AC, чья эквивалентность AC открыта. Принцип разделения, который был сформулирован до самого AC, был процитирован Цермело как оправдание для веры в AC. В 1906 году Рассел объявил PP эквивалентным, но вопрос о том, следует ли из принципа разделения AC, все еще является самой старой открытой проблемой в теории множеств, а эквивалентность других утверждений - такие же трудные старые открытые проблемы. В каждом известен Модель ZF, в которой выбор невозможен, эти утверждения также терпят неудачу, но неизвестно, могут ли они выполняться без выбора.

• Теория множеств
  • Принцип разбиения: если есть сюрприз из А к B, существует инъекция из B к А. В равной степени каждый раздел п набора S меньше или равно S по размеру.
  • Converse Теорема Шредера – Бернштейна.: если у двух наборов есть отклонения друг от друга, они равны.
  • Принцип слабого разбиения: разбиение множества S не может быть строго больше, чем S. Если WPP выполняется, это уже означает существование неизмеримого множества. Каждое из трех предыдущих утверждений подразумевается предыдущим, но неизвестно, можно ли отменить любое из этих утверждений.
  • Нет бесконечной убывающей последовательности кардиналов. Об эквивалентности предположил Шенфлис в 1905 году.
• Абстрактная алгебра
  • Теорема вложения Хана: Каждая упорядоченная абелева группа грамм order-embeds как подгруппа аддитивной группы ℝ^Ω наделен лексикографический порядок, где Ω - множество классов архимедовой эквивалентности Ω. Эта эквивалентность была высказана Ханом в 1907 году.

Более сильные формы отрицания переменного тока

Если мы будем сокращать до BP утверждение, что каждый набор действительных чисел имеет собственность Бэра, то BP сильнее, чем ¬AC, который утверждает, что любой функции выбора не существует, возможно, только на одном множестве непустых множеств. Усиленные отрицания могут быть совместимы с ослабленными формами AC. Например, ZF + DC^[27] + BP согласован, если ZF согласован.

Также согласно ZF + DC, каждый набор вещественных чисел Измеримый по Лебегу; однако этот результат согласованности из-за Роберт М. Соловей, не может быть доказан в самом ZFC, но требует умеренного большой кардинал предположение (наличие недоступный кардинал ). Гораздо сильнее аксиома детерминированности, или AD, означает, что каждый набор действительных чисел измерим по Лебегу, обладает свойством Бэра и имеет идеальный набор собственности (все три результата опровергаются самим AC). ZF + DC + AD непротиворечива при условии, что согласована достаточно сильная кардинальная аксиома (существование бесконечно большого числа Кардиналы Вудена ).

Система аксиоматической теории множеств Куайна, «Новые основы» (НФ), получила свое название от названия («Новые основы математической логики») статьи 1937 года, в которой она была представлена. В аксиоматической системе NF аксиома выбора может быть опровергнута.^[28]

Утверждения, согласующиеся с отрицанием переменного тока

Существуют модели теории множеств Цермело-Френкеля, в которых аксиома выбора неверна. Мы будем сокращать «теория множеств Цермело-Френкеля плюс отрицание аксиомы выбора» на ZF¬C. Для некоторых моделей ZF¬C можно доказать отрицание некоторых стандартных фактов. Любая модель ZF¬C также является моделью ZF, поэтому для каждого из следующих утверждений существует модель ZF, в которой это утверждение верно.

• В некоторых моделях есть набор, который можно разделить на строго большее количество классов эквивалентности, чем в исходном наборе есть элементы, и функция, область определения которой строго меньше, чем ее диапазон. На самом деле так происходит во всех известен модели.
• Есть функция ж от действительных чисел к действительным числам, таким, что ж не является непрерывным в а, но ж является последовательно непрерывный в а, т.е. для любой последовательности {Икс_п} сходящийся к а, lim_п f (Икс_п) = f (а).
• В некоторых моделях существует бесконечный набор действительных чисел без счетно бесконечного подмножества.
• В некоторых моделях действительные числа представляют собой счетное объединение счетных множеств.^[29] Это не означает, что действительные числа являются счетными: как указывалось выше, чтобы показать, что счетное объединение счетных множеств само является счетным, требуется Аксиома счетного выбора.
• В какой-то модели есть поле без алгебраического замыкания.
• Во всех моделях ZF¬C есть векторное пространство без базиса.
• В какой-то модели есть векторное пространство с двумя базами разной мощности.
• В некоторых моделях есть бесплатный полная логическая алгебра на счетном множестве генераторов.^[30]
• В какой-то модели есть набор, который нельзя упорядочить линейно.
• Существует модель ZF¬C, в которой каждое множество в R^п является измеримый. Таким образом, можно исключить противоречивые результаты, такие как Парадокс Банаха – Тарского которые доказываются в ZFC. Кроме того, это возможно при условии, что Аксиома зависимого выбора, который слабее, чем AC, но достаточен для развития большей части реальный анализ.
• Во всех моделях ZF¬C гипотеза обобщенного континуума не держит.

Доказательства см. Jech (2008).

Кроме того, налагая условия определимости на множества (в смысле описательная теория множеств ) часто можно доказать ограниченные версии аксиомы выбора из аксиом, несовместимых с общим выбором. Это появляется, например, в Лемма мощовакиса о кодировании.

Аксиома выбора в теории типов

В теория типов, другой вид утверждения известен как аксиома выбора. Эта форма начинается с двух типов, σ и τ, и отношения р между объектами типа σ и объектами типа τ. Аксиома выбора утверждает, что если для каждого Икс типа σ существует у типа τ такой, что р(Икс,у), то существует функция ж от объектов типа σ к объектам типа τ таким, что р(Икс,ж(Икс)) выполняется для всех Икс типа σ:

${displaystyle (forall x^{sigma })(exists y^{ au })R(x,y) o (exists f^{sigma o au })(forall x^{sigma })R(x,f(x)).}$

В отличие от теории множеств, аксиома выбора в теории типов обычно формулируется как схема аксиом, в котором р варьируется по всем формулам или по всем формулам определенной логической формы.

Цитаты

Очевидно, что аксиома выбора верна, принцип хорошего порядка заведомо ложное, и кто может рассказать о Лемма Цорна ?

— Джерри Бона^[31]

Это шутка: хотя все три математически эквивалентны, многие математики находят аксиому выбора интуитивной, принцип хорошего упорядочения - парадоксальным, а лемму Цорна - слишком сложной для любой интуиции.

Аксиома выбора необходима для выбора набора из бесконечного числа пар носков, но не из бесконечного числа пар обуви.

— Бертран Рассел^[32]

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

Тарский попытался опубликовать свою теорему [эквивалентность AC и «всякое бесконечное множество А имеет ту же мощность, что и А × А", см. выше] в Comptes Rendus, но Фреше и Лебег отказался его представить. Фреше писал, что импликация между двумя хорошо известными [истинными] предложениями не является новым результатом, а Лебег писал, что импликация между двумя ложными предложениями не представляет интереса.

Польско-американский математик Ян Мыцельски рассказывает об этом анекдоте в статье 2006 года в Уведомлениях AMS.^[33]

Аксиома получила свое название не потому, что математики предпочитают ее другим аксиомам.

— А. К. Дьюдни

Это цитата из известного День дурака статья в компьютерные развлечения столбец Scientific American, Апрель 1989 г.

Примечания

1. Цермело 1904 г..
2. Jech 1977, п. 351
3. Jech, 1977, с. 348ff; Мартин-Лёф 2008, стр. 210. Согласно Мендельсон 1964, п. 201:

   Статус Аксиомы выбора в последние годы стал менее спорным. Большинству математиков это кажется вполне правдоподобным и имеет так много важных приложений практически во всех областях математики, что отказ от него показался бы умышленным увлечением практикующего математика.

4. Херрлих 2006, п. 9. Согласно Суппес 1972, п. 243, это была формулировка аксиомы выбора, которая первоначально была дана Цермело 1904 г.. Смотрите также Халмос 1960, п. 60 для этой формулы.
5. Суппес 1972, п. 240.
6. Tourlakis (2003), стр. 209–210, 215–216.
7. Френкель, Абрахам А.; Бар-Гилель, Иегошуа; Леви, Азриэль (1973), Основы теории множеств (2-е изд.), Амстердам-Лондон: North-Holland Publishing Co., стр. 69–70, ISBN  9780080887050, МИСТЕР  0345816.
8. Розенблум, Пол К. (2005), Элементы математической логики, Courier Dover Publications, стр. 147, ISBN  9780486446172.
9. Доусон, Дж. У. (август 2006 г.), «Потрясающие основы или революционная перестройка? Столетняя оценка влияния Курта Гёделя на логику, математику и информатику», Proc. 21-й ежегодный симпозиум IEEE по логике в компьютерных науках (LICS 2006), стр. 339–341, Дои:10.1109 / LICS.2006.47, ISBN  978-0-7695-2631-7, S2CID  15526447, Аксиома выбора, хотя он был использован бессознательно во многих аргументов в анализе, стал спорным когда-то сделал явным, не только из-за своей неконструктивной характер, а потому, что он подразумевает такие чрезвычайно неинтуитивными последствия, как парадокс Банаха-Тарского..
10. Пер Мартин-Лёф, Интуиционистская теория типов, 1980.Энн Сьерп Трельстра, Метаматематическое исследование интуиционистской арифметики и анализа, Спрингер, 1973.
11. Эрретт Бишоп и Дуглас С. Бриджес, Конструктивный анализ, Springer-Verlag, 1985.
12. Мартин-Лёф, Пер (2006). «100 лет аксиомы выбора Цермело: в чем была проблема?». Компьютерный журнал. 49 (3): 345–350. Bibcode:1980CompJ..23..262L. Дои:10.1093 / comjnl / bxh162.
13. Фред Ричман, «Конструктивная математика без выбора», в: Воссоединение антиподов - конструктивные и нестандартные взгляды на континуум (П. Шустер и др., Ред.), Synthèse Library 306, 199–205, Kluwer Academic Publishers, Амстердам, 2001.
14. Гёдель, Курт (9 ноября 1938). «Непротиворечивость аксиомы выбора и гипотезы обобщенного континуума». Труды Национальной академии наук Соединенных Штатов Америки. 24 (12): 556–557. Bibcode:1938ПНАС ... 24..556Г. Дои:10.1073 / пнас.24.12.556. ЧВК  1077160. PMID  16577857.
15. Коэн, Пол (2019). «Независимость аксиомы выбора» (PDF). Библиотеки Стэнфордского университета. Получено 22 марта 2019.
16. Это потому, что арифметические утверждения абсолютный к конструируемая вселенная L. Теорема Шенфилда об абсолютности дает более общий результат.
17. Видеть Мур 2013, pp. 330–334, чтобы получить структурированный список из 74 эквивалентов. Видеть Ховард и Рубин 1998, pp. 11–16, для 86 эквивалентов со ссылками на источники.
18. Бласс, Андреас (1984). «Существование базисов подразумевает аксиому выбора». Аксиоматическая теория множеств (Boulder, Colo., 1983). Современная математика. 31. Провиденс, Род-Айленд: Американское математическое общество. С. 31–33. Дои:10.1090 / conm / 031/763890. МИСТЕР  0763890.
19. А. Хайнал, А. Кертес: Некоторые новые алгебраические эквиваленты аксиомы выбора, Publ. Математика. Дебрецен, 19(1972), 339–340, см. Также Х. Рубин, Дж. Рубин, Эквиваленты аксиомы выбора, II, Северная Голландия, 1985, с. 111.
20. Awodey, Стив (2010). Теория категорий (2-е изд.). Оксфорд: Издательство Оксфордского университета. стр.20 –24. ISBN  978-0199237180. OCLC  740446073.
21. проективный объект в nLab
22. Серр, Жан-Пьер (2003), Деревья, Springer Monographs in Mathematics, Springer, p. 23; Соукуп, Лайош (2008), «Бесконечная комбинаторика: от конечного к бесконечному», Горизонты комбинаторики, Математические исследования Общества Бойяи, 17, Берлин: Springer, стр. 189–213, CiteSeerX  10.1.1.222.5699, Дои:10.1007/978-3-540-77200-2_10, ISBN  978-3-540-77199-9, МИСТЕР  2432534. См., В частности, теорему 2.1, стр. 192–193.
23. Это показано Jech 2008, pp. 119–131, аксиома счетного выбора влечет эквивалентность бесконечных и бесконечных по Дедекинду множеств, но что эквивалентность бесконечных и бесконечных по Дедекинду множеств не влечет аксиомы счетного выбора в ZF.
24. Это было показано Леви 1958 и другие, использующие модели Мостовского, утверждают, что восемь определений конечного множества независимы в ZF без AC, хотя они эквивалентны, когда предполагается AC. Определения: I-конечный, Ia-конечный, II-конечный, III-конечный, IV-конечный, V-конечный, VI-конечный и VII-конечный. I-конечность - это то же самое, что и нормальная конечность. IV-конечность - это то же самое, что конечность Дедекинда.
25. «[FOM] Изоморфны (C, +) и (R, +)».
26. Эш, К. Дж. «Следствие аксиомы выбора». Журнал Австралийского математического общества. Получено 27 марта 2018.
27. Аксиома зависимого выбора
28. "Новые основы Куайна". Стэнфордская энциклопедия философии. Получено 10 ноября 2017.
29. Jech 2008, pp. 142–144, теорема 10.6 с доказательством.
30. Стави, Джонатан (1974). «Модель ZF с бесконечной свободной полной булевой алгеброй». Израильский математический журнал. 20 (2): 149–163. Дои:10.1007 / BF02757883. S2CID  119543439.
31. Кранц, Стивен Г. (2002), «Аксиома выбора», Справочник по логике и методам доказательства для компьютерных наук, Springer, стр. 121–126, Дои:10.1007/978-1-4612-0115-1_9, ISBN  978-1-4612-6619-8.
32. Метафора ботинок и носков была дана в 1919 г. Рассел 1993 С. 125–127. Он предположил, что миллионер мог ℵ₀ пары сапог и ℵ₀ пары носков.

    Среди ботинок мы можем различать правые и левые, и поэтому мы можем выбрать по одному из каждой пары, а именно, мы можем выбрать все правильные ботинки или все левые ботинки; но с носками такой принцип отбора не напрашивается сам собой, и мы не можем быть уверены, если не примем аксиому мультипликативности, что существует какой-либо класс, состоящий из одного носка из каждой пары.

    Рассел обычно использовал термин «мультипликативная аксиома» для аксиомы выбора. Ссылаясь на упорядочение счетно бесконечного множества пар объектов, он писал:

    С ботинками это сделать нетрудно. В пары даны как образующие ℵ₀, а следовательно, как поле прогрессии. В каждой паре сначала возьмите левый ботинок, а второй - правый, сохраняя порядок пары неизменным; таким образом мы получаем прогрессию всех ботинок. Но с носками нам придется произвольно выбирать для каждой пары, что ставить первым; а бесконечное количество произвольных выборов невозможно. Если мы не сможем найти правило для выбора, то есть отношения, которое является селектором, мы не знаем, что выбор даже теоретически возможен.

    Затем Рассел предлагает использовать в качестве селектора расположение центра масс каждого носка.

33. Мыцельски, Ян (2006), «Система аксиом теории множеств для рационалистов» (PDF), Уведомления Американского математического общества, 53 (2): 206–213, МИСТЕР  2208445.

Рекомендации

• Халмос, Пол Р. (1960). Наивная теория множеств. Университетская серия по математике. Принстон, Нью-Джерси: компания van Nostrand. Zbl  0087.04403.
• Херрлих, Хорст (2006). Аксиома выбора. Конспект лекций по математике. 1876 ​​г., Берлин: Springer-Verlag. ISBN  978-3-540-30989-5.
• Говард, Пол; Рубин, Жан Э. (1998). Последствия аксиомы выбора. Математические обзоры и монографии. 59. Провиденс, Род-Айленд: Американское математическое общество. ISBN  9780821809778.
• Jech, Thomas (2008) [1973]. Аксиома выбора. Минеола, Нью-Йорк: Dover Publications. ISBN  978-0-486-46624-8.
• Jech, Thomas (1977). «Об аксиоме выбора». У Джона Барвайса (ред.). Справочник по математической логике.
• Леви, Азриэль (1958). «Независимость различных определений конечности» (PDF). Fundamenta Mathematicae. 46: 1–13. Дои:10.4064 / fm-46-1-1-13.
• Пер Мартин-Лёф, «100 лет аксиомы выбора Цермело: в чем была проблема?», В Логицизм, интуиционизм и формализм: что из них стало?, Стен Линдстрем, Эрик Палмгрен, Кристер Сегерберг и Вигго Столтенберг-Хансен, редакторы (2008). ISBN  1-4020-8925-2
• Мендельсон, Эллиотт (1964). Введение в математическую логику. Нью-Йорк: Ван Ностранд Рейнхольд.
• Мур, Грегори Х. (1982). Аксиома выбора Цермело, ее происхождение, развитие и влияние. Springer. ISBN  978-0-387-90670-6., доступный как Dover Publications перепечатка, 2013, ISBN  0-486-48841-1.
• Мур, Грегори Х (2013) [1982]. Аксиома выбора Цермело: ее происхождение, развитие и влияние. Минеола, Нью-Йорк: Dover Publications. ISBN  978-0-486-48841-7.
• Герман Рубин, Жан Э. Рубин: Эквиваленты аксиомы выбора. Северная Голландия, 1963 год. Переиздано Эльзевир, Апрель 1970 г. ISBN  0-7204-2225-6.
• Герман Рубин, Жан Э. Рубин: эквиваленты аксиомы выбора II. Северная Голландия / Эльзевир, июль 1985 г., ISBN  0-444-87708-8.
• Рассел, Бертран (1993) [1919]. Введение в математическую философию. Нью-Йорк: Dover Publications. ISBN  978-0-486-27724-0.
• Суппес, Патрик (1972) [1960]. Аксиоматическая теория множеств. Минеола, Нью-Йорк: Дувр. ISBN  978-0-486-61630-8.
• Джордж Турлакис, Лекции по логике и теории множеств. Vol. II: Теория множеств, Издательство Кембриджского университета, 2003. ISBN  0-511-06659-7
• Цермело, Эрнст (1904). "Beweis, dass jede Menge wohlgeordnet werden kann" (перепечатка). Mathematische Annalen. 59 (4): 514–16. Дои:10.1007 / BF01445300. S2CID  124189935.
• Эрнст Цермело, "Untersuchungen über die Grundlagen der Mengenlehre I", Mathematische Annalen 65: (1908) стр. 261–81. Скачать PDF через digizeitschriften.de

Переведено на: Жан ван Хейеноорт, 2002. От Фреге до Гёделя: Справочник по математической логике, 1879–1931 гг.. Новый выпуск. Издательство Гарвардского университета. ISBN  0-674-32449-8

• 1904. «Доказательство того, что каждый набор можно хорошо заказать», 139-41.
• 1908. "Исследования по основам теории множеств I", 199–215.

внешняя ссылка

• Аксиома выбора вход в Springer Энциклопедия математики.
• Аксиома выбора и ее аналоги запись в ProvenMath. Включает формальное утверждение аксиомы выбора, принципа максимума Хаусдорфа, леммы Цорна и формальные доказательства их эквивалентности до мельчайших деталей.
• Последствия аксиомы выбора, по книге Пол Ховард и Жан Рубин.
• «Аксиома выбора» запись Джон Лейн Белл в Стэнфордская энциклопедия философии.