>>119834010. (AC) Декартово произведение семейства непустых множеств не пусто.
Эта аксиома называется аксиомой Цермело.
Пусть i - какое-нибудь множество. Мы говорим, что задано семейство множеств, если с каждым i из I связано одно вполне определённое множество Mi. Множество I называется множеством индексов. Оно может быть как конечным, так и бесконечным. Семейство обозначается как {Mi, i∈I}. Ещё оно может быть обозначено как M1, M2, ... , Mi, ... в случае, когда хочется подчеркнуть его возможную бесконечность.
Например, пусть I = {1, 2, 3, 4}. Тогда в семейство {Mi, i∈I} входят четыре множества: первое, второе, третье и четвертое.
Декартово произведение семейства M1, M2, ... , Mi, .... - это множество всевозможных кортежей вида <m1, m2, ... , mi, ... >, в которых i-я компонента является элементом i-го множества. Оно обозначается символом П{Mi, i∈I}. Если в семействе лишь конечное количество множеств, то его произведение обозначается проще: M1×M2×...×Mn.
Кортеж из двух элементов <p,q> называется упорядоченной парой p и q (в таком порядке). Если p и q различны, то <p,q> не равно <q,p>. Часто используют не угловые скобочки, а круглые: не <p,q>, а (p,q).
Например, декартово произведение двух множеств M1 = {яблоко, груша} и M2 = {огурец, томат, репа} состоит из шести упорядоченных пар:
M1×M2 = {
<яблоко, огурец>,
<яблоко, томат>,
<яблоко, репа>,
<груша, огурец>,
<груша, томат>,
<груша, репа> }.
Произведение трёх множеств M1 = {яблоко, груша}, M2 = {огурец, томат}, M3 = {бегемот, кашалот} состоит из восьми упорядоченных троек:
M1×M2×M3 = {
<яблоко, огурец, бегемот>,
<яблоко, огурец, кашалот>,
<яблоко, томат, бегемот>,
<яблоко, томат, кашалот>,
<груша, огурец, бегемот>,
<груша, огурец, кашалот>,
<груша, томат, бегемот>,
<груша, томат, кашалот>}.
Если перемножаемые множества суть одно и то же множество {0,1}, то декартово произведение n таких множеств является просто-напросто множеством битовых строк длины n. Например, {0,1}×{0,1}×{0,1}×{0,1} = {0000, 0001, 0010, 0011, 0100, 0101, ... }
Здесь упорядоченная четверка <0, 1, 0, 1> для простоты записывается как 0101 и т.п.
В теории ZFC всё является множеством. Каким множеством является кортеж?
Изначально Цермело считал упорядоченные двойки, тройки и т.д. элементарными понятиями и не хотел останавливаться на их определении. В 1921 году Казимир Куратовский предложил определять упорядоченную пару с помощью неупорядоченной: за <a,b> он принял множество {{a}, {a,b}}. Определение пары по Куратовскому оказалось простым и удобным. Пары <a,b> и <p,q> оказались равны тогда и только тогда, когда a=p и b=q, что и требовалось от упорядоченной пары. Тройки, четверки и т.д. определяются с помощью упорядоченных пар.
Иная ситуация с кортежами бесконечной длины. По определению, кортежем для {Mi, i∈I} называется отображение, определённое на множестве I, обладающее следующим качеством: образ элемента i является элементом множества Mi. Такие отображения называются функциями выбора на {Mi, i∈I}. Формально они принимают значения во множестве ∪Mi.
Например, пусть у нас есть бесконечное множество цветов, занумерованное натуральными числами: красный=0, зеленый=1, синий=2, ... , и для каждого номера дано множество вещей этого цвета. В такой ситуации кортежем будет функция натурального аргумента, которая каждому номеру (=натуральному числу) сопоставляет вещь, окрашенную в цвет указанного номера. Понятно, что если вещей каждого цвета дано хотя бы пять-десять штук, то различных функций выбора будет бесконечно много.
От термина "функция выбора" происходит название обсуждаемой аксиомы. Другое название аксиомы Цермело - "аксиома выбора", AC, axiom of choice.
Аксиома выбора приводит к нескольким неожиданным выводам. Так, оказывается, что любое множество может быть упорядочено полным порядком (любые два элемента сравнимы и в любом непустом подмножестве есть наименьший элемент). Этот факт известен как теорема Цермело; он логически эквивалентен аксиоме выбора. Другой известный факт, эквивалентный аксиоме выбора, - лемма Цорна, находящая множество применений в алгебре.
Из аксиомы выбора следует, что шар можно разбить на две части, имеющих тот же объём, что и сам шар (парадокс Банаха-Тарского). Кроме того, из неё следует существование на вещественной прямой множеств, неизмеримых по Лебегу (исторически первый пример - множество Витали). Эти следствия создавали столь много неудобств для теоретиков матанализа, что ими было основано движение против всякого использования аксиомы выбора. Им не удалось этого сделать: проблемы начались уже на этапе построения числовой прямой. Оказалось, что аксиома выбора использовалась при доказательстве несчётности множества всех вещественных чисел, и даже более того: в доказательстве утверждения, что в любом бесконечном множестве есть счётное подмножество (т.е. подмножество, элементы которого можно перенумеровать натуральными числами).
В самом деле, вот классическое доказательство последнего утверждения. Пусть M - бесконечное множество. Возьмём в нём какой-нибудь элемент a1. Выкинем его из множества M; во множестве останется бесконечно много элементов. Выберем из оставшихся элемент a2. Выкинем его из M, в M останется бесконечно много элементов, выберем a3 и т.д. Получится счетное множество a1, a2, a3, ...
Аксиома выбора используется здесь при каждом выборе какого-нибудь элемента из M. Дело в том, что все элементы произвольного M равноправны, и нет явного способа написать предикат, позволяющий объективно предпочесть один элемент всем другим элементам. А всякий раз, когда выбор совершается неявно, нужна аксиома выбора.
Расселл иллюстрировал эту ситуацию таким примером. Пусть есть бесконечное множество пар ботинок. Тогда в каждой паре мы можем выбрать левый ботинок - это даёт нам явное словесное описание функции выбора, "выбрать в каждой паре левый ботинок". Но пусть теперь нам дано бесконечное множество пар шнурков. Шнурки делаются одинаковыми, и явного способа предпочесть один шнурок другому не имеется. Поэтому остаётся лишь констатировать факт, что каким-нибудь образом выбор шнурка из каждой пары может быть сделан, и явно описать этот выбор словами уже нельзя.
Обнаружив невозможность изгнать аксиому выбора, борцы с ней пошли другим путём: решили заменить её какой-нибудь другой аксиомой, которая сохраняла бы все нужные свойства множеств и запрещала бы множества с плохими свойствами. Этот подход оказался более плодотворен.
Так, один из конкурентов аксиомы выбора - аксиома счетного выбора, ACω.
Она утверждает, что декартово произведение
счетного семейства непустых множеств не пусто, и ничего не говорит о ситуациях, когда I настолько бесконечно, что его нельзя перенумеровать натуральными числами. Эта аксиома покрывает большинство ситуаций, используемых в анализе. Но всё-таки не все: так, она не позволяет вывести теорему Бэра о категориях.
Более мощный инструмент - аксиома зависимого выбора (DC, axiom of dependent choice). Давайте вообразим ориентированный граф, из каждой вершины которого исходит стрелка. Тогда в этом графе есть хотя бы один путь счётной длины: A0→A1→A2→... Вершины в этом пути могут повторяться. В частности, если в вершине A есть петелька, то можно бесконечно нарезать круги A→A→A→... , поэтому обычно всё-таки требуют, чтобы петелек не было. Аксиома зависимого выбора несколько более наглядна, чем аксиома выбора, и для теоремы о категориях её достаточно. Можно доказать, что аксиома зависимого выбора следует из общей аксиомы выбора и влечёт аксиому счётного выбора: AC→DC→ACω.
Следование AC→DC очевидно: AC позволяет сделать выбор в каждом множестве исходящих стрелок и таким образом построить путь.
Следование DC→ACω также несложно. Пусть M0, M1, M2, ... - счетное семейство множеств, и пусть V - множество кортежей вида <m0>, <m0, m1>, <m0, m1, m2> и т.д. Здесь i-я компонента берётся из i-го множества. Примем V за множество вершин графа. Стрелку из кортежа <m0, m1, ... , mp> длины p в кортеж <n0, n1, ... , np, nq> длины q мы проведем, если и только если первые p элементов у этих кортежей совпадают. m0=n0, m1=n1, ... , mp=np, nq произвольно. Тогда применение DC к этому графу даст нам путь вида <m0> → <m0, m1> → <m0, m1, m2> → ... В этом пути последний элемент кортежа номер i даёт нам выбор элемента из i-го множества, и таким образом мы получаем функцию выбора на всех Mi.
Ещё одна из аксиом, которые здесь нужно упомянуть, - аксиома о булевом простом идеале (BPI, Boolean prime ideal theorem). Формулировке этой аксиомы нужно предпослать несколько понятий из общей алгебры.
Множество с частичным порядком называется решёткой, если для любых двух элементов a и b определены точная верхняя и точная нижняя грань, обозначаемые соответственно a∧b и a∨b. Дистрибутивная решётка - в которой (a∨b)∧c=(a∨c)∧(b∨c) (закон де Моргана). Ограниченная решётка - в которой есть наибольший элемент 1 и наименьший элемент 0. Комплементированная решётка - ограниченная, в которой для любого a есть такой "двойственный элемент" b, что a∨b = 1 и a∧b = 0. Решётки обычно изображаются диаграммами Хассе.
Комплементированная дистрибутивная решётка называется булевой.
Самая простая булева алгебра содержит два элемента 0 и 1 и три таблицы истинности - ИЛИ, И, НЕ. ∨ толкуется как "или", ∧ как "и". Элемент, двойственный к a, определяется как НЕ-a.
Булеву решётку можно считать коммутативным кольцом с единицей, в котором сложение - это ∨, умножение - это ∧. Идеалом в кольце называется множество, замкнутое по сложению и выдерживающее умножение на всевозможные элементы кольца. Идеал называется простым, если он не равен всему кольцу, а также обладает свойством простоты: если произведение ab лежит в идеале, то хотя бы один из элементов a, b лежит в идеале.
Аксиома BPI утверждает, что в булевой алгебре всегда есть простой идеал.
BPI следует из AC, но она слабее: можно доказать, что AC нельзя вывести из BPI. Из BPI следуют теорема Хана-Банаха, теорема Стоуна-Чеха о компактификации, теорема Тихонова для произведения хаусдорфовых компактов, теорема о существовании алгебраического замыкания для любого поля и многие другие теоремы. Также BPI даёт возможность упорядочить любое множество линейным порядком (а не гарантированно полным) и доказать, что декартово произведение непустых
конечных множеств непусто. Из BPI не следуют ни DC, ни ACω. Есть модели ZF, в которых BPI и DC выполнено, а AC - нет.
AC можно переформулировать в терминах теории графов.
Скелет графа - его связный подграф, содержащий все вершины и не содержащий циклов. Скелет часто называют остовным деревом или остовом.
AC = у каждого связного графа есть скелет.
Некоторые другие утверждения, эквивалентные AC:
- теорема Цермело о вполне упорядочивании
- лемма Цорна
- принцип максимума Хаусдорфа
- в любом чуме есть максимальная антицепь
- между A и A×A есть биекция, если A бесконечно
- каждая сюръекция имеет сечение
- Крулль: нетривиальное кольцо с единицей имеет максимальный идеал
- Тихонов: произведение семейства компактных пространств компактно
- непустое множество можно наделить структурой группы
- у любого векторного пространства есть базис
В целом, в анализе не удалось заменить аксиому выбора никакой другой аксиомой. Анализ на основе DC выглядит самым перспективным, но без теоремы Тихонова и теоремы Хана-Банаха современный анализ всё-таки неполноценен. Ну а сочетание DC+BPI уже слишком мало отличается от AC, чтобы были основания урезать общность.
Иная ситуация в науке, которая называется дескриптивная теория множеств. В ней аксиома выбора с большим успехом была заменена так называемой аксиомой детерминированности, которую ввели в 1962 году Ян Мычельский и Гуго Штейнгауз.
Рассмотрим следующую игру. Пусть A - множество счетных последовательностей натуральных чисел. Играют два игрока. Первый пишет число a1, второй a2, первый a3, второй a4, ...
Так продолжается бесконечно. У них получается строка r. Первый игрок выигрывает, если r является элементом A, иначе выигрывает второй игрок.
Аксиома детерминированности (AD): у одного из двух игроков есть выигрышная стратегия.
Более формально это всё звучит так. Как и раньше, Пусть A - множество счетных последовательностей натуральных чисел. Уточним понятие стратегии. Рассмотрим множество конечных строк натуральных чисел. Разобьём его на два множества - E и O, множества строк соответственно четной и нечётной длины (пустая строка считается строкой четной длины). Функции со значениями во множестве натуральных чисел, определённые на E, называются стратегиями первого игрока; со значениями на O - второго игрока. Т.е. стратегия говорит игроку, какое число нужно дописывать. Пусть дана последовательность натуральных чисел. Она называется согласованной со стратегией S1 первого игрока, если любая её начальная подпоследовательность нечетной длины имеет вид "строка четной длины, дополненная значением S1 от этой строки"; согласованной со стратегией S2 второго игрока, если любая её начальная подпоследовательность ненулевой четной длины имеет вид "строка нечетной длины, дополненная значением S2 от этой строки". Стратегия S1 первого игрока называется выигрышной, если есть согласованная с ней последовательность, лежащая в A. Стратегия S2 второго игрока называется выигрышной, если есть согласованная с ней последовательность, не лежащая в A.Из AD вытекает ACω. Еще из AD следует, что любое множество вещественных чисел измеримо по Лебегу, имеет свойство Бэра и либо счетно, либо континуально, таким образом AD прямо противоречит AC. По настоящее время AD остаётся плохо изученной аксиомой.
Итак, канон ZFC:
1. Экстенсиональность.
2. Неупорядоченная пара.
3. Объединение.
4. Булеан.
5. Схема выделения.
6. Схема подстановки (1922).
7. Пустое множество.
8. Бесконечность.
9. Регулярность (1930).
10. AC.
Канон начался с публикации Цермело 1908 года. Аксиомы 2 и 7 изначально объединялись в одну аксиому, так называемую аксиому элементарных множеств: "Cуществует пустое множество; для любой вещи a существует множество {a}; для любых двух вещей a и b существует множество {a,b}". Аксиома бесконечности давалась в виде: "Существует хотя бы одно множество, содержащее пустое множество и с каждым элементом a содержащее множество {a}". Аксиома выбора давалась в виде: "Если множество T состоит из непустых попарно непересекающихся множеств, то его объединение ∪T имеет хотя бы одно подмножество, пересекающихся с каждым из множеств из T в точности по одному элементу". В формулировке аксиом подстановки использовался термин "высказывательная функция", который позднее был уточнен с помощью исследования так называемых теорий первого порядка. Эта версия канона известна как теория Z. Z не запрещала существование урэлементов, но и не постулировала их существование.
В 1922 году Френкель и Сколем доказали, что аксиом Z недостаточно, чтобы утверждать, что {N0, N1, N2, ... } является множеством (N0 - натуральные числа, N^(n+1) = 2^N). Эту совокупность, однако, следует считать множеством, если имеется желание построить теорию ординалов, согласованную с канторовской теорией порядковых чисел. Таким образом, Цермело был вынужден принять в канон схему подстановки. Эта аксиома резко увеличила допустимые размеры бесконечностей. В 1925 году фон Нейман построил красивую теорию кумулятивной иерархии, опираясь на введённую им аксиому фундирования. Несколько лет спустя Цермело, весьма увлеченный кумулятивной иерархией, добавил в канон регулярность. Это введение одобрили не все теоретики; так, Куратовский предпочитал не пользоваться этой аксиомой в своих учебниках, а Френкель слишком любил урэлементы, которые аксиома выкидывала. Аксиома регулярности независима от остальных аксиом ZF (и даже ZFC) и не противоречит им.
--
В следующих постах: языки и модели; NBG и MK; теория ординалов и кардиналов; L, континуум-гипотеза и бриллиантик Йенсена; MA, PFA, и другие аксиомы форсинга; большие кардиналы; логика в топосах, ETCS и ETCC; (∞,n).