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

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

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

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

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

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

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

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

Заявление

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

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

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

$\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]\,.$

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

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

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

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

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

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

Варианты

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

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

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

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

∀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 , тогда как согласно определению, используемому в других местах этой статьи, областью определения функции выбора для набора множеств является набор, и это имеет смысл только для наборов наборов. Используя это альтернативное понятие функции выбора, аксиому выбора можно компактно сформулировать как

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

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

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

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

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

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

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

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

До конца XIX века аксиома выбора часто использовалась неявно, хотя формально она еще не была сформулирована. Например, установив, что множество 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 несчетно. Следовательно, распадается на бесчисленное множество орбит под действием G. S Используя аксиому выбора, мы могли бы выбрать одну точку на каждой орбите, получив несчетное подмножество X из S со свойством, что все его сдвиги на G не пересекаются с X . Набор этих трансляций разбивает круг на счетный набор непересекающихся множеств, которые все попарно конгруэнтны. Поскольку X не измеримо ни для какой счетно-аддитивной конечной меры на S , инвариантной к вращению , поиск алгоритма формирования множества путем выбора точки на каждой орбите требует добавления аксиомы выбора к нашим аксиомам теории множеств. см. в разделе «Неизмеримый набор» Более подробную информацию .

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

аксиомы

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

Эквиваленты

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

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

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

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

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

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

формы

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

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

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

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

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

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

последствия

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

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

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

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

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

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

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

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

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

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

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

выбора в

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

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

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

Цитаты

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

— Джерри Л. Бона

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

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

— Бертран Рассел

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

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

Польско-американский математик Ян Мыцельский рассказывает этот анекдот в статье 2006 года в «Извещениях AMS».

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

— АК Дьюдни

Эта цитата взята из знаменитой первоапрельской статьи в колонке «Компьютерные развлечения » журнала Scientific American за апрель 1989 года.

Ссылки

• Френкель, Абрахам (1922), «Термин «определенный» и независимость аксиомы отбора», труды Королевской прусской академии наук : 253–257, JFM   48.0199.02
• Халмос, Пол Р. (1960). Наивная теория множеств . Университетская серия по математике для студентов. Принстон, Нью-Джерси: компания van Nostand. Збл   0087.04403 .
• Херлих, Хорст (2006). Аксиома выбора . Конспекты лекций по математике 1876 г. Берлин: Springer-Verlag . ISBN  978-3-540-30989-5 .
• Ховард, Пол; Рубин, Жан Э. (1998). Следствия аксиомы выбора . Математические обзоры и монографии. Том. 59. Провиденс, Род-Айленд: Американское математическое общество . ISBN  9780821809778 .
• Джех, Томас (2008) [1973]. Аксиома выбора . Минеола, Нью-Йорк: Dover Publications . ISBN  978-0-486-46624-8 .
• Джех, Томас (1977). «Об аксиоме выбора». В Джоне Барвайзе (ред.). Справочник по математической логике .
• Леви, Азриэль (1958). «Независимость различных определений конечности» (PDF) . Фундамента Математика . 46 : 1–13. дои : 10.4064/fm-46-1-1-13 . Архивировано (PDF) из оригинала 9 октября 2022 года.
• Пер Мартин-Лёф, «100 лет выбора аксиомы Цермело: в чем была проблема?», в книге «Логицизм, интуиционизм и формализм: что с ними стало?» , Стен Линдстрем, Эрик Палмгрен, Кристер Сегерберг и Вигго Столтенберг-Хансен, редакторы (2008). ISBN   1-4020-8925-2
• Мендельсон, Эллиотт (1964). Введение в математическую логику . Нью-Йорк: Ван Ностранд Рейнхольд.
• Мур, Грегори Х. (1982). Аксиома выбора Цермело, ее истоки, развитие и влияние . Спрингер . ISBN  978-0-387-90670-6 . , доступно в виде переиздания Dover Publications , 2013 г., ISBN   0-486-48841-1 .
• Мостовский, Анджей (1938), «Über den Begriff einer Endlichen Menge», Протоколы заседаний Варшавского общества наук и литературы, класс III , 31 (8): 13–20
• Мур, Грегори Х (2013) [1982]. Аксиома выбора Цермело: ее истоки, развитие и влияние . Минеола, Нью-Йорк: Dover Publications. ISBN  978-0-486-48841-7 .
• Герман Рубин , Жан Э. Рубин : Эквиваленты аксиомы выбора. Северная Голландия, 1963 г. Переиздано Elsevier , апрель 1970 г. ISBN   0-7204-2225-6 .
• Герман Рубин, Жан Э. Рубин: Эквиваленты аксиомы выбора II. Северная Голландия/Эльзевир, июль 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 .
• Суппес, Патрик (1972) [1960]. Аксиоматическая теория множеств . Минеола, Нью-Йорк: Дувр. ISBN  978-0-486-61630-8 .
• Джордж Турлакис, Лекции по логике и теории множеств. Том. II: Теория множеств , Издательство Кембриджского университета , 2003. ISBN   0-511-06659-7
• Цермело, Эрнст (1904). «Доказательство того, что любое множество может быть упорядочено» (перепечатка) . Математические летописи . 59 (4): 514–16. дои : 10.1007/BF01445300 . S2CID   124189935 .
• Эрнст Цермело , «Исследования основ теории множеств I», Mathematical Annals 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 и Жана Рубина.
• «Аксиома выбора» Статья Джона Лейна Белла в Стэнфордской энциклопедии философии .