Аксиома выбора

Аксиома теории множеств

Иллюстрация аксиомы выбора, где каждое множество S _i представлено как банка, а его элементы — как шарики. Каждый элемент x _i представлен как шарик справа. Цвета используются для указания функциональной ассоциации шариков после принятия аксиомы выбора. Существование такой функции выбора в общем случае не зависит от ZF для наборов бесконечной мощности, даже если все S _i конечны.

(S _i ) — это бесконечное индексированное семейство множеств, индексированных по действительным числам R ; то есть, существует множество S _i для каждого действительного числа i , с небольшой выборкой, показанной выше. Каждое множество содержит по крайней мере один, а возможно и бесконечно много элементов. Аксиома выбора позволяет нам выбрать один элемент из каждого множества, образуя соответствующее семейство элементов ( x _i ), также индексированных по действительным числам, причем x _i взят из S _i . В общем случае коллекции могут быть индексированы по любому множеству I , (называемому индексным множеством, элементы которого используются в качестве индексов для элементов в множестве), а не только по R .

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

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

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

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

Заявление

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

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

Формально это можно выразить следующим образом:

${\displaystyle \forall X\left[\varnothing \notin X\implies \exists f\colon X\rightarrow \bigcup _{A\in X}A\quad \forall A\in X\,(f(A)\in A)\right]\,.}$

Таким образом, отрицание аксиомы может быть выражено как существование набора непустых множеств, не имеющего функции выбора. Формально это может быть выведено с использованием логической эквивалентности к . ${\displaystyle \neg \forall X\left[P(X)\to Q(X)\right]}$ ${\displaystyle \exists X\left[P(X)\land \neg Q(X)\right]}$

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

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

Номенклатура

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

• AC – Аксиома выбора. Реже используется AoC. ^[4]
• ZF – Теория множеств Цермело–Френкеля, исключающая аксиому выбора.
• ZFC – теория множеств Цермело–Френкеля, расширенная за счет включения аксиомы выбора.

Варианты

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

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

Для любого множества X , если пустое множество не является элементом X и элементы X попарно не пересекаются , то существует множество C , такое что его пересечение с любым из элементов X содержит ровно один элемент. ^[5]

Это можно формализовать в логике первого порядка следующим образом:

∀x (

∃o (o ∈ x ∧ ¬∃n (n ∈ o)) ∨

∃a ∃b ∃c (a ∈ x ∧ b ∈ x ∧ c ∈ a ∧ c ∈ b ∧ ¬(a = b)) ∨

∃c ∀e (e ∈ x → ∃a (a ∈ e ∧ a ∈ c ∧ ∀b ((b ∈ e ∧ b ∈ c) → a = b))))

Обратите внимание, что P ∨ Q ∨ R логически эквивалентно (¬P ∧ ¬Q) → R.
На английском языке это предложение первого порядка выглядит так:

Для любого множества X ,

X содержит пустое множество как элемент или

элементы X не являются попарно непересекающимися или

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

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

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

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

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

Каждый набор имеет функцию выбора. ^[6]

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

Другим аргументом против аксиомы выбора является то, что она подразумевает существование объектов, которые могут показаться контринтуитивными. ^[10] Одним из примеров является парадокс Банаха-Тарского , который гласит, что можно разложить 3-мерный сплошной единичный шар на конечное число частей и, используя только вращения и переносы, собрать части в два сплошных шара, каждый с тем же объемом, что и исходный. Части в этом разложении, построенном с использованием аксиомы выбора, являются неизмеримыми множествами .

Более того, недавно были отмечены парадоксальные последствия аксиомы выбора для принципа отсутствия сигнализации в физике. ^[11]

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

