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

Введение

Аксиома теории множеств – математическая концепция.

В математике аксиома выбора, сокращенно AC или AoC, является аксиомой теории множеств, эквивалентной утверждению о том, что декартово произведение коллекции непустых множеств непусто. Неформально говоря, аксиома выбора утверждает, что для любой коллекции множеств, каждое из которых содержит по крайней мере один элемент, можно построить новое множество, выбирая по одному элементу из каждого множества, даже если коллекция бесконечна. Формально, она утверждает, что для каждого индексированного семейства непустых множеств существует индексированное множество, такое что для каждого элемента семейства существует элемент в соответствующем множестве. Аксиома выбора была сформулирована в 1904 году Эрнстом Зермело для формализации его доказательства теоремы о хорошем упорядочении. Во многих случаях множество, созданное путем выбора элементов, можно сформировать без использования аксиомы выбора, особенно если число множеств, из которых выбираются элементы, конечно, или если доступно каноническое правило выбора элементов – некоторое отличительное свойство, которое выполняется ровно для одного элемента в каждом множестве. Иллюстративным примером служат множества, взятые из натуральных чисел. Из таких множеств всегда можно выбрать наименьший элемент, например, для множеств {4, 5, 6}, {10, 12}, {1, 400, 617, 8000} множество, содержащее каждый наименьший элемент, будет равно {4, 10, 1}. В этом случае «выбрать наименьший элемент» является функцией выбора. Даже если собрана бесконечная коллекция множеств из натуральных чисел, всегда можно выбрать наименьший элемент из каждого множества, чтобы получить множество. То есть функция выбора предоставляет набор выбранных элементов. Однако для коллекции всех непустых подмножеств действительных чисел неизвестна никакая функция выбора. В этом случае необходимо использовать аксиому выбора. Бертран Расселл привел аналогию: для любой (даже бесконечной) коллекции пар обуви можно выбрать левый ботинок из каждой пары, чтобы получить соответствующую коллекцию (то есть множество) обуви; это позволяет непосредственно определить функцию выбора. Для бесконечной коллекции пар носков (предполагается, что они не имеют различительных признаков) нет очевидного способа создать функцию, формирующую множество, выбирая один носок из каждой пары без использования аксиомы выбора. Хотя изначально аксиома выбора была спорной, в настоящее время большинство математиков используют ее без оговорок, и она включена в стандартную форму аксиоматической теории множеств – теорию множеств Зермело-Френкеля с аксиомой выбора (ZFC). Одной из причин этого является то, что ряд общепринятых математических результатов, таких как теорема Тихонова, требуют аксиомы выбора для их доказательства. Современные теоретики множеств также изучают аксиомы, несовместимые с аксиомой выбора, например, аксиому определенности. Аксиома выбора избегается в некоторых вариантах конструктивной математики, хотя существуют варианты конструктивной математики, в которых она принимается.

In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non empty sets is non empty. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family of nonempty sets, there exists an indexed set such that for every The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well ordering theorem. In many cases, a set created by choosing elements can be made without invoking the axiom of choice, particularly if the number of sets from which to choose the elements is finite, or if a canonical rule on how to choose the elements is available — some distinguishing property that happens to hold for exactly one element in each set. An illustrative example is sets picked from the natural numbers. From such sets, one may always select the smallest number, e. g. given the sets 4, 5, 6}, {10, 12}, {1, 400, 617, 8000, the set containing each smallest element is {4, 10, 1}. In this case, "select the smallest number" is a choice function. Even if infinitely many sets are collected from the natural numbers, it will always be possible to choose the smallest element from each set to produce a set. That is, the choice function provides the set of chosen elements. But no definite choice function is known for the collection of all non empty subsets of the real numbers. In that case, the axiom of choice must be invoked. Bertrand Russell coined an analogy: for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate collection (i. e. set) of shoes; this makes it possible to define a choice function directly. For an infinite collection of pairs of socks (assumed to have no distinguishing features), there is no obvious way to make a function that forms a set out of selecting one sock from each pair without invoking the axiom of choice. Although originally controversial, the axiom of choice is now used without reservation by most mathematicians, and is included in the standard form of axiomatic set theory, Zermelo–Fraenkel set theory with the axiom of choice (ZFC). One motivation for this is that a number of generally accepted mathematical results, such as Tychonoff's theorem, require the axiom of choice for their proofs. Contemporary set theorists also study axioms that are not compatible with the axiom of choice, such as the axiom of determinacy. The axiom of choice is avoided in some varieties of constructive mathematics, although there are varieties of constructive mathematics in which the axiom of choice is embraced.

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

Обычная формулировка аксиомы выбора не уточняет, конечна или бесконечна коллекция непустых множеств, и, следовательно, подразумевает, что для каждой конечной коллекции непустых множеств существует функция выбора. Однако этот частный случай является теоремой теории множеств Цермело — Френкеля без аксиомы выбора (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 несчетна. Следовательно, S распадается на несчетное множество орбит относительно G. Используя аксиому выбора, мы можем выбрать одну точку с каждой орбиты, получив несчетное подмножество X из S с тем свойством, что все его трансляции относительно G не пересекаются с X. Множество этих трансляций разбивает окружность на счетное множество непересекающихся множеств, которые все попарно конгруэнтны. Поскольку X не измерима ни для одной ротационно инвариантной счетно-аддитивной конечной меры на S, поиск алгоритма для формирования множества путем выбора точки на каждой орбите требует добавления аксиомы выбора к нашим аксиомам теории множеств. Подробнее см. в статье о неизмеримых множествах. В классической арифметике натуральные числа хорошо упорядочены: для каждого непустого подмножества натуральных чисел существует единственный наименьший элемент в соответствии с естественным порядком. Таким образом, можно указать множество из любого заданного подмножества. Можно сказать: "Даже если обычный порядок действительных чисел не работает, возможно найти другой порядок действительных чисел, который будет являться отношением хорошего упорядочения. Тогда наша функция выбора может выбрать наименьший элемент каждого множества в нашем необычном порядке". Затем проблема сводится к построению хорошего упорядочения, для существования которого требуется аксиома выбора; каждый набор может быть хорошо упорядочен тогда и только тогда, когда аксиома выбора верна.

The nature of the individual nonempty sets in the collection may make it possible to avoid the axiom of choice even for certain infinite collections. For example, suppose that each member of the collection X is a nonempty subset of the natural numbers. Every such subset has a smallest element, so to specify our choice function we can simply say that it maps each set to the least element of that set. This gives us a definite choice of an element from each set, and makes it unnecessary to add the axiom of choice to our axioms of set theory. The difficulty appears when there is no natural choice of elements from each set. If we cannot make explicit choices, how do we know that our selection forms a legitimate set (as defined by the other ZF axioms of set theory)? For example, suppose that X is the set of all non empty subsets of the real numbers. First we might try to proceed as if X were finite. If we try to choose an element from each set, then, because X is infinite, our choice procedure will never come to an end, and consequently we shall never be able to produce a choice function for all of X. Next we might try specifying the least element from each set. But some subsets of the real numbers do not have least elements. For example, the open interval (0,1) does not have a least element: if x is in (0,1), then so is x/2, and x/2 is always strictly smaller than x. So this attempt also fails. Additionally, consider for instance the unit circle S, and the action on S by a group G consisting of all rational rotations, that is, rotations by angles which are rational multiples of π. Here G is countable while S is uncountable. Hence S breaks up into uncountably many orbits under G. Using the axiom of choice, we could pick a single point from each orbit, obtaining an uncountable subset X of S with the property that all of its translates by G are disjoint from X. The set of those translates partitions the circle into a countable collection of disjoint sets, which are all pairwise congruent. Since X is not measurable for any rotation invariant countably additive finite measure on S, finding an algorithm to form a set from selecting a point in each orbit requires that one add the axiom of choice to our axioms of set theory. See non measurable set for more details. In classical arithmetic, the natural numbers are well ordered: for every nonempty subset of the natural numbers, there is a unique least element under the natural ordering. In this way, one may specify a set from any given subset. One might say, "Even though the usual ordering of the real numbers does not work, it may be possible to find a different ordering of the real numbers which is a well ordering. Then our choice function can choose the least element of every set under our unusual ordering." The problem then becomes that of constructing a well ordering, which turns out to require the axiom of choice for its existence; every set can be well ordered if and only if the axiom of choice holds.

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

Доказательство, требующее аксиомы выбора, может установить существование объекта, не определяя его явно на языке теории множеств. Например, хотя аксиома выбора подразумевает существование хорошего упорядочения вещественных чисел, существуют модели теории множеств с аксиомой выбора, в которых никакое индивидуальное хорошее упорядочение вещественных чисел не определимо. Аналогично, хотя существование подмножества вещественных чисел, не измеримого по Лебегу, может быть доказано с использованием аксиомы выбора, непротиворечиво, что ни одно такое множество не определимо. Аксиома выбора доказывает существование этих неосязаемых объектов (объектов, существование которых доказано, но которые не могут быть явно построены), что может противоречить некоторым философским принципам. Поскольку не существует канонического упорядочения всех множеств, построение, опирающееся на упорядочение, может не дать канонического результата, даже если желателен канонический результат (как часто бывает в теории категорий). Это используется как аргумент против использования аксиомы выбора. Другой аргумент против аксиомы выбора заключается в том, что она подразумевает существование объектов, которые могут показаться контринтуитивными. Одним из примеров является парадокс Банаха — Тарского, утверждающий, что можно разложить трехмерный единичный шар на конечное число частей и, используя только вращения и сдвиги, собрать эти части в два шара, каждый из которых имеет тот же объем, что и исходный. Части в этом разложении, построенные с использованием аксиомы выбора, являются неизмеримыми множествами. Более того, недавно были отмечены парадоксальные следствия аксиомы выбора для принципа отсутствия передачи сигналов в физике. Несмотря на эти кажущиеся парадоксальными результаты, большинство математиков принимают аксиому выбора как допустимый принцип для доказательства новых результатов в математике. Однако дискуссия достаточно интересна, чтобы считаться значимой, когда теорема в ZFC (ZF плюс AC) логически эквивалентна (при использовании только аксиом ZF) аксиоме выбора, и математики ищут результаты, требующие ложности аксиомы выбора, хотя такой тип дедукции встречается реже, чем тип, требующий истинности аксиомы выбора. Теоремы ZF верны в любой модели этой теории, независимо от истинности или ложности аксиомы выбора в данной конкретной модели. Следствия аксиомы выбора, включая более слабые версии самой аксиомы, перечислены ниже, поскольку они не являются теоремами ZF. Например, парадокс Банаха — Тарского не доказуем и не опровержим только из ZF: невозможно построить требуемое разложение единичного шара в ZF, но также невозможно доказать отсутствие такого разложения. Такие утверждения можно перефразировать как условные утверждения, например: «Если AC истинна, то разложение в парадоксе Банаха — Тарского существует». Такие условные утверждения доказуемы в ZF, если исходные утверждения доказуемы из ZF и аксиомы выбора.

A proof requiring the axiom of choice may establish the existence of an object without explicitly defining the object in the language of set theory. For example, while the axiom of choice implies that there is a well ordering of the real numbers, there are models of set theory with the axiom of choice in which no individual well ordering of the reals is definable. Similarly, although a subset of the real numbers that is not Lebesgue measurable can be proved to exist using the axiom of choice, it is consistent that no such set is definable. The axiom of choice proves the existence of these intangibles (objects that are proved to exist, but which cannot be explicitly constructed), which may conflict with some philosophical principles. Because there is no canonical well ordering of all sets, a construction that relies on a well ordering may not produce a canonical result, even if a canonical result is desired (as is often the case in category theory). This has been used as an argument against the use of the axiom of choice. Another argument against the axiom of choice is that it implies the existence of objects that may seem counterintuitive. One example is the Banach–Tarski paradox, which says that it is possible to decompose the 3 dimensional solid unit ball into finitely many pieces and, using only rotations and translations, reassemble the pieces into two solid balls each with the same volume as the original. The pieces in this decomposition, constructed using the axiom of choice, are non measurable sets. Moreover, paradoxical consequences of the axiom of choice for the no signaling principle in physics have recently been pointed out. Despite these seemingly paradoxical results, most mathematicians accept the axiom of choice as a valid principle for proving new results in mathematics. But the debate is interesting enough that it is considered notable when a theorem in ZFC (ZF plus AC) is logically equivalent (with just the ZF axioms) to the axiom of choice, and mathematicians look for results that require the axiom of choice to be false, though this type of deduction is less common than the type that requires the axiom of choice to be true. Theorems of ZF hold true in any model of that theory, regardless of the truth or falsity of the axiom of choice in that particular model. The implications of choice below, including weaker versions of the axiom itself, are listed because they are not theorems of ZF. The Banach–Tarski paradox, for example, is neither provable nor disprovable from ZF alone: it is impossible to construct the required decomposition of the unit ball in ZF, but also impossible to prove there is no such decomposition. Such statements can be rephrased as conditional statements—for example, "If AC holds, then the decomposition in the Banach–Tarski paradox exists." Such conditional statements are provable in ZF when the original statements are provable from ZF and the axiom of choice.

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

Как обсуждалось выше, в классической теории ZFC аксиома выбора допускает неконструктивные доказательства, в которых существование некоторого типа объекта доказывается без построения конкретного экземпляра. Фактически, в теории множеств и теории топосов теорема Диаконеску показывает, что аксиома выбора влечет за собой закон исключённого третьего. Таким образом, этот принцип недоступен в конструктивной теории множеств, где используется неклассическая логика. Ситуация иная, когда принцип формулируется в теории типов Мартина Лёфа. Там и в арифметике Хейтинга высшего порядка соответствующее утверждение аксиомы выбора (в зависимости от подхода) включается в качестве аксиомы или доказывается как теорема. Причина этого различия заключается в том, что аксиома выбора в теории типов не обладает свойствами экстенсиональности, которыми обладает аксиома выбора в конструктивной теории множеств. Контекст теории типов обсуждается подробнее ниже. Различные принципы выбора были тщательно изучены в конструктивных контекстах, и их статус варьируется между разными школами и направлениями конструктивной математики. Некоторые результаты в конструктивной теории множеств используют аксиому счётного выбора или аксиому зависимого выбора, которые не влекут за собой закон исключённого третьего. Эрретт Бишоп, известный разработкой основы для конструктивного анализа, утверждал, что аксиома выбора конструктивно допустима, говоря:

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

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

В 1938 году Курт Гёдель показал, что отрицание аксиомы выбора не является теоремой ZF, построив внутреннюю модель (конструктивную вселенную), удовлетворяющую ZFC, тем самым доказав, что ZFC является непротиворечивой, если ZF непротиворечива сама по себе. В 1963 году Пол Коэн использовал технику принуждения, разработанную специально для этой цели, чтобы показать, что, при условии непротиворечивости ZF, аксиома выбора сама по себе не является теоремой ZF. Он сделал это, построив гораздо более сложную модель, удовлетворяющую ZF¬C (ZF с добавленной аксиомой отрицания AC), и тем самым доказав непротиворечивость ZF¬C. Вместе эти результаты устанавливают логическую независимость аксиомы выбора от ZF. Предположение о непротиворечивости ZF безобидно, поскольку добавление еще одной аксиомы к уже противоречивой системе не может ухудшить ситуацию. В силу этой независимости, решение об использовании аксиомы выбора (или её отрицания) в доказательстве нельзя принимать, опираясь на другие аксиомы теории множеств. Оно должно быть основано на других соображениях. Один из аргументов в пользу использования аксиомы выбора заключается в её удобстве, поскольку она позволяет доказывать некоторые упрощающие утверждения, которые иначе были бы недоказуемы. Многие теоремы, доказуемые с использованием аксиомы выбора, обладают элегантным общим характером: кардинальности любых двух множеств сопоставимы, каждое нетривиальное кольцо с единицей имеет максимальный идеал, каждое векторное пространство имеет базис, каждый связный граф имеет остовное дерево, и каждое произведение компактных пространств компактно, среди прочих. Часто аксиома выбора позволяет обобщить теорему на "более широкие" объекты. Например, без аксиомы выбора можно доказать, что каждое векторное пространство конечной размерности имеет базис, но обобщение на все векторные пространства требует аксиомы выбора. Аналогично, компактность конечного произведения компактных пространств можно доказать без аксиомы выбора, но обобщение на бесконечные произведения (теорема Тихонова) требует аксиомы выбора. Доказательство независимости также показывает, что широкий класс математических утверждений, включая все утверждения, которые можно сформулировать на языке арифметики Пеано, доказуемы в ZF тогда и только тогда, когда они доказуемы в ZFC. К этому классу относятся утверждение о том, что P = NP, гипотеза Римана и многие другие нерешенные математические проблемы. При попытке решить задачи этого класса не имеет значения, используется ZF или ZFC, если вопрос заключается только в существовании доказательства. Однако возможно, что для ZFC существует более короткое доказательство теоремы, чем для ZF. Аксиома выбора – не единственное значимое утверждение, независимое от ZF. Например, обобщенная гипотеза континуума (GCH) не только независима от ZF, но и независима от ZFC. Однако ZF вместе с GCH влечет за собой AC, что делает GCH строго более сильным утверждением, чем AC, хотя оба они независимы от ZF.

In 1938, Kurt Gödel showed that the negation of the axiom of choice is not a theorem of ZF by constructing an inner model (the constructible universe) that satisfies ZFC, thus showing that ZFC is consistent if ZF itself is consistent. In 1963, Paul Cohen employed the technique of forcing, developed for this purpose, to show that, assuming ZF is consistent, the axiom of choice itself is not a theorem of ZF. He did this by constructing a much more complex model that satisfies ZF¬C (ZF with the negation of AC added as axiom) and thus showing that ZF¬C is consistent. Together these results establish that the axiom of choice is logically independent of ZF. The assumption that ZF is consistent is harmless because adding another axiom to an already inconsistent system cannot make the situation worse. Because of independence, the decision whether to use the axiom of choice (or its negation) in a proof cannot be made by appeal to other axioms of set theory. It must be made on other grounds. One argument in favor of using the axiom of choice is that it is convenient because it allows one to prove some simplifying propositions that otherwise could not be proved. Many theorems provable using choice are of an elegant general character: the cardinalities of any two sets are comparable, every nontrivial ring with unity has a maximal ideal, every vector space has a basis, every connected graph has a spanning tree, and every product of compact spaces is compact, among many others. Frequently, the axiom of choice allows generalizing a theorem to "larger" objects. For example, it is provable without the axiom of choice that every vector space of finite dimension has a basis, but the generalization to all vector spaces requires the axiom of choice. Likewise, a finite product of compact spaces can be proven to be compact without the axiom of choice, but the generalization to infinite products (Tychonoff's theorem) requires the axiom of choice. The proof of the independence result also shows that a wide class of mathematical statements, including all statements that can be phrased in the language of Peano arithmetic, are provable in ZF if and only if they are provable in ZFC. Statements in this class include the statement that P = NP, the Riemann hypothesis, and many other unsolved mathematical problems. When attempting to solve problems in this class, it makes no difference whether ZF or ZFC is employed if the only question is the existence of a proof. It is possible, however, that there is a shorter proof of a theorem from ZFC than from ZF. The axiom of choice is not the only significant statement that is independent of ZF. For example, the generalized continuum hypothesis (GCH) is not only independent of ZF, but also independent of ZFC. However, ZF plus GCH implies AC, making GCH a strictly stronger claim than AC, even though they are both independent of ZF.

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

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

Слабые формы

Существует несколько более слабых утверждений, которые не эквивалентны аксиоме выбора, но тесно с ней связаны. Одним из примеров является аксиома зависимого выбора (DC). Еще более слабым примером является аксиома выбора для счетных множеств (ACω или CC), которая утверждает, что функция выбора существует для любого счетного множества непустых множеств. Эти аксиомы достаточны для многих доказательств в элементарном математическом анализе и согласуются с некоторыми принципами, такими как лебегова измеримость всех множеств действительных чисел, которые опровергаются полной аксиомой выбора. Для порядкового параметра α ≥ ω+2, любое множество S с рангом меньше α хорошо упорядочимо. Для порядкового параметра α ≥ 1, любое множество S с числом Хартогоса меньше ωα хорошо упорядочимо. По мере увеличения порядкового параметра, эти утверждения все более и более приближаются к полной аксиоме выбора. Другие аксиомы выбора, более слабые, чем аксиома выбора, включают теорему Буля о простых идеалах и аксиому униформизации. Первая эквивалентна в ZF лемме Тарского об ультрафильтрах 1930 года: каждый фильтр является подмножеством некоторого ультрафильтра.

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

Если обозначить через BP утверждение о том, что любое множество действительных чисел обладает свойством Бэра, то BP сильнее, чем ¬AC, которое утверждает несуществование функции выбора, возможно, даже только для одного множества непустых множеств. Усиленные отрицания могут быть совместимы с ослабленными формами АС. Например, ZF + DC + BP непротиворечивы, если непротиворечива ZF. Также непротиворечиво с ZF + DC, что любое множество действительных чисел измеримо по Лебегу, однако этот результат непротиворечивости, полученный Робертом М. Соловаем, нельзя доказать в самой ZFC, а требуется умеренное предположение о больших кардиналах (существование недоступного кардинала). Гораздо более сильная аксиома детерминированности, или АД, влечет за собой, что любое множество действительных чисел измеримо по Лебегу, обладает свойством Бэра и обладает свойством совершенного множества (все три этих утверждения опровергаются самой АС). ZF + DC + AD непротиворечивы при условии, что непротиворечива достаточно сильная аксиома о больших кардиналах (существование бесконечного числа кардиналов Вудина). Система аксиоматической теории множеств Куйна, New Foundations (NF), получила свое название от названия ("Новые основания математической логики") статьи 1937 года, в которой она была представлена. В аксиоматической системе NF аксиому выбора можно опровергнуть.

Заявления, соответствующие отрицанию АС

Существуют модели теории множеств Зермело — Френкеля, в которых аксиома выбора ложна. Мы будем обозначать «теорию множеств Зермело — Френкеля вместе с отрицанием аксиомы выбора» как ZF¬C. Для некоторых моделей ZF¬C возможно подтвердить отрицание некоторых стандартных теорем ZFC. Поскольку любая модель ZF¬C также является моделью ZF, то для каждого из следующих утверждений существует модель ZF, в которой это утверждение истинно. Существует множество, которое можно разбить на строго больше классов эквивалентности, чем элементов в исходном множестве, и функция, область определения которой строго меньше области значений. Фактически, это справедливо во всех известных моделях. Существует функция f из действительных чисел в действительные числа, такая что f не является непрерывной в точке a, но f последовательно непрерывна в точке a, то есть для любой последовательности {xₙ}, сходящейся к a, limₙ f(xₙ) = f(a). Существует бесконечное множество действительных чисел, не содержащее счетного бесконечного подмножества. Действительные числа являются счетным объединением счетных множеств. Это не подразумевает, что действительные числа счетны: как отмечалось выше, чтобы показать, что счетное объединение счетных множеств само является счетным, требуется аксиома счетного выбора. Существует поле без алгебраического замыкания. Во всех моделях ZF¬C существует векторное пространство без базиса. Существует векторное пространство с двумя базисами различной кардинальности. Существует свободная полная булева алгебра на счетном множестве образующих. Существует множество, которое нельзя линейно упорядочить. Существует модель ZF¬C, в которой каждое множество в Rⁿ измеримо. Таким образом, можно исключить контринтуитивные результаты, такие как парадокс Банаха — Тарского, которые доказуемы в ZFC. Более того, это возможно при условии принятия аксиомы зависимого выбора, которая слабее AC, но достаточна для развития большей части математического анализа. Во всех моделях ZF¬C обобщенная гипотеза континуума не выполняется. Для доказательств см. [указание на источник]. Кроме того, накладывая условия определимости на множества (в смысле описательной теории множеств), часто можно доказать ограниченные версии аксиомы выбора из аксиом, несовместимых с аксиомой выбора в общем виде. Это проявляется, например, в кодирующей лемме Мошковиса.

There are models of Zermelo Fraenkel set theory in which the axiom of choice is false. We shall abbreviate "Zermelo Fraenkel set theory plus the negation of the axiom of choice" by ZF¬C. For certain models of ZF¬C, it is possible to validate the negation of some standard ZFC theorems. As any model of ZF¬C is also a model of ZF, it is the case that for each of the following statements, there exists a model of ZF in which that statement is true. There is a set that can be partitioned into strictly more equivalence classes than the original set has elements, and a function whose domain is strictly smaller than its range. In fact, this is the case in all known models. There is a function f from the real numbers to the real numbers such that f is not continuous at a, but f is sequentially continuous at a, i. e., for any sequence {xn} converging to a, limn f(xn)=f(a). There is an infinite set of real numbers without a countably infinite subset. The real numbers are a countable union of countable sets. This does not imply that the real numbers are countable: As pointed out above, to show that a countable union of countable sets is itself countable requires the Axiom of countable choice. There is a field with no algebraic closure. In all models of ZF¬C there is a vector space with no basis. There is a vector space with two bases of different cardinalities. There is a free complete Boolean algebra on countably many generators. There is a set that cannot be linearly ordered. There exists a model of ZF¬C in which every set in Rn is measurable. Thus it is possible to exclude counterintuitive results like the Banach–Tarski paradox which are provable in ZFC. Furthermore, this is possible whilst assuming the Axiom of dependent choice, which is weaker than AC but sufficient to develop most of real analysis. In all models of ZF¬C, the generalized continuum hypothesis does not hold. For proofs, see
Additionally, by imposing definability conditions on sets (in the sense of descriptive set theory) one can often prove restricted versions of the axiom of choice from axioms incompatible with general choice. This appears, for example, in the Moschovakis coding lemma.

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

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

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

Цитаты

Аксиома выбора очевидно истинна, принцип хорошего упорядочения очевидно ложен, а что можно сказать о лемме Зорна? | Джерри Л. Бона

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

Суть наблюдения заключается в том, что можно определить функцию для выбора элемента из бесконечного множества пар обуви, например, выбирая левый ботинок из каждой пары. Без аксиомы выбора нельзя утверждать, что такая функция существует для пар носков, поскольку левый и правый носки (предположительно) неразличимы. Тарский попытался опубликовать свою теорему [эквивалентность между АС и утверждением, что "каждое бесконечное множество A имеет ту же мощность, что и A × A", см. выше] в Comptes Rendus, но Фреше и Лебег отказались её представлять. Фреше написал, что следствие из двух хорошо известных [истинных] утверждений не является новым результатом, а Лебег написал, что следствие из двух ложных утверждений не представляет интереса. Польско-американский математик Ян Мицельский рассказывает об этом анекдоте в статье 2006 года в Notices of the AMS. Аксиома получила своё название не потому, что математики предпочитают её другим аксиомам. | А. К. Дьюдни

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