top-book

3. Кардиналы и теорема Кантора

жеств") и множеств ("множеств небольшой мощности, которыми можно оперировать в соответствии с наивным представлением о множествах"). Эта система аксиом была упрощена и улучшена Паулем Бернайсом (Paul Bernays) в конце 1930-х, и Гёделем в 1940-м. Она эквивалентна системе аксиом Цермело-Френкеля.

Для большинства разделов современной математики основанием является не теория множеств, а теория категорий (о теории категорий см. лекцию 14 и дальше). Строгое построение теории категорий обыкновенно осуществляется на основе аксиоматики фон Ноймана-Бернайса-Гёделя (NBG).

Аксиоматика NBG и описание ее применений хорошо излагаются в англоязычной Википедии; там же можно прочитать биографию фон Ноймана с подробным очерком его работ по логике.

Прекрасный учебник (а по совместительству и задачник) наивной теории множеств первая часть книги Н. К. Верещагина и А. Шеня "Лекции по математической логике и теории алгоритмов," доступная на сайте Независимого Университета: http://www.mccme.ru/free-books/

Доказательство Коэна недоказуемости континуум-гипотезы можно найти в книжке "Теория множеств и континуум-гипотеза", П. Дж. Коэн.

Часть I. Основания математики

Аксиома выбора и ее приложения

4.1. Сечение отображения

Пусть ' : A ! B сюръективное отображение множеств. Сечением отображения ' называется отображение : B ! A, такое, что ' =

IdB.

ψ

A

φ

B

Сечение сюръективного отображения

Аксиома выбора утверждает, что каждое сюръективное отображение имеет сечение.

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

Один из подходов к обоснованию математики называется формализмом, и принадлежит он Давиду Гильберту. В начале XX-го века математика оказалась в кризисе, сотрясаемая парадоксами, которые следовали из “наивной теории множеств”, придуманной Георгом Кантором. Стало ясно, что обращение с произвольно взятыми бесконечными множествами опасно и приводит к противоречиям. В надежде избежать парадоксов, математики (Фреге, Гильберт, Цермело, Рассел и Уайтхед) стали строить

4. Аксиома выбора и ее приложения

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

Система аксиом, предложенная Фреге, оказалось противоречивой, основания математики по версии Рассела-Уайтхеда слишком сложными, и к настоящему времени канонической стала система аксиом, предложенная в 1908-м году Эрнстом Цермело, и улучшенная в 1922 Адольфом Френкелем и (независимо от него) Торальфом Сколемом (Adolf Fraenkel, Thoralf Skolem). В учебниках встречается немало версий системы Цермело-Френкеля, но все они эквивалентны.

Ernst Friedrich Ferdinand Zermelo

(1871 1953)

Цермело провел 3 года (1905-1908), пытаясь доказать, что его система аксиом непротиворечива (не приводит к противоречию). Вплоть до 1930-х годов, Гильберт с коллегами были уверены, что в скором вре-

Часть I. Основания математики

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

В 1931-м году Курт Гёдель доказал, что непротиворечивость системы аксиом Цермело-Френкеля недоказуема. Если точно, Гёдель доказал, что невозможно доказать непротиворечивость любой системы аксиом в математическом языке, достаточно сильном, чтобы сформулировать на нем утверждения арифметики, если из этой системы аксиом следуют аксиомы Пеано (существование натуральных чисел и принцип индукции). Еще точнее Гёдель доказал невозможность доказательства средствами, допускающими формализацию в рамках того же самого математического языка.

Отмечу, что опровергнуть непротиворечивость такой системы аксиом как раз весьма просто – надо вывести из аксиом противоречие. Таким образом, к примеру, была опровергнута система аксиом Готтлоба Фреге.

Многие математики убеждены в непротиворечивости системы аксиом Цермело-Френкеля; другие считают, что в случае противоречий будет изобретена новая система аксиом, и осмысленную часть математических утверждений с легкостью переведут на новый язык (и так до бесконечности, по мере обнаружения противоречий). Именно этой точке зрения следовала группа Бурбаки.

Есть немало математиков, считающих, что аксиоматический метод порочен сам по себе. Эта точка зрения была выдвинута голландским математиком Брауэром (Luitzen Egbertus Jan Brouwer), знаменитым топо-

логом, в 1908-м году, в статье, провокативно озаглавленной “De onbetrouwbaarheid der logische principes” “О сомнительности основ логики”. Брауэр счи-

тал, что классическая (аристотелева) логика не может быть применима к бесконечным множествам, и все математические исследования, которые основаны на таких применениях неправильны. Особенно Брауэру не нравился принцип исключенного третьего, на котором основаны популярные доказательства “от противного”. На протяжении 1920-х годов Брауэр был редактором журнала Mathematische Annalen, и он принципиально возвращал авторам все статьи, где использовались доказательства от противного.

Брауэр называл свою философию “интуиционизмом”. В середине XXго века русские математики, близкие к Маркову и Колмогорову, развили свою версию философии интуиционизма, под названием “конструк-

4. Аксиома выбора и ее приложения

тивизм”;1 как и интуиционисты, конструктивные математики отрицают классическую математику, точнее все неявные доказательства существования.

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

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

4.3. Аксиома выбора и ее конкуренты

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

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

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

Ближе к концу 1920-х годов оказалось, что аксиома выбора позволяет доказывать (наряду с верными и полезными) утверждения чрезвычайно сомнительные и противоречащие физической интуиции. Так, в 1924-м году Банах и Тарский обнаружили парадоксальное разложение шара в R3 в счетное количество частей, из которых можно сложить два таких же шара. Сейчас известно, что шар можно разложить в 5 частей, и сложить из них два таких же шара, изометрически передвигая эти части в R3.

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

Впрочем, исключение аксиомы выбора не избавит математику от противоречий: непротиворечивость системы Цермело-Френкеля с аксиомой

1Надо отметить, что лично Колмогоров не одобрял конструктивизма.

Часть I. Основания математики

выбора1 равносильна непротиворечивости Цермело-Френкеля без нее. Тем не менее, хорошим тоном считается не пользоваться аксиомой вы-

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

В математике (кроме очень экзотических областей) без аксиомы выбора довольно часто удается обойтись. Основные утверждения, для которых нужна аксиома выбора, такие.

1.Теорема о существовании максимальных идеалов (см. лекцию 9).

2.Теорема о существовании базиса в любом бесконечномерном векторном пространстве (“базиса Коши-Гамеля”).

3.Теорема Хана-Банаха о существовании замкнутой гиперплоскости, разделяющей два выпуклых, непересекающихся, замкнутых подмножества в топологическом векторном пространстве.

4.Теорема Тихонова о компактности произведения бесконечного количества компактов.

Аксиома выбора влечет много утверждений, которые не нужны для доказательства полезных теорем, и противоречат интуиции наподобие парадокса Банаха-Тарского. Основная проблема, которая следует из принятия аксиомы выбора существование неизмеримых множеств, множеств, для которых не определена мера Лебега (мерой Лебега в математике называется понятие “объема подмножества" в Rn; неизмеримые подмножетва подмножества, для которых не определен объем). Множества, которые фигурируют в парадоксе Банаха-Тарского, очевидно неизмеримы: иначе суммарный объем пяти частей, на которые разбит шар, не мог бы равняться удвоенному объему шара.

Существуют аксиомы теории множеств, которые противоречат аксиоме выбора; самая известная из них аксиома детерминированности (axiom of determinacy), из которой, среди прочего, следует, что любое подмножество Rn измеримо.

Неизвестно, следует ли из непротиворечивости ZF+AC непротиворечивость системы Цермело-Френкеля с аксиомой детерминированности (ZF+AD). Другими словами, ZF+AD может оказаться противоречива, даже если ZF+AC непротиворечива. Поэтому ZF+AD не нашла широкого употребления.

Другая причина, по которой аксиомы, отрицающие аксиому выбора, не нашли употребления, такая. Пусть X и Y два множества. Из

1Эту систему аксиом часто обозначают ZF+AC, или ZFC.

4. Аксиома выбора и ее приложения

аксиомы выбора следует, что либо X равномощно подмножеству Y , либо Y равномощно подмножеству X. Оказывается, что это утверждение равносильно аксиоме выбора. Поэтому из любой аксиомы, отрицающей аксиому выбора, следует существование таких множеств X и Y , что X не равномощно подмножеству Y , а Y не равномощно подмножеству X. Вместо изящной иерархии кардинальных чисел,2 построенной Кантором, мы получаем огромное количество множеств, которые никак не соизмеримы по мощности.

Вместо использования аксиомы выбора можно пользоваться ее слабой формой, которая называется аксиома зависимого выбора (dependent choice). Аксиома зависимого выбора утверждает следующее. Пусть дано множество X, и подмножество V X X такое, что 1(V ) = X, где 1 проекция на первый сомножитель. Тогда есть бесконечная последовательность fxig такая, что (xi; xi+1) 2 V , для любого i.

Система аксиом Цермело-Френкеля без аксиомы выбора, но с зависимым выбором (ZF+DC) достаточна для почти всех задач, где необходим выбор, но недостаточна для утверждений 1-4, перечисленных выше. Также она следует из аксиомы детерминированности.

Любопытно, что непротиворечивость Цермело-Френкеля равносильна непротиворечивости системы аксиом, состоящей из ZF+DC плюс аксиомы "каждое подмножество Rn измеримо". Кроме того, DC следует из аксиомы детерминированности.

4.4. Вполне упорядоченные множества

Определение 4.1. Пусть X множество, а R X X бинарное отношение на множестве X, обозначенное x1 x2. Это отношение называется отношением частичного порядка (partial order), если верны следующие утверждения

транзитивность: из x y и y z следует x z.

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

Часть I. Основания математики

асимметричность: если x y, то невозможно y x.

Множество (X; ) с отношением частичного порядка называется частично упорядоченным множеством.

Определение 4.2. Пусть (X; ) частично упорядоченное множество. Если для каких-то x; y 2 X имеет место x y либо y x, мы говорим, что x и y сравнимы. Отношение называется отношением линейного порядка (total order), если любые два элемента сравнимы. Множество (X; ) с отношением линейного порядка называется линейно упорядоченным множеством, или цепью.

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

Если x = y или x y, мы пишем x 4 y.

Определение 4.3. Пусть (X; ) линейно упорядоченное множество, а Y X его подмножество. Элемент y0 2 Y называется минимальным, если для любого y 2 Y , имеем y0 4 y. Линейно упорядоченное множество называется вполне упорядоченным (well-ordered set), если любое его подмножество имеет минимальный элемент. Отношение порядка на таком множестве называется отношением полного порядка.

Определение 4.4. Начальным элементом вполне упорядоченного множества называется его минимальный элемент. Отрезком линейно упорядоченного множества (X; ) называется подмножество Y X такое, что для любых x; z 2 Y , и любого y 2 X такого, что x y z, имеем y 2 Y . Начальным отрезком вполне упорядоченного множества называется отрезок, содержащий минимальный элемент. Начальным элементом отрезка называется его минимальный элемент.

Замечание 4.5. Пусть X0 X начальный отрезок вполне упорядоченного множества, x0 его начальный элемент, а x минимальный элемент в XnX0 (мы предполагаем, что это множество непусто). Легко видеть, что X0 множество всех y таких, что x0 4 y x (докажите это). Мы обозначаем такой отрезок [x0; x[.

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

4. Аксиома выбора и ее приложения

Georg Ferdinand Ludwig Philipp Cantor

(1845 1918)

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

Замечание 4.7. Ординалы можно складывать (для этого надо взять

F

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

(x; y) (x0; y0) если y y0; либо y = y0; x x0:

Задача 4.1. Докажите, что эти определения задают вполне упорядоченные множества. Докажите ассоциативность и умножения и сложения и дистрибутивность слева сложения относительно умножения. Приведи-

1Классы изоморфизма суть классы эквивалентности по соотношению “изоморфизм”.

Часть I. Основания математики

те примеры, когда сложение и умножение ординалов не коммутативно и не дистрибутивно справа.2

Теорема 4.8: Пусть X, Y вполне упорядоченные множества. Тогда X изоморфно начальному отрезку Y , либо Y изоморфно начальному отрезку X. Более того, такой изоморфизм определен однозначно.

Доказательство: Пусть Z множество пар (X1; Y1) изоморфных начальных отрезков X и Y .

Шаг 1. Изоморфизм начальных отрезков (X1; Y1) определяется однозначно множеством X1. В самом деле, пусть существует два различных вложения ' : X1 ! Y и '0 : X1 ! Y , задающие изоморфизм X1 и начального отрезка Y . Обозначим через x минимальный элемент мно-

и '0 изоморфизмы, из этого следует, что '(x) = '0(x).

Шаг 2. Мы получили, что Z упорядочено по включению и это задает на Z полный порядок (докажите). Пусть x минимальный элемент X, не принадлежащий X1 для какого-то (X1; Y1) 2 Z. Если такого нет, это значит, что X изоморфен начальному отрезку Y . Если Y1 = Y , мы все доказали. В противном случае, начальный отрезок [x0; x[ изоморфен начальному отрезку [y0; y[, следовательно, отрезок [x0; x] изоморфен [y0; y]. Мы пришли к противоречию. Это доказывает Теорему 4.8.

Теоремой Цермело называется следующее утверждение, доказанное Эрнстом Цермело в 1904-м году.

Теорема 4.9: (Теорема Цермело, "well-ordering theorem") Любое множество может быть вполне упорядочено.

Теорема Цермело равносильна аксиоме выбора; мы докажем это немного погодя.

2Дистрибутивность слева: x (y + z) = x y + x z. Дистрибутивность справа:

(y + z) x = y x + z x.