Теоремы ZF верны в любой модели этой теории, независимо от истинности или ложности аксиомы выбора в этой конкретной модели. Нижеперечисленные импликации выбора, включая более слабые версии самой аксиомы, перечислены, поскольку они не являются теоремами ZF. Например, парадокс Банаха–Тарского не является ни доказуемым, ни опровергаемым из одной только ZF: невозможно построить требуемое разложение единичного шара в ZF, но также невозможно доказать, что такого разложения не существует. Такие утверждения можно перефразировать как условные утверждения, например, «Если выполняется AC, то разложение в парадоксе Банаха–Тарского существует». Такие условные утверждения доказуемы в ZF, когда исходные утверждения доказуемы из ZF и аксиомы выбора.

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

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

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

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

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

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

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

Еще с 1922 года было известно, что аксиома выбора может не выполняться в варианте ZF с праэлементами , с помощью техники моделей перестановок, введенной Авраамом Френкелем ^[16] и развитой далее Анджеем Мостовским . ^[17] Базовую технику можно проиллюстрировать следующим образом: пусть x _n и y _n будут различными праэлементами для n = 1, 2, 3... , и построим модель, в которой каждый набор симметричен относительно замены x _n ↔ y _n для всех, кроме конечного числа n . Тогда набор X = {{ x ₁ , y ₁ }, { x ₂ , y ₂ }, { x ₃ , y ₃ }, ...} может быть в модели, но такие наборы, как { x ₁ , x ₂ , x ₃ , ...} , не могут, и, таким образом, X не может иметь функцию выбора.

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

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

Одним из аргументов в пользу использования аксиомы выбора является то, что она удобна, поскольку позволяет доказать некоторые упрощающие предложения, которые в противном случае не могли бы быть доказаны. Многие теоремы, доказываемые с использованием выбора, имеют элегантный общий характер: мощности любых двух множеств сравнимы, каждое нетривиальное кольцо с единицей имеет максимальный идеал , каждое векторное пространство имеет базис , каждый связный граф имеет остовное дерево , и каждое произведение компактных пространств компактно , среди многих других. Часто аксиома выбора позволяет обобщить теорему на «большие» объекты. Например, без аксиомы выбора доказывается, что каждое векторное пространство конечной размерности имеет базис, но обобщение на все векторные пространства требует аксиомы выбора. Аналогично, конечное произведение компактных пространств может быть доказано как компактное без аксиомы выбора, но обобщение на бесконечные произведения ( теорема Тихонова ) требует аксиомы выбора.

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

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

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

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

Эквиваленты

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

• Теория множеств
  • Теорема Тарского о выборе : Для любого бесконечного множества A существует биективное отображение между множествами A и A × A.
  • Трихотомия : если даны два множества, то либо они имеют одинаковую мощность, либо одно из них имеет меньшую мощность, чем другое.
  • Если даны два непустых множества, одно из них имеет сюръекцию на другое.
  • Каждая сюръективная функция имеет правую обратную .
  • Декартово произведение любого семейства непустых множеств непусто. Другими словами, каждое семейство непустых множеств имеет функцию выбора ( т.е. функцию, которая отображает каждое из непустых множеств в один из его элементов).
  • Теорема Кёнига : В разговорной речи сумма последовательности кардиналов строго меньше произведения последовательности больших кардиналов. (Причина термина «в разговорной речи» заключается в том, что сумма или произведение «последовательности» кардиналов не могут быть определены без некоторого аспекта аксиомы выбора.)
  • Теорема о хорошем порядке : Каждое множество может быть хорошо упорядочено. Следовательно, каждый кардинал имеет начальный ординал .
  • Лемма Цорна : Каждое непустое частично упорядоченное множество, в котором каждая цепь ( т. е . полностью упорядоченное подмножество) имеет верхнюю границу, содержит по крайней мере один максимальный элемент.
  • Максимальный принцип Хаусдорфа : Каждое частично упорядоченное множество имеет максимальную цепь. Эквивалентно, в любом частично упорядоченном множестве каждая цепь может быть расширена до максимальной цепи.
  • Лемма Тьюки : Любая непустая совокупность конечного характера имеет максимальный элемент относительно включения.
  • Принцип антицепи : Каждое частично упорядоченное множество имеет максимальную антицепь . Эквивалентно, в любом частично упорядоченном множестве каждая антицепь может быть расширена до максимальной антицепи.
  • Множество любого ординала может быть вполне упорядочено.
• Абстрактная алгебра
  • Каждое векторное пространство имеет базис ( т.е. линейно независимое охватывающее подмножество). Другими словами, векторные пространства эквивалентны свободным модулям. ^[22]
  • Теорема Крулля : Каждое единичное кольцо (кроме тривиального) содержит максимальный идеал . Эквивалентно, в любом нетривиальном единичном кольце каждый идеал может быть расширен до максимального идеала.
  • Для каждого непустого множества S существует бинарная операция, определенная на S , которая задает ему групповую структуру . ^[23] ( Достаточно сокращающей бинарной операции, см. групповую структуру и аксиому выбора .)
  • Каждая свободная абелева группа проективна . ^[24 ]
  • Критерий Бэра: Каждая делимая абелева группа инъективна . ^[24 ]
  • Каждое множество является проективным объектом в категории Множество множеств. ^{[25] [26]}
• Функциональный анализ
  • Замкнутый единичный шар двойственного к нормированному векторному пространству над действительными числами имеет крайнюю точку .
• Топология точечно-множественного типа
  • Декартово произведение любого семейства связных топологических пространств связно.
  • Теорема Тихонова : Декартово произведение любого семейства компактных топологических пространств компактно.
  • В топологии произведения замыкание произведения подмножеств равно произведению замыканий.
• Математическая логика
  • Если S — множество предложений логики первого порядка , а B — непротиворечивое подмножество S , то B входит в множество, которое является максимальным среди непротиворечивых подмножеств S. Частный случай, когда S — множество всех предложений первого порядка в заданной сигнатуре , является более слабым и эквивалентен теореме о простом идеале Буля ; см. раздел «Более слабые формы» ниже.
• Теория графов
  • Каждый связный граф имеет остовное дерево . Эквивалентно, каждый непустой граф имеет остовный лес. ^[27]

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

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

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

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

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

Есть несколько более слабых утверждений, которые не эквивалентны аксиоме выбора, но тесно связаны с ней. Одним из примеров является аксиома зависимого выбора (DC). Еще более слабым примером является аксиома счетного выбора (AC _ω или CC), которая утверждает, что функция выбора существует для любого счетного множества непустых множеств. Эти аксиомы достаточны для многих доказательств в элементарном математическом анализе и согласуются с некоторыми принципами, такими как измеримость по Лебегу всех множеств действительных чисел, которые опровергаются из полной аксиомы выбора.

При наличии порядкового параметра α ≥ ω+2 — для любого множества S с рангом меньше α, S вполне упорядочиваемо. При наличии порядкового параметра α ≥ 1 — для любого множества S с числом Хартогса меньше ω _α , S вполне упорядочиваемо. По мере увеличения порядкового параметра они приближаются к полной аксиоме выбора все ближе и ближе.

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

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

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

• Теория множеств
  • Лемма об ультрафильтре (с ZF) может быть использована для доказательства аксиомы выбора для конечных множеств: если заданы и набор непустых конечных множеств, их произведение непусто. ^[28] ${\displaystyle I\neq \varnothing }$ ${\displaystyle \left(X_{i}\right)_{i\in I}}$ ${\displaystyle \prod _{i\in I}X_{i}}$
  • Объединение любого счетного семейства счетных множеств счетно (это требует счетного выбора , но не полной аксиомы выбора).
  • Если множество A бесконечно , то существует инъекция из натуральных чисел N в A (см. Дедекиндово бесконечное ). ^[29]
  • Восемь определений конечного множества эквивалентны. ^[30]
  • Каждая бесконечная игра , в которой есть борелевское подмножество пространства Бэра , определена . ${\displaystyle G_{S}}$ ${\displaystyle S}$
• Каждый бесконечный кардинал κ удовлетворяет условию 2× κ = κ . ^[31]
• Теория меры
  • Теорема Витали о существовании неизмеримых множеств , которая утверждает, что существует подмножество действительных чисел , которое не измеримо по Лебегу .
  • Существуют измеримые по Лебегу подмножества действительных чисел, которые не являются борелевскими множествами . То есть, борелевская σ-алгебра действительных чисел (которая порождается всеми действительными интервалами) отличается от σ-алгебры меры Лебега действительных чисел.
  • Парадокс Хаусдорфа .
  • Парадокс Банаха- Тарского .
• Алгебра
  • Каждое поле имеет алгебраическое замыкание .
  • Каждое расширение поля имеет основу трансцендентности .
  • Каждое бесконечномерное векторное пространство содержит бесконечное линейно независимое подмножество (это требует зависимого выбора , но не полной аксиомы выбора).
  • Теорема Стоуна о представлении булевых алгебр требует теоремы о простом булевом идеале .
  • Теорема Нильсена –Шрайера о том, что каждая подгруппа свободной группы свободна.
  • Аддитивные группы R и C изоморфны. ^{[32] [33]}
• Функциональный анализ
  • Теорема Хана–Банаха в функциональном анализе , допускающая расширение линейных функционалов .
  • Теорема о том, что каждое гильбертово пространство имеет ортонормированный базис.
  • Теорема Банаха –Алаоглу о компактности множеств функционалов.
  • Теорема Бэра о категории полных метрических пространств и ее следствия, такие как теорема об открытом отображении и теорема о замкнутом графике .
  • На каждом бесконечномерном топологическом векторном пространстве существует разрывное линейное отображение .
• Общая топология
  • Равномерное пространство компактно тогда и только тогда, когда оно полно и вполне ограничено.
  • Каждое тихоновское пространство имеет компактификацию Стоуна–Чеха .
• Математическая логика
  • Теорема Гёделя о полноте для логики первого порядка: каждый непротиворечивый набор предложений первого порядка имеет завершение. То есть, каждый непротиворечивый набор предложений первого порядка может быть расширен до максимального непротиворечивого набора.
  • Теорема компактности : Если — множество предложений первого порядка (или, альтернативно, нулевого порядка ) , такое, что каждое конечное подмножество имеет модель , то имеет модель. ^[34] ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$

Возможные эквивалентные последствия переменного тока

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

• Теория множеств
  • Принцип разбиения: если есть сюръекция из A в B , то есть инъекция из B в A. Эквивалентно, каждое разбиение P множества S меньше или равно S по размеру.
  • Обратная теорема Шредера–Бернштейна : если два множества имеют сюръекции друг на друга, то они равночисленны.
  • Слабый принцип разбиения: если есть инъекция и сюръекция из A в B , то A и B равночисленны. Эквивалентно, разбиение множества S не может быть строго больше, чем S. Если WPP выполняется, это уже подразумевает существование неизмеримого множества. Каждое из предыдущих трех утверждений подразумевается предыдущим, но неизвестно, можно ли обратить любое из этих импликаций.
  • Не существует бесконечной убывающей последовательности кардиналов. Эквивалентность была выдвинута Шёнфлисом в 1905 году.
• Абстрактная алгебра
  • Теорема вложения Хана : Каждая упорядоченная абелева группа G упорядоченно вкладывается как подгруппа аддитивной группы, наделенной лексикографическим порядком , где Ω — множество архимедовых классов эквивалентности G. Эта эквивалентность была выдвинута Ханом в 1907 году. ${\displaystyle \mathbb {R} ^{\Omega }}$

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

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

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

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

Высказывания, подразумевающие отрицание AC

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

• Отрицание слабого принципа разбиения : существует множество, которое можно разбить на строго большее количество классов эквивалентности, чем исходное множество имеет элементов, и функция, область определения которой строго меньше ее диапазона. Фактически, это имеет место во всех известных моделях.
• Существует функция f из действительных чисел в действительные числа такая, что f не является непрерывной в точке a , но f последовательно непрерывна в точке a , т. е. для любой последовательности { x _n }, сходящейся к a , lim _n f( x _n )=f(a).
• Существует бесконечное множество действительных чисел без счетно бесконечного подмножества.
• Действительные числа представляют собой счетное объединение счетных множеств. ^[38] Это не означает, что действительные числа счетны: как указано выше, чтобы показать, что счетное объединение счетных множеств само по себе счетно, требуется аксиома счетного выбора .
• Существует поле без алгебраического замыкания.
• Во всех моделях ZF¬C имеется векторное пространство без базиса.
• Имеется векторное пространство с двумя базисами разной мощности.
• Существует свободная полная булева алгебра на счетном числе образующих. ^[39]
• Существует множество, которое невозможно упорядочить линейно .
• Существует модель ZF¬C, в которой каждое множество в R n измеримо ^. Таким образом, можно исключить контринтуитивные результаты, такие как парадокс Банаха–Тарского, которые доказуемы в ZFC. Более того, это возможно при допущении аксиомы зависимого выбора , которая слабее, чем AC, но достаточна для разработки большей части реального анализа .
• Во всех моделях ZF¬C обобщенная континуальная гипотеза не выполняется.

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

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

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

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

${\displaystyle (\forall x^{\sigma })(\exists y^{\tau })R(x,y)\to (\exists f^{\sigma \to \tau })(\forall x^{\sigma })R(x,f(x)).}$

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

Примечания

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

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

4. Розенберг, Стивен (21 декабря 2021 г.). Приглашение в абстрактную алгебру. CRC Press. ISBN 9781000516333.
5. Herrlich 2006, стр. 9. Согласно Suppes 1972, стр. 243, это была формулировка аксиомы выбора, которая была первоначально дана Zermelo 1904. См. также Halmos 1960, стр. 60 для этой формулировки.
6. Саппс 1972, стр. 240.
7. Турлакис (2003), стр. 209–210, 215–216.
8. Френкель, Авраам А .; Бар-Хиллель, Иегошуа ; Леви, Азриэль (1973), Основы теории множеств (2-е изд.), Амстердам-Лондон: North-Holland Publishing Co., стр. 69–70, ISBN 9780080887050, МР  0345816.
9. Розенблум, Пол К. (2005), Элементы математической логики, Courier Dover Publications, стр. 147, ISBN 9780486446172.
10. Доусон, Дж. В. (август 2006 г.), «Пошатнувшиеся основы или новаторская перестройка? Столетняя оценка влияния Курта Гёделя на логику, математику и информатику», Труды 21-го ежегодного симпозиума IEEE по логике в информатике (LICS 2006 г.) , стр. 339–341, doi :10.1109/LICS.2006.47, ISBN 978-0-7695-2631-7, S2CID  15526447, Аксиома выбора, хотя она и использовалась неосознанно во многих аргументах в анализе, стала спорной, как только была сделана явной, не только из-за ее неконструктивного характера, но и потому, что она подразумевала такие крайне неинтуитивные следствия, как парадокс Банаха-Тарского..
11. Баумелер, А., Дакич, Б. и Дель Санто, Ф., 2022. Аксиома выбора и принцип отсутствия сигналов, препринт arXiv — arXiv:2206.08467.
12. Пер Мартин-Лёф , Интуиционистская теория типов , 1980. Энн Шерп Троелстра , Метаматематическое исследование интуиционистской арифметики и анализа , Springer, 1973.
13. Мартин-Лёф, Пер (2006). «100 лет аксиоме выбора Цермело: в чём была проблема?». The Computer Journal . 49 (3): 345–350. Bibcode : 1980CompJ..23..262L. doi : 10.1093/comjnl/bxh162.
14. Эрретт Бишоп и Дуглас С. Бриджес, Конструктивный анализ , Springer-Verlag, 1985.
15. Фред Ричман, «Конструктивная математика без выбора», в: Reuniting the Antipodes—Constructive and Nonstandard Views of the Continuum (P. Schuster et al., eds), Synthèse Library 306, 199–205, Kluwer Academic Publishers, Амстердам, 2001.
16. Френкель 1922.
17. Мостовский 1938.
18. Гёдель, Курт (9 ноября 1938 г.). «Непротиворечивость аксиомы выбора и обобщенной континуум-гипотезы». Труды Национальной академии наук Соединенных Штатов Америки . 24 (12): 556–557. Bibcode : 1938PNAS...24..556G. doi : 10.1073 /pnas.24.12.556 . PMC 1077160. PMID  16577857. 
19. Коэн, Пол (2019). «Независимость аксиомы выбора» (PDF) . Библиотеки Стэнфордского университета . Архивировано (PDF) из оригинала 9 октября 2022 г. . Получено 22 марта 2019 г. .
20. Это происходит потому, что арифметические утверждения абсолютны по отношению к конструируемой вселенной L. Теорема абсолютности Шенфилда дает более общий результат.
21. См. Moore 2013, стр. 330–334, для структурированного списка из 74 эквивалентов. См. Howard & Rubin 1998, стр. 11–16, для 86 эквивалентов со ссылками на источники.
22. Бласс, Андреас (1984). «Существование баз подразумевает аксиому выбора». Аксиоматическая теория множеств (Боулдер, Колорадо, 1983) . Contemporary Mathematics. Т. 31. Провиденс, Род-Айленд: Американское математическое общество. С. 31–33. doi :10.1090/conm/031/763890. MR  0763890.
23. A. Hajnal , A. Kertész: Некоторые новые алгебраические эквиваленты аксиомы выбора, Publ. Math. Debrecen , 19 (1972), 339–340, см. также H. Rubin, J. Rubin , Equivalents of the axiom of choice, II , North-Holland , 1985, стр. 111.
24. Blass, Andreas (1979). «Инъективность, проективность и аксиома выбора». Труды Американского математического общества . 255 : 31–59. doi : 10.2307/1998165 . JSTOR  1998165.
25. Аводей, Стив (2010). Теория категорий (2-е изд.). Оксфорд: Oxford University Press. С. 20–24. ISBN 978-0199237180. OCLC  740446073.
26. проективный объект в n Lab
27. Серр, Жан-Пьер (2003), Деревья , Springer Monographs in Mathematics, Springer, стр. 23; Соукуп, Лайош (2008), «Бесконечная комбинаторика: от конечного к бесконечному», Горизонты комбинаторики , Математические исследования общества Бойяи, т. 17, Берлин: Springer, стр. 189–213, CiteSeerX 10.1.1.222.5699 , doi :10.1007/978-3-540-77200-2_10, ISBN  978-3-540-77199-9, г-н  2432534, См. в частности теорему 2.1, стр. 192–193.
28. Мугер, Майкл (2020). Топология для работающего математика .
29. Jech 2008, стр. 119–131, показывает, что аксиома счетного выбора подразумевает эквивалентность бесконечных и дедекиндово бесконечных множеств, но что эквивалентность бесконечных и дедекиндово бесконечных множеств не подразумевает аксиому счетного выбора в ZF.
30. Было показано Леви 1958 и другими с использованием моделей Мостовского, что восемь определений конечного множества независимы в ZF без AC, хотя они эквивалентны, когда AC предполагается. Определения: I-конечность, Ia-конечность, II-конечность, III-конечность, IV-конечность, V-конечность, VI-конечность и VII-конечность. I-конечность совпадает с нормальной конечностью. IV-конечность совпадает с конечностью по Дедекинду.
31. Сагеев, Гершон (март 1975 г.). «Независимый результат относительно аксиомы выбора». Annals of Mathematical Logic . 8 (1–2): 1–184. doi :10.1016/0003-4843(75)90002-9.
32. "[FOM] Являются ли (C,+) и (R,+) изоморфными". 21 февраля 2006 г.
33. Эш, CJ (1975). «Следствие аксиомы выбора». Журнал Австралийского математического общества . 19 (3): 306–308. doi : 10.1017/S1446788700031505 . S2CID  122334025.
34. Шехтер 1996, стр. 391–392.
35. «О принципе разбиения».
36. Аксиома зависимого выбора
37. «Новые основания Куайна». Стэнфордская энциклопедия философии . Получено 10 ноября 2017 г.
38. Jech 2008, стр. 142–144, Теорема 10.6 с доказательством.
39. Стави, Джонатан (1974). «Модель ZF с бесконечной свободной полной булевой алгеброй». Israel Journal of Mathematics . 20 (2): 149–163. doi :10.1007/BF02757883. S2CID  119543439.

Ссылки

• Френкель, Абрахам (1922), «Der Begriff «определенный» и умереть Unabhängigkeit des Auswahlaxioms», Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften : 253–257, JFM  48.0199.02
• Халмос, Пол Р. (1960). Наивная теория множеств . Университетская серия по математике для студентов. Принстон, Нью-Джерси: van Nostrand Company. Zbl  0087.04403.
• Херлих, Хорст (2006). Аксиома выбора . Конспект лекций по математике. 1876. Берлин: Springer-Verlag . ISBN 978-3-540-30989-5.
• Howard, Paul; Rubin, Jean E. (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. doi : 10.4064/fm-46-1-1-13 . Архивировано (PDF) из оригинала 9 октября 2022 г.
• Пер Мартин-Лёф, «100 лет аксиомы выбора Цермело: в чём была проблема?», в Logicism, Intuitionism, and Formalism: What Has Become of Them?, редакторы Стен Линдстрём, Эрик Пальмгрен, Кристер Сегерберг и Вигго Столтенберг-Хансен (2008). ISBN 1-4020-8925-2 
• Мендельсон, Эллиотт (1964). Введение в математическую логику . Нью-Йорк: Van Nostrand Reinhold.
• Мур, Грегори Х. (1982). Аксиома выбора Цермело, ее происхождение, развитие и влияние . Springer . ISBN 978-0-387-90670-6., доступно в виде переиздания Dover Publications , 2013, ISBN 0-486-48841-1 . 
• Мостовский, Анджей (1938), «Über den Begriff einer Endlichen Menge», Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Classe III , 31 (8): 13–20
• Мур, Грегори Х. (2013) [1982]. Аксиома выбора Цермело: ее происхождение, развитие и влияние . Минеола, Нью-Йорк: Dover Publications. ISBN 978-0-486-48841-7.
• Герман Рубин, Джин Э. Рубин : Эквиваленты аксиомы выбора. Северная Голландия, 1963. Переиздано Elsevier , апрель 1970. ISBN 0-7204-2225-6 . 
• Герман Рубин, Джин Э. Рубин: Эквиваленты аксиомы выбора II. North Holland/Elsevier, июль 1985 г., ISBN 0-444-87708-8 . 
• Рассел, Бертран (1993) [1919]. Введение в математическую философию . Нью-Йорк: Dover Publications. ISBN 978-0-486-27724-0.
• Шехтер, Эрик (1996). Справочник по анализу и его основам . Сан-Диего, Калифорния: Academic Press. ISBN 978-0-12-622760-4. OCLC  175294365.
• Suppes, Patrick (1972) [1960]. Аксиоматическая теория множеств . Mineola, New York: Dover. ISBN 978-0-486-61630-8.
• Джордж Турлакис, Лекции по логике и теории множеств. Том II: Теория множеств , Cambridge University Press , 2003. ISBN 0-511-06659-7 
• Цермело, Эрнст (1904). «Beweis, dass jede Menge wohlgeordnet werden kann» (перепечатка) . Математические Аннален . 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. Включает формальную формулировку аксиомы выбора, максимального принципа Хаусдорфа, леммы Цорна и формальные доказательства их эквивалентности вплоть до мельчайших деталей.
• Последствия аксиомы выбора. Архивировано 15 мая 2021 г. на Wayback Machine , основано на книге Пола Ховарда. Архивировано 26 февраля 2021 г. на Wayback Machine и Джин Рубин.
• «Аксиома выбора» — статья Джона Лейна Белла в Стэнфордской энциклопедии философии .