Текст
ВВЕДЕНИЕ
В АКСИОМАТИЧЕСКУЮ
ТЕОРИЮ МНОЖЕСТВ
Н. И. Казимиров
Петрозаводск 2000
УДК 517.2
Казимиров Н. И. Введение в аксиоматическую теорию множеств:
Учеб. пособие. — Петрозаводск: Изд-во (не опр.)г 2000. — 104 с.
Книга представляет собой краткое изложение курса
аксиоматической теории множеств и посвящена теории порядковых и
кардинальных чисел, а также изложению фундаментальных
математических определений в терминах теории множеств, и может быть
использована j\ah подготовки спец. курсов по теории множеств.
Библиогр. 14 назв.
Рецензенты:
д.ф.-м.н. А. В. Иванов, д.ф.-м.н. В. М. Тарарин
® Н. И. Казимиров, 2000 г.
Содержание
Введение 4
1 Основание 10
§1.1 Формальная аксиоматика 10
§ 1.2 Основные свойства множеств 14
§ 1.3 Определяемые отображения и функции 17
§ 1.4 Отношения и их свойства 22
§ 1.5 Натуральные числа 25
§ 1.6 Суммы и произведения множеств 28
§ 1.7 Классы множеств 32
2 Ординалы 36
§2.1 Определение и свойства ординалов 36
§ 2.2 Рекурсивные определения. Порядковые типы 42
§ 2.3 Арифметика ординалов 46
§2.4 Аксиома выбора 51
3 Кардиналы 63
§3.1 Мощность множества. Алефы 63
§3.2 Конечные и бесконечные множества. СН 71
§ 3.3 Предельные теоремы. Теорема о квадрате 74
§ 3.4 Арифметика кардиналов 78
§ 3.5 Типы кардиналов. Аксиомы бесконечности 83
§ 3.6 Универсальные множества. Метод моделей 87
Литература 97
Указатель обозначений 98
Предметный указатель 101
1*
Введение
Изложение курса начнем с рассмотрения наивной (канторовской)
теории множеств [1г 2]. Для начала опишем язык (или символику)
теории множеств. В теории множеств (как в наивной, так и в
формальной) мы любой объект считаем множеством, т. к.г во-первых,
это ничуть не мешает нам моделировать при помощи теории
множеств реальные объекты, а во-вторых, это упрощает построение
самой теории.
Для обозначения произвольных множеств мы будем использовать
латинские буквы а, 6,..., z, которые в дальнейшем будем называть
переменными.
Основной логической формулой при описании множеств
является формула вида х е у, где переменные х, у могут быть
заменены любыми другими переменными. Отметим также, что в
формуле х е у переменные х, у, обозначающие произвольные множества,
имеют несколько более конкретный смысл, а именно, у обозначает
некое множество элементов-множеств, среди которых есть
множество х. Поэтому формула х е у читается «х есть элемент у» или же
«х принадлежит у», иногда также говорят «у содержит х (в качестве
элемента)». Из основной, а далее мы будем называть ее
атомарной, формулы можно при помощи логических связок и кванторов
строить новые формулы, описывающие различные свойства
множеств. Для этого введем в рассмотрение символы логических связок
и кванторов: ] заменяет частицу «не», Л — союз «и», V — «или», —>>
— «следует», о — «тогда и только тогда, когда», «равносильно», V
— и/\ая любого», 3 — «существует».
Построение формул происходит рекурсивно с использованием
атомарной формулы и логических связок и кванторов. Так, при
помощи атомарной формулы можно построить формулы: [х е у) Л (х е
z), Зх ((х е z)/\\(x g j/)). Переменная в формуле называется
связанной, если она стоит под каким-либо квантором, в противном случае
она называется свободной. Так, в формуле Зх ((х е z) Л (\(х е у))
переменная х связанная, а переменные у, z свободные.
5
Сами формулы мы также будем часто обозначать переменными,
для этих целей мы используем греческие буквы ср и ф, указывая в
скобках, если нужно, переменные, свободно входящие в формулы.
Например, мы можем обозначить формулу х е у через (р, (р(х), (р(у),
<р(х,у) или <р(у,х). При этом всегда следует помнить, какие именно
переменные указаны в скобках, чтобы при замене переменных не
нарушалась структура формулы. Так, если у нас через (р(х)
обозначена формула х е у, то (p(z) будет обозначать формулу z е у] если
же мы обозначили через (р(х) формулу у е х, то (p(z) уже будет
обозначать формулу у £ z \
Чтобы не использовать громоздкие записи формул (которые к
тому же часто оказываются неудобочитаемыми), мы будем
использовать сокращения записи /\ая формул. Ниже приводится список
сокращений, в котором слева от значка := ставится определяемый
символ, а справа — формула, которую он заменяет.
Ух е а : ср
Зх е а : (р
аСЪ
а — Ъ
а С Ъ
а ф b
афЪ
— Ух (х е а —>> (р)
= Зх (х е а Л (р)
= Ух (х е а -^ х е Ъ)
= (а С 6) Л (Ь С а)
= (а С 6) Л (а ^ 6)
=] (а G 6)
=1 (а = Ь)
Первые два определения здесь являются не сокращениями ^^ая
конкретных формул, а схемами сокращений, а каждое конкретное
сокращение определяется уже конкретной заменой переменной ср
на некоторую формулу.
Некоторые из этих формул читаются специальным образом, а
именно, а С b читается «а содержится в 6» или «а есть подмножество
6», а С b — «а есть собственное подмножество 6».
Все обозначения, приведенные тут, стандартны и встречаются во
всех областях математики. Заметим, что равенство множеств мы
определяем, а не рассматриваем его как нечто предопределенное, и
выражает оно тот факт, что множества, состоящие из одних и тех
же элементов, равны.
Кроме обозначения формул используются также обозначения /\ая
множеств. Это связано с тем, что множества можно задавать
посредством некоторых формул. Например, j\ah обозначения множества,
6
ВВЕДЕНИЕ
составленного из двух элементов х,у, используется символ {х,у}.
Определение такого множества через описание его элементов
осуществляется указанием формулы (p(z) \—z — х V z — у} т. е.
множество {х, у} состоит из всех таких элементов z, &ая которых истинно
(p(z). Такой способ описания множеств мы и зафиксируем в
следующих обозначениях (обычно их принято называть термами). Через
{х\ (р(х)} условимся обозначать множество всех таких х, &ая которых
(р(х) истинно,1 далее положим:
{а, Ь}
{а}
ailb
aUb
a\b
Ua
Exp (а)
S(a)
0
={x\ x = a V x = b}
—{a, a}
—{x
—{x
—{x
—{x
—{x
x e а л x e b}
x e a v x e b}
x e а Л x £ b}
3y e a : iGj/}
x С a}
— a U {a}
={x| i/x}
Понятно, что все эти термы, кроме S(a)1 имеют свои названия, и
все эти названия стандартны /\ая любой области математики.
Например, ailb обозначает пересечение множеств а и 6, терм Ехр(а)
обозначает множество всех подмножеств множества а и называется экс-
понентой или степенным множеством множества а, а терм {а},
обозначающий одноточечное множество, называется синглётом. Терм
5(a) будет использоваться нами достаточно часто при изложении
курса, поэтому мы введем название и /\ая него. Множество S(a)
будем называть последующим за множеством а. Если раскрыть его
определение более подробно, то нетрудно заметить, что j\ah всякого
элемента х е S(a) имеет место х е a V х — а. Это множество на один
элемент расширяет множество а, добавляя в качестве элемента само
множество а.
1 Такой способ описания множеств заставляет нас использовать термы, в
которых присутствуют связанные переменные и формулы: в терме {х\ ц>(х)}
переменная х связана, а фигурные скобки играют здесь роль квантора с тем лишь
отличием, что в итоге мы получаем не формулу, а терм. Таким образом, язык,
который мы описываем сейчас, не является языком первого порядка [3, 4].
Поскольку языки первого порядка имеют несколько преимуществ (с точки зрения
простоты их изучения) перед остальными языками, то в § 1.1 мы построим теорию
множеств в языке первого порядка — без использования подобных термов.
7
Из определения равенства множеств нетрудно заключить, что &ая
каждого множества х истинно х — х, поэтому в пустом множестве 0
нет ни единого элемента. Пустое множество 0 нам также
необходимо &ая построения теории множеств, какг например, число ноль в
арифметике. Так как мы хотим в результате пересечения множеств
всякий раз получать множество, то мы обязаны предусмотреть и
тот случай, когда два множества, пересечение которых мы ищем,
не имеют общих элементов, т. е. их пересечением является пустое
множество.
На этом завершается описание языка теории множеств.2
С самого начала мы предположили, что все множества, какие мы
рассматриваем в наивной (канторовской) теории множеств
представляют из себя произвольные наборы множеств, никаких других
ограничений на понятие множества мы не накладывали. Покажем,
что такое достаточно произвольное определение множества не
может быть корректным с точки зрения логики, ибо приводит к
противоречию. Следующий парадокс, который мы получим здесь,
называется парадоксом Расселла.
Поскольку атомарная формула х е у, выражающая
принадлежность множества х к множеству у, имеет смысл j\ah любых
множеств х и у, ничто не мешает нам рассмотреть такой ее вид: х е х.
С точки зрения здравого смысла формула х е х должна быть
ложной /\ая любого множества х, ибо мы считаем, что часть некоего
объекта (в данном случае множества) не может совпадать с самим
этим объектом. Поэтому мы вводим следующее определение:
множество х такое, что х £ х, называется регулярным, а множество х,
&ая которого х е х, назовем сингулярным.
Снова нам ничто не мешает собрать все регулярные множества
в одно множество Л, точнее, R\—{x\ х ф х}. Попытаемся теперь
ответить на следующий вопрос: регулярно или сингулярно множество
т
Предположим, что множество R регулярно, т.е. R ^ R. Но тогда
R удовлетворяет тому свойству, которым оно само определено,
значит, R е R. Противоречие. Предположим тогда, что R сингулярно,
т. е. R е R. Но тогда R не удовлетворяет тому свойству, которым
определены его элементы, следовательно, R £ R. Противоречие.
Итак, множество R не регулярно и не сингулярно, чего быть не
может, если мы принимаем закон исключенного третьего (либо А,
либо не А). Так может быть, R — не множество?
2Более подробно о языках теории множеств и их анализ см. в [Зг 4].
8
ВВЕДЕНИЕ
Полученный парадокс, как может показаться, доказывает
несостоятельность самой идеи множества, как высшей точки абстракции
в математических науках. На самом же деле весь тот путь, который
мы прошли при построении множеств и при рассмотрении
парадокса Расселла, уже дает предпосылки к решению этого парадокса.
Мы с самого начала считали, что множество есть произвольная
совокупность (множеств), что привело к построению парадоксального
множества R. Насколько велико это множество, мы также не
знаем, ибо мы предположили существование сингулярных множеств. С
другой стороны, если предположить, что все множества регулярны,
то R будет просто множеством всех множеств. Конечно, это не
избавляет нас от противоречия, но зато дает повод попытаться
исключить из рассмотрения сингулярные множества, а также «слишком
большие» совокупности множеств путем навязывания множествам
некоторых условий или, как принято говорить, аксиом.
Мы пойдем примерно по тому же пути, каким в свое время пошел
Цермело, опубликовавший впервые в 1908 году некоторые аксиомы
теории множеств, которые были впоследствии дополнены
Френкелем. Мы воспользуемся методом формализации Гильберта, который
впервые был применен Гильбертом при построении формальной
аксиоматической геометрии [5] (чем, собственно, была закрыта
проблема пятого постулата Евклида) и развит в его совместном с Бер-
найсом фундаментальном труде «Основания математики» [6].
Для этого мы попытаемся определить основные требования к
множествам так, чтобы избежать известных парадоксов наивной теории
множеств и в то же время сохранить уровень абстракции понятия
множества.
Перечислим некоторые из этих требований.
1) Основное свойство равенства (по Гильберту [6]),
заключающееся в следующем: если х — у, то если истинно ср(х), то таково
же и ср(у). Это свойство множеств мы будем называть
объемностью.
2) Существование пустого множества 0.
3) Из двух множеств х и у можно получить пару множеств {х, у},
которая также будет множеством.
4) Для всякого множества х ко множествам отнесем и его
объединение Ux.
9
5) Для всякого множества х множеством назовем и его степень
Ехр(х).
6) Если х множество, a cp(z) — формула, то множеством будет
также и {z\ z е х Л <p(z)}.
7) Все множества будем считать регулярными.
Все эти требования, кроме последнего, отражают
конструктивные аксиомы множеств, т. е. аксиомы, являющиеся, по сути,
правилами /\ая построения множеств, отправляясь от пустого
множества. Однако этих аксиом еще оказывается недостаточно /\ая того,
чтобы формализовать в теории множеств большинство
математических результатов, например, из-за отсутствия аксиомы
бесконечного множества. Полный набор аксиом, представляющий сегодня
формальную теорию множеств Цермело—Френкеля включает
девять аксиом, с формулировки которых мы и начнем рассмотрение
аксиоматической теории множеств.
Глава 1
ОСНОВАНИЕ
§ 1.1 Формальная аксиоматика
Предмет изучения данного параграфа представляет собой язык
первого порядка (ибо в качестве термов мы используем только
переменные), более простой, чем тотг с которым мы имели дело во
введении, с набором аксиом, которые мы приведем чуть позже. Язык,
который мы опишем здесь, по традиции мы будем называть ZF —
по первым буквам создателей аксиоматической теории множеств
Цермело (Zermelo) и Френкеля (Fraenkel). Этот же символ (ZF) мы
будем использовать и j\ah обозначения только аксиоматики нашей
теории.
Как и прежде, мы используем здесь латинские буквы а, Ь,..., z в
качестве переменных, пробегающих множества, греческие буквы ip
и ф в качестве обозначений формул и принимаем все те правила
построений формул и сокращений записи формул, о которых шла
речь во введении. 1
Аксиоматика ZF (по Колмогорову [4]) представляет собой
следующий список аксиом.
51. Аксиома экстенсиональности (объемности):
x = y^(xEz^yEz).
52. Аксиома пустого множества:
ЗиУг z £ и.
!Мы пока избегаем использования сокращений для записи множеств (термов),
которые были уже определены во введении, поскольку хотим сформулировать
аксиомы в максимально простом языке, см. [3, 4].
§1.1. ФОРМАЛЬНАЯ АКСИОМАТИКА
11
53. Аксиома пары:
Зи \/z (z е и <^> (z = х V z = у)).
54. Аксиома объединения (суммы):
Зг/, Vz (z е г/, <^ Зг; (г е г; Л г; е х)).
55. Аксиома степенного множества (экспоненты):
3n Vz (z G n <^> z С х).
S6[<^]. Схема аксиом содержательности (выделения):
ЗиУz (z Е и ^ z Е х /\ <p(z)),
где формула (p(z) языка ZF не содержит свободно переменной и.
S7. Аксиома регулярности (фундирования):
(3z z е х) —>* (3z Gx:]3n(nGzAnG х)).
S8[<^]. Схема аксиом подстановки:
Зи \lz (z е г/, <^ Зх е г; : <р(х, 2;) Л Угу ((р(х, w) —>> z = ги)),
формула (p(x,z) не содержит свободно переменных и и v.
S9. Аксиома бесконечности:
Зг/, (Уг (Ух x^z)^zEuA
\/z Е и : (\/v (Ух xEv^xEzMx — z)^vE и)).
Нетрудно убедиться в томг что первые семь аксиом SI — S7
практически в точности повторяют те требования к множествам, которые
были нами сформулированы во введении. Например, аксиома S2
выражает существование пустого множества, р^\я этого достаточно
воспользоваться определением терма 0Г приведенного нами во
введении. Аксиома S1 имеет более тривиальный вид, чем наше
требование 1). Оказывается, что аксиомы S1 достаточно /\ая выполнения 1),
о чем свидетельствует следующая теорема о равенстве множеств.
Теорема 1.1. Равенство множеств удовлетворяет следующим
свойствам:
1) х = х для любого множества х.
2) для произвольной формулы (р(х) со свободной переменной х:
х = у-> (ср(х) -> ср(у))
12
ГЛАВА 1. ОСНОВАНИЕ
Доказательство. Первое утверждение вытекает непосредственно
из определения равенства и правил вывода, &ая проверки
второго необходимо воспользоваться всеми сокращениями j\ah формул и
правилами вывода (см. [6])г а также аксиомой S1.
Сначала заметим, что равенство множеств симметрично, т. е. из
х — у вытекает у — х, что проверяется непосредственно по
определению формулы равенства.
Доказательство утверждения 2) проводится индуктивно по
сложности формулы <р, а аксиома S1 является базой индукции. Именно,
сначала необходимо проверить, что 2) справедливо в том случае,
когда (р(х) является атомарной формулой. При этом ср может иметь
один из следующих двух видов: либо ср(х) \—z е х, либо ср(х) \—x^z.
Понятно, что вместо z можно подставить любую другую
переменную. Справедливость утверждения 2) рфя формулы z е х вытекает
непосредственно из определения равенства (см. Введение); ^я
формулы х е z утверждение 2) есть в точности аксиома S1.
Итак, 2) выполняется /\ая атомарной формулы. Предположим
далее, что 2) верно /\ая формул ср(х) и ф(х). Теперь необходимо
показать, что 2) будет справедливо и ^^ая формул ~}(р(х), (р(х) Аф(х),
3z (p(x,z), где z свободно входит в (р. Все прочие формулы
являются комбинациями перечисленных только что формул, поэтому нет
необходимости их рассматривать.2
Рассмотрим сначала ](р(х). По предположению
х = у^ (<р(х) -+<р(у)),
откуда заменой переменных получаем
у = х^ (<р(у) -+<р(х)).
Из симметричности равенства и по правилу контрапозиции [6]
получаем
х = у ^ (]<р(х) -+]ср(у)),
что и требовалось.
Рассмотрим теперь ср(х) Аф(х). Поскольку в силу предположения
имеем
х = у-> (ср(х) -> ср(у)), х = у -> (ф(х) -> ф(у)),
то по правилу соединения выводов [6] получим:
х = у^> (<р(х) ->► <р(у)) Л (ф(х) ->► ф(у)),
2Действительно, ip V ф <£>] (] <рЛ]ф); <р —>• ф <£>] <р V ф;
[(р <£> ф] <^> [ip ->. ф) л (ф -> ip)\ Vx if о](Эх](р).
§1.1. ФОРМАЛЬНАЯ АКСИОМАТИКА
13
откуда по правилу введения конъюнкции [6] заключаем:
х = у^> (<р(х) Л ф{х) -+ <р(у) Л ф{у)).
Рассмотрим, наконец, формулу 3z (p(x,z). Из предположения
х = у^ (<p(x,z) ->cp(y,z))
по правилу введения квантора существования [6] получаем
х = у^> (<р(х, z) -л 3t <р(у, *)),
откуда контрапозицией приходим к
х = у ->► (Vt]cp(y,i) -+]cp(x,z)),
где применяем правило введения квантора всеобщности [6]:
x = y^(Vt]<p(y,t)^Vt]<p(x,t)),
откуда заменой переменных и по правилу контрапозиции получим:
х = У -+ (Зя <р(х, z) -л 3z <р(у, z)).
Итак, мы показали, что при построении произвольной формулы,
отправляясь от атомарной формулы, на каждом шаге построения
формула удовлетворяет свойству 2). Таким образом, ^я любой
заданной формулы <р(х) свойство 2) выполнено. □
Данная теорема о равенстве показывает, что равенство множеств,
определенное нами через атомарную формулу принадлежности,
удовлетворяет аксиомам равенства, сформулированным Гильбертом
в «Основаниях математики» [6].
Аксиома регулярности выражает несколько иное свойство
множеств, чем то, которое было обозначено нами 7), а именно: в каждом
множестве есть наименьший по принадлежности элемент. Почему
это так, нам еще предстоит выяснить. Обычно множества,
удовлетворяющие аксиоме S7, называют фундированными (см., например,
[7, 8]), что отмечено нами в названии аксиомы. На самом деле,
любое фундированное множество регулярно, о чем также пойдет речь
в следующем параграфе.
Роль схемы аксиом подстановки и аксиомы бесконечности мы
установим немного позднее, когда уже будет накоплен некоторый
опыт работы с множествами.
14
ГЛАВА 1. ОСНОВАНИЕ
В этом параграфе мы рассмотрели формальную аксиоматику
теории множеств и соответствующий формальный язык ZF. В
дальнейшем мы не будем придерживаться только языка ZF при построении
тех или иных объектов в теории множеств и при доказательстве ее
теорем. Это неразумно, т. к. формальный язык, будучи чрезвычайно
строгим инструментом, не является удобочитаемым языком.
Поэтому чаще всего мы будем применять разговорный (русский) язык и
сокращения j\ah термов, принятых нами во введении, однако при
этом не следует забывать о том, что все наши рассуждения о
множествах должны формализовываться в ZF.
Все последующее построение теории называется содержательной
частью теории множеств, ибо под множествами мы будем все же
понимать не чисто формальные термы, а некоторые вполне понятные
нам объекты.
§ L2 Основные свойства множеств
Приведем здесь еще раз сокращения записи множеств,
используемые в нашем изложении: {х\ (р(х)}, {а, b}, ailb, aUb, a\b, Ua, Ехр(а),
S(a), 0.
То, что большинство из этих термов являются множествами, нам
еще предстоит доказать. А сейчас условимся, что в качестве
переменных, обозначающих множества, мы будем использовать не
только строчные латинские буквы а, 6,..., z, но также заглавные
А, Б,..., Z, кроме S (она занята у нас /\ая обозначения
последующего множества), все греческие, кроме ср, ф и и, и все готические
21, а, *В, Ь,..., 3,3? кроме с, 2J и Я, сочетая их с различными
математическими акцентами (например, А1', х и прочее). Буквы ш, с, 9J и 11
будут использоваться нами как обозначения некоторых конкретных
объектов, т. е. в качестве термов-констант.
Кроме перечисленных способов записи множеств (термов) мы
будем вводить и новые, но в силу достаточно большого их количества
мы не будем перечислять здесь все эти термы, а вместо этого
условимся, что всякое новое обозначение мы будем вводить либо
средствами разговорного (русского) языка, либо при помощи символа
:=, как мы это уже делали ранее. Этот же символ мы будем
использовать при определении некоторых формул, например, ср(х) :=0 е х.
Теорема 1.2. Пусть А, В — множества, ср — некоторая формула
языка ZF. Тогда термы {х\ х е А Л (р(х)}г {А, В}, AnB, A\J В, А\В,
UAf Ехр(А), S(A)r 0 суть множества.
§ 1.2. ОСНОВНЫЕ СВОЙСТВА МНОЖЕСТВ
15
Доказательство. Для термов {х\ х е А А (р(х)}, {А, В}, иД Ехр(А),
0 доказательство непосредственно вытекает из аксиом S2—S6.
Рассмотрим терм A U В. Нетрудно видеть, что ЛиВ = и{Д В}, откуда
по аксиоме пары и аксиоме объединения получаем, что Аи В есть
множество. АпВ = {х\х е АЛх е £?}г откуда по аксиоме
содержательности получаем, что и А П Б — множество. Аналогично проверяется
терм А\В. Далее, поскольку S(A) = А и {А} и {А} = {А, А}, то по
уже доказанному S(A) — множество. □
Часто вместо терма {х\ х е А Л (р(х)} используют семантически
равный ему терм {х е А| <р(ж)}г чтобы подчеркнуть, что данный терм
определяет множество как часть другого более широкого
множества А при помощи формулы ср(х), и в этом случае говорят, что
множество {х е А\ (р(х)} является определяемой (формулой ф) частью
множества А.
Итак, мы видим, что р^\я терма {х\ <р(х)} мы не всегда можем
сказать, что он является множеством, аксиома содержательности,
которая ограничивает нас в этом, — это своеобразная «плата» за
устранение известных парадоксов теории множеств. Однако мы найдем
применение и терму {х\ (р(х)} в общем виде, когда будем вести
разговор о классах множеств (§ 1.7). Основная же часть теории (не
касающаяся классов множеств), подчеркнем еще раз, должна форма-
лизовываться в языке ZF.
Обратимся теперь к аксиоме регулярности S7. Фактически эта
аксиома утверждает, что /\ая каждого множества х оно либо пусто,
либо в нем найдется такой элемент z, что пересечение zilx пусто. Это
требование (фундированность) более сильное, чем регулярность, в
чем нас убеждает следующая
Теорема 1.3. Для любых множеств А и В
А^А, АеВ^В <£А.
Доказательство. Предположим, А е А. Рассмотрим множество {А}.
В этом множестве по аксиоме регулярности существует элемент z
(т.к. {А} не пусто), не имеющий общих элементов с А. Очевидно,
что z = А, а по аксиоме регулярности Ф = гГ\А = АпА = А, что
противоречит тому, что А не пусто (ведь А & А).
Для доказательства второй части утверждения рассмотрим
множество {А, В}. По аксиоме регулярности существует z е {А, В}
такой, что z П {А, В} = 0, откуда А П {А, В} = 0 или В П {А, В} = 0.
Если А п {А, В} = 0, то В £ А. Если же В П {А, В} = 0, то А $ В.
Противоречие. Итак, В 0 А. □
16
ГЛАВА 1. ОСНОВАНИЕ
Замечание 1. Аналогичные теоремы можно доказывать для
произвольных конечных последовательностей множеств. Такг например,
если имеет место А е В е С е D е Е, то не верно, что £ G i.
Для доказательства нужно рассмотреть множество {A,B,C,D,E},
которое является множеством как определяемая часть множества
Ехр(А UBUCUDUE), и вновь применить аксиому регулярности.
Этот пример можно обобщить и до бесконечных наборов множеств
с некоторыми ограничениями.
Определение 1.1. Пусть задана некоторая формула (р(х) языка ZF.
Мы говорим, что формула ср определяет множество а однозначно,
или что а, &ая которого ср истинно, единственно, если (р(а) и /\ая
любых х, у из того, что (р(х) Л (р(у), следует х — у.
Читателю предлагается самостоятельно проверить, что все
конструкции множеств {х е А\ (р(х)}, {А, В}, А П В, А и В, А\ В, иД
Exp (A), S(A), 0 определяются однозначно по исходным множествам
А,Ви формуле (р.
Определение 1.2. Упорядоченной парой (по Куратбвскому) множеств
а и b называется терм {{а}, {а, Ь}}, &ая которого впредь мы будем
использовать обозначение (а, Ъ), а множества а и b называются,
соответственно, левой и правой координатами пары (а, Ь).
Теорема 1.4. Упорядоченная пара множеств есть множество и для
любых множеств а, 6, с, d имеем:
(а, Ъ) = (с, d) О (а = с) Л (b = d)
Доказательство. По аксиоме пары нетрудно получить, что {а} и
{а, 6} суть множества, поэтому (х, у) также множество по аксиоме
пары. Докажем вторую часть теоремы.
Импликация справа налево следует из определения
упорядоченной пары и ее единственности при заданных координатах.
Пусть (а, Ь) = (с, d), т. е. {{а}, {а, 6}} = {{с}, {с, d}}. По аксиоме пары
здесь возможны следующие варианты: {а} = {с} Л {а, 6} = {с, d} или
{а} = {с, d} Л {а, 6} = {с, d} или {а} = {с, d} Л {а, 6} = {с} или {а} = {с}
Л {а, 6} = {с}.
Пользуясь определением равенства, в первом случае получим а =
= с и если 6 = с, то и с = d и, следовательно, 6 = d, если Ъ ф с,иоЪ — d.
Так или иначе, получаем а = с Л Ъ — d.
Предположим далее, что {а} = {с, d} Л {а, 6} = {c,d}. Из первого
равенства вытекает а — с — d, тогда из второго равенства получаем
§1.3. ОПРЕДЕЛЯЕМЫЕ ОТОБРАЖЕНИЯ И ФУНКЦИИ 17
{а, Ь} = {а}, поэтому а = 6 = с = d. Пусть теперь {а} = {с, d} Л {а, 6} =
= {с}. Тогда а = с = йис = а = 6г откуда вновь а = 6 = с = d.
Наконец, в последнем случае {а} = {с} Л {а, Ь} = {с} получаем а =
= сис = а = 6. Поэтому из (а, Ъ) — (с, d) следует {{а}} = {{а}, {а, d}}r
откуда {a, d} = {а}г откуда а — d. В итоге вновь получим а — b — с —
= d. □
Определение 1.3. Прямым (декартовым) произведением множеств А
и Б называется терм
Ах В :={z\ Зи е А : Зг; е В : z = (и, г;)},
а множества А и В называются, соответственно, левым и правым
сомножителями произведения А х Б
Теорема 1.5. Прямое произведение множеств есть множество и
определяется однозначно по множествам А и В.
Доказательство. Пусть An В множества. Если а е A, b е В, то {а} е
Ехр(А U Б), а также {а, 6} е Ехр(А и В). Поэтому (а, Ь) С Ехр(А и Б),
откуда следует (а, 6) е Ехр(Ехр(А UB)). Тогда
А х В = {х е Ехр(Ехр(АиБ))| Зае А : ЗЬ е В : х = (а,Ъ)}.
Поэтому в силу аксиомы степенного множества и аксиомы
содержательности прямое произведение А х В есть множество.
Однозначность построения А х В по множествам А и В вполне
очевидна. □
§1.3 Определяемые отображения и функции
Пусть имеется некоторая формула (р(х,у) языка ZF, в которой
переменные х, у входят свободно.
Определение 1.4. Мы говорим, что формула <р определяет (х н> у)—
отображение, если, во-первых, существуют х,у такие, что (р(х,у),
во-вторых, всякий раз из того, что ср(х, у) Л ср(х, z) следует у — z.
Значок (х \-> у), являющийся, вообще говоря, термом со
свободными переменными х, у, мы будем употреблять по мере
необходимости, точнее, тогда, когда нам будет важно указать данные
переменные в данном порядке, например, при формальном выводе
некоторых формул.
Z Н. И. Казимиров
18
ГЛАВА 1. ОСНОВАНИЕ
Пусть (р(х,у) определяет отображение, и пусть А — множество.
Язык теории множеств, описанный нами во введении, позволяет
нам определить терм
ran ((р\А) :={z\ Зх е А : <р(х, z)}.
Можно ли определить такое множество в теории ZF? Чтобы
ответить на этот вопрос, заметим j\ah начала, что формула
Зх е А : (р(х, z)
эквивалентна формуле 3
Зх е А : (<р(х, г) Л (Угу <р(х, w) —>* z = ги)).
Теперь обратимся к аксиоме подстановки S8. Нетрудно видеть, что
элементы множества и, существование которого нам гарантирует
эта аксиома, определяются ровно таким же способом (учитывая
показанную эквивалентность), как элементы гап((р\А). Поэтому
ran ((р\А) = {z\ Зх е А : (ср(х, z) Л \/w ((р(х, w) —>> z = ги))},
откуда гап(<р|А) — множество. В этом, собственно, и
заключается роль схемы аксиом подстановки, точнее, если у нас имеется
некое множество и формула, определяющая отображение, то по
этому множеству и формуле мы можем построить новое множество
гап((р\А), которое мы впредь будем называть областью значений
определяемого формулой ср отображения относительно множества
А.
Приведем пример одного часто используемого в теории множеств
определяемого отображения. Рассмотрим формулу (р(х,у):=у =
= S(x), которая, как мы знаем, достаточно просто формализуется
в ZF. Пусть х1 — 0, у1 — {0}. Нетрудно убедиться в том, что у1 — S(x')
при выбранных х',у'. Далее, предположим, что у — S(x) Л z = S(x).
Тогда, как легко проверить, у — z. Поэтому формула у — S(x)
определяет отображение. Назовем тогда букву S отображением,
определяемым формулой у = S(x). Тогда ^^ая каждого множества А область
значений ran (у = S(x)\A) отображения S относительно множества А
будет множеством по аксиоме подстановки.
3Говоря точнее, из условия, что (р(х,у) определяет (х \-> у) — отображение,
можно вывести эквиваленцию указанных формул, а значит, и показать их
дедуктивное равенство [6].
§1.3. ОПРЕДЕЛЯЕМЫЕ ОТОБРАЖЕНИЯ И ФУНКЦИИ 19
Перейдем к определению функции. Обычно в математике под
функцией принято понимать некоторое правило, по которому
элементам одного множества ставятся в соответствие элементы другого
множества такг что каждому элементу первого соответствует один
и только один элемент второго. Поскольку мы хотим использовать
теорию множеств /\ая описания всех математических объектов, то
такое определение функции насг понятно, не устроит. Ведь
объектами изучения аксиоматической теории множеств ZF являются
множества и только множества. Поэтому нам нужно определить
функцию именно как некоторое множество и никак иначе. Для этого мы
воспользуемся понятием, также часто используемым математиками,
— график функции. Ведь график функции, определенной на
множестве А и принимающей значения из множества В, есть не что
иное как подмножество прямого произведения А х В с
некоторыми специфическими свойствами. На этом и основано определение
функции в теории множеств Цермело—Френкеля.
Определение 1.5. Подмножество / С А х В прямого произведения
множеств А и В называется функцией (из А в В), если:
1) ^^ая каждого х е А существует у е В такое, что (х, у) е /;
2) из (ж, у) е f A(x,z) е f следует у = z.
Тот факт, что / есть функция из А в В принято записывать в виде
следующей сокращенной записи формулы: / : А —» В, при этом
говорят, что множество А есть область определения функции /. Для
обозначения области определения функции используют также терм
dom (/). Для каждого множества х е А мы можем рассмотреть
единственное множество у е В такое, что (х,у) е /. Условимся это
множество, однозначно определяемое функцией / и множеством х,
обозначать термом f(x), который будем называть значением функции f
в точке х. Тогда вместо формулы (х, у) е / мы можем записывать
эквивалентную ей формулу у = f(x), либо f(x) = у.
Множество
ran (/) \—{у G В\3х е А у — f(x)}
называется областью значений функции /.
Функция / : А —» В называется сюръекцией, если ran (/) = В,
инъекцией, если ^^ая любых х,у е А из равенства f(x) = f(y) вытекает
х — у, биекцией (взаимно однозначным соответствием), если /
инъекция и сюръекция одновременно. Для обозначения того факта, что
/ есть биекция из А в В, мы используем символ / : А о В. Если
же мы хотим выразить то, что существует биекция из А в В, то мы
пишем А о В.
2*
20
ГЛАВА 1. ОСНОВАНИЕ
Пусть f : А -> В и D С A, D ^ ®. Тогда функция
f\D :={(х, y)eAxB\xeDA(x,y)ef}
называется сужением функции / на множество D.
Пусть теперь / : А —» В, д : В —» С, тогда функция h : А —> С,
определяемая как h = {(x,z) ^ Ах С\ z — g(f(x))}, называется
суперпозицией функций fag, аая нее обычно используется обозначение
9°f-
Функция / : А —» А называется тождественной на А, если ^^ая
каждого х е А имеем f(x) — х. В этом случае ^я f принято
использовать обозначение id а-
Мы говорим, что /\ая функции / : А —» В функция д : В —» А
является обратной, если их суперпозиция тождественна, т.е. до f = id а-
Для обратной к / функции используется обычное обозначение /_1.
Следующая теорема показывает некоторые тривиальные свойства
обратных функций и биекций.
Теорема 1.6. f : А—> В, тогда:
1) существует f~l тогда и только тогда, когда f — биекция;
2) если существует f~l, то f~l — биекция;
3) если существует f~l, то f суть обратная к f~l функция.
Введем теперь еще несколько полезных обозначений и понятия
образа и прообраза множества относительно функции.
Если / : А —» В и С есть подмножество в А, то множество
fC:={yeB\3x(xeAAy = f(x))}
называется образом множества С относительно функции f.
Если /:А—^БиССБ, то множество
rlC-.={xeA\f(y)eC}
называется прообразом множества С относительно функции f.
Следует обратить внимание на тог что множество С здесь вовсе не
обязано быть подмножеством области значений функции /, а также
вполне может быть пустым множеством (в этом случае, очевидно,
образ и прообраз также будут пусты), и, кроме того, обратная
функция к функции / может и не существовать.
Если множество С в том и другом случае записано в виде
длинного многосимвольного терма, то удобнее заключать его в скобки,
§1.3. ОПРЕДЕЛЯЕМЫЕ ОТОБРАЖЕНИЯ И ФУНКЦИИ 21
поэтому для обозначений образов и прообразов разрешим
использовать и такие обозначения: 4
f[C] — для образа, f~l[C] — для прообраза.
Использование круглых скобок здесь недопустимо, ибо так мы
обозначаем значение функции в данной точке.
Предположим далее, что формула (р(х,у) определяет [х \-> у) —
отображение, и рассмотрим множество А такое, что существует
х е А, для которого найдется у такой, что (р(х, у). Как мы уже знаем,
существует множество ran ((р\А) — область значений определяемого
формулой ср отображения относительно А. Рассмотрим
подмножество / прямого произведения Ахгап ((р\А), определяемое следующим
образом:
/ = {(я, у) еАх ran (<р\А) | <р(х, у)}.
Поскольку ср определяет отображение, то для /, очевидно,
выполнено второе требование определения функции. Обозначим далее
через D подмножество множества А, включающее все те х е А,
для которых <р(х,у) истинно при каком-нибудь у. Тогда множество
/ будет функцией из множества D в множество гап(р\А), причем
ran (/) = ran (р\А).
Итак, мы видим, что по всякой формуле, определяющей
отображение, можно построить функцию (и даже далеко не одну). Для
такой функции обычно используется термин сужение отображения.
В наших обозначениях / есть сужение определяемого формулой ср
отображения на множество D. Понятие функции позволяет нам
рассматривать сужение отображения на некоторое (произвольно
выбранное) множество и, таким образом, вместо формулы (объекта
изучения метатеории) рассматривать вполне определенное
множество (объект изучения теории ZF).
Отметим также, что для всякой функции / можно определить
формулу ср(х,у):=(х,у) G /, и эта формула, как нетрудно
проверить, будет определять [х н> у) —отображение. Поэтому функцию
мы иногда будем называть определяемым отображением или просто
отображением.
В математике часто используется такое понятие как индекс. Здесь
мы намерены формализовать представление об индексе (хотя бы
частично).
4Куратовский и Мостовский [9] используют символ /1(С) для обозначения
образа множества С.
22
ГЛАВА 1. ОСНОВАНИЕ
Пусть имеется сюръекция / : / —» X. В этом случае мы можем
говорить, что множество X проиндексировано множеством I, при
этом функцию / мы будем называть индексацией. С чем связана
такая терминология? Понятно, что поскольку функция /
является сюръекцией, то для множества X справедливо равенство X =
= {f(i)\ г е /}. Введем вместо терма /(г) терм Х{. Тогда множество X
можно записать в виде терма {xi\ г е /}. Часто вместо такого терма
используют обозначение {хг}ге/- В таком виде обычно
записываются последовательности (в анализе) и другие проиндексированные
семейства множеств. Переменную г при этом принято называть
индексом.
Еще раз отметим, что в силу аксиомы подстановки S8 {хг}ге/
является множеством, если / — множество. Понятно, что переменные
х и г могут быть заменены на другие, лишь бы только не возникало,
как мы говорим, коллизий между переменными.
Индекс удобно использовать, например, /\ая обозначения
объединения элементов множества X: (J Х{, или их пересечения: Q Х{.
iei iei
§1.4 Отношения и их свойства
Определение 1.6. Любое подмножество множества Ах А называется
бинарным отношением (или отношением) на А.
«Вырожденные» случаи отношений на А: пустое 0 и полное Ах А.
Любая функция / : А —» В есть подмножество в А х В, а значит, и
в (A U В) х (A U В), поэтому / есть отношение на А и В.
Если R есть отношение на А и (а, Ъ) е R, то это принято записывать
так: aRb.
На любом множестве можно задать два также достаточно
стандартных отношения: равенство и принадлежность. Для обозначения
отношений используют, как правило, разные «экзотические»
символы, например, <,~, *, ^<.
Рассмотрим теперь некоторые виды часто встречающихся в
математике отношений.
Определение 1.7. (виды отношений) Отношение R на множестве А
называется
а) рефлексивным, если ^^ая любого х из А имеем xRx.
б) симметричным, если /\ая любых х, у е А из xRy следует yRx.
в) транзитивным, если ^^ая любых х, у, z е А из хДу Л уДг следует
§1.4. ОТНОШЕНИЯ И ИХ СВОЙСТВА
23
г) отношением эквивалентности, если оно рефлексивное,
симметричное и транзитивное.
Прежде чем перейти к определению отношений порядка,
рассмотрим некоторые свойства отношения эквивалентности. Для начала
введем следующие обозначения. Чаще всего отношение
эквивалентности обозначают символом ~. Множество [а]„ \—{х е А\ х ~ а} &ая
каждого а е А будем называть классом эквивалентности элемента
а е А. В случае, когда из контекста очевидно, о каком отношении
идет речь, вместо [а]„ мы будем писать просто [а]. Классы
эквивалентности обладают следующим свойством.
Теорема 1.7. Два класса эквивалентности либо не пересекаются
(пересечение пусто), либо совпадают.
Доказательство. Пусть ~ — отношение эквивалентности на
множестве A, a, b е А. Предположим, что [а] П [Ь] ф 0. Тогда существует
с е [а] П [Ь]. Тогда с ^ а и с ^ 6. Отсюда в силу симметричности и
транзитивности отношения ^ получаем а ~ Ь. Если х е [а], то х ~ а,
откуда х ~ Ь, т.е. х е [Ь]. Так что [а] С [Ь]. Аналогично получаем
[Ъ] С [а]. Итак, [а] = [6]. □
Нетрудно показать (используя аксиому степенного множества),
что j\ah любого множества А и любого отношения эквивалентности
на множестве А существует множество всех классов
эквивалентности множества А. Для его обозначения используют символ А/„ и
называют фактор-множеством множества А. Итак,
А/„ :={х е Ехр(А)| За е А : х = [а]^}.
Продолжим определение различных видов отношений.
Отношение R на множестве А называется
д) антирефлексивным, если /\ая любого а е А имеем ~}(aRa).
е) частичным упорядочением (или частичным порядком), если R
антирефлексивно и транзитивно.
ж) частичное упорядочение называется линейным порядком, если
^я любых элементов a,b е А выполнено условие связности:
(aRb) V (а = Ъ) V (6Да)
Чаще всего частичный порядок мы будем обозначать символом
< с индексами или без таковых. Если на множестве А задано
частичное упорядочение <, то пара (Д <) называется частично
упорядоченным множеством. Если < — линейный порядок, то (Д <) —
24
ГЛАВА 1. ОСНОВАНИЕ
линейно упорядоченное множество. Пусть далее (А, <) — частично
упорядоченное множество. Вместо формулы (х < у) V (х = у) будем
писать, как обычно, х ^ у. Пусть В С А. Элемент х е А называется
нижней (верхней) гранью множества В, если ^^ая любого b е В име-
ем х ^ b (b ^ х). Через inf В (sup Б) обозначают точную нижнюю
(верхнюю) грань множества В, которая должна удовлетворять тому
условию, что, во-первых, сама является нижней (верхней) гранью, а
во-вторых, j\ah всякой нижней (верхней) грани х множества В
имеет место х ^ inf В (sup Б ^ х). Если inf Б е В, то вместо символа inf
пишут min, в этом случае точная нижняя грань называется
минимумом. Если sup Б е Б, то вместо символа sup пишут max, и в этом
случае точная верхняя грань называется максимумом.
Иногда под символами sup, inf, min, max приписывают
обозначение того частичного порядка, в котором они определены, например,
sup Б.
<
Кроме понятия максимума множества есть также понятие
максимального элемента множества. Элемент х е Б называется
максимальным &ая множества Б, если ^^ая любого элемента b е Б не верно,
что х < Ь. Заметим, что в случае частичного упорядочения
формулы ] (х < Ь) и b ^ х не эквивалентны, т. к. частичное упорядочение,
вообще говоря, не связно, но из второй формулы выводима первая.
Поэтому максимум множества Б всегда является максимальным
элементом, но обратное в общем случае не верно. В случае
линейного порядка указанные формулы равносильны. Точнее, справедлива
следующая
Теорема 1.8. Пусть (Д <) — линейно упорядоченное множество и
В С At В ф 0. Тогда следующие утверждения равносильны:
1) х = max Б;
2) для любого ЬеВЬ^хихеВ;
3) х — максимальный элемент в В.
Равносильными являются также и утверждения
1) х = min Б;
2) для любого b е Б х ^Ь и х е Б.
Введем еще несколько терминов из теории упорядоченных
множеств. Пусть по-прежнему (А, <) — частично упорядоченное
множество и Б С А. Множество Б называется цепью в А, если частич-
§ 1.5. НАТУРАЛЬНЫЕ ЧИСЛА
25
ный порядок < линейно упорядочивает множество В. Цепь
называется ограниченной в А, если /\ая нее существует верхняя грань в
множестве А. Цепь называется сквозной в А, если у нее нет
верхней грани, не принадлежащей ей самой (т. е. либо у нее вообще нет
верхней грани, либо ее верхняя грань в А единственна и является
максимумом этой цепи).
Отношение линейного порядка на А называется вполне
упорядочением (или полным упорядочением), если каждое непустое
подмножество В С А имеет минимум. Пара (Д <)г где < — вполне
упорядочение на А, — называется вполне упорядоченным множеством.
Если (А, <) — частично упорядоченное множество, a,b е А, то
множества
[а; Ь] \—{х е А\ а ^ х ^ &}, [а; Ъ) \—{х е А\ а ^ х < &},
(а; Ь] \—{х е А| а < х ^ &}, (а; 6) :={х е А| а < х < Ь}
называются, соответственно, отрезком (или <-отрезком),
полуинтервалами и интервалом (<-интервалом). В том случае, когда
необходимо отметить, каким именно частичным порядком определен
отрезок, полуинтервал или интервал, мы допускаем обозначения:
[а;6]<, [а;6)<, (а;6]<, (а;Ь)<.
§ L5 Натуральные числа
В этом параграфе мы наконец воспользуемся девятой (последней)
аксиомой Цермело—Френкеля из приведенных нами в первом
параграфе аксиом SI — S9 — аксиоматики формальной теории ZF.
Определение 1.8. Всякое множество и, удовлетворяющее свойствам
1) 0Gcj;
2) Ух е ио : 5(х) £ cj;
3) Vx G cj : (ж ^ 0 ->► Зу G и : ж = 5(у));
называется множеством (порядковых) натуральных чисел. Для
обозначения такого множества мы всегда будем использовать букву
и. Элементы и называются (порядковыми) натуральными числами,
/\ая их обозначения мы, как правило, будем использовать буквы
n, m, l,p, q, s, если не оговорено противное. Условимся также, что
пустое множество 0 мы будем обозначать как 0 в том случае, если мы
используем его как порядковое натуральное число.
26
ГЛАВА 1. ОСНОВАНИЕ
Прежде, чем перейти к изучению свойств множества и, нам
необходимо доказать о нем следующий факт.
Теорема 1.9. Множество и существует и единственно.
Доказательство. По аксиоме бесконечности S9 существует
множество и, удовлетворяющее следующим свойствам: 0 е и и &ая всякого
х е и имеем S(x) е и. Таким образом, множество и
удовлетворяет требованиям 1) и 2) определения множества и. Будем называть
такие множества прогрессивными. В качестве множества
натуральных чисел и мы хотим взять наименьшее из всех прогрессивных
множеств, т. е. их пересечение. Точнее, положим
и = {х е и\ My {у — прогрессивное) -^ х е у}.
По аксиоме содержательности S6 и будет множеством. Нетрудно
установить, что и будет прогрессивным множеством, т. е.
удовлетворяет 1) и 2). Покажем, что и удовлетворяет условию 3). Для этого
выделим в и подмножество X, определенное как
X = {х е и\ х ф 0 -» (Зу е ио : х = S(y))}.
Нетрудно показать, что X прогрессивно. Действительно, 0 е X и
^^ая каждого у е X имеем у е и и, поскольку и прогрессивно, то
S(y) е и, но 5(у) удовлетворяет свойству элементов множества X,
поэтому S(y) е X. Итак, X прогрессивно. Тогда с одной стороны
имеем X С и, с другой — и С X, поскольку и содержится во всех
прогрессивных множествах. Таким образом, X — и.
А это и означает, что j\ah всякого х е ио если х ф $, то существует
у е 6J такой, что х — S(y), т. е. множество и удовлетворяет 3).
Покажем теперь, что множество ш, удовлетворяющее свойствам
1)—3), единственно. Пусть /\ая и' также выполнены условия 1) —
3). Допустим, что множество и \ и' не пусто. Тогда в силу аксиомы
регулярности S7 существует х е и \ и' такой, что х П (и \ и') = 0.
Поскольку х ф 0, то существует у е и такой, что х = S(y). Нетрудно
показать, что в этом случае j/Gw'. Но тогда в силу прогрессивности
множества и' имеем х е и?'. Противоречие. Итак, и \ и' — 0. Точно
так же доказывается, что и' \ и = 0. Таким образом, и = а/. Теорема
доказана. □
Вместо символа е JV^ натуральных чисел принято использовать
символ <. Это правило будет еще обобщено нами в главе 2. По
определению положим п + l:=S(ri) &ш всякого пей. Далее мы
займемся изучением структуры множества и.
§ 1.5. НАТУРАЛЬНЫЕ ЧИСЛА
27
Теорема 1.10. Множество и удовлетворяет аксиомам Пеано:
1) Оеи;
2) для любого пей имеем п + 1 е и;
3) для любого пей верно п + 1 ф 0;
4) для любых ri,m£(jn = m^n + l = m + l;
5) если ICo; ul прогрессивно, то X = и.
Доказательство этой теоремы несложно, и мы предлагаем
провести его читателю самостоятельно. Следующая теорема выражает
известный принцип математической индукции.
Пусть (р(х) — произвольная формула языка ZF.
Теорема 1.11. Если <р(0) и для каждого пей имеем (р(п) —» (р(п + 1),
то тогда Мп е ио \ (р(п).
Доказательство. Пусть X = {х е о;| <р(ж)}. Нетрудно убедиться в
томг что X есть прогрессивное множество и X С о;, поэтому X = gj,
откуда Мп е ио \ (р{п). □
Определение 1.9. Множество X назовем транзитивным, если для
каждого х е X имеем х С X.
Теорема 1.12. a; и каждый его элемент транзитивны.
Доказательство. Обозначим через X множество всех таких пей,
&ая которых п С и. Понятно, что X ф 0, т. к. 0 е X. Пусть n е Хг
отсюда следует, что п С а; и {п} С о;. Поэтому и множество n U {п} =
= п + 1 содержится в и. Таким образом, п + 1 е X. По принципу
полной индукции получаем, что X = о;. Таким образом, и транзи-
тивно.
Для доказательства транзитивности всех п е cj снова
воспользуемся индукцией по п. Очевидно, что 0 транзитивен. Предположим, что
транзитивно п. Рассмотрим множество n + 1 = nU {п}. Пусть ken.
Тогда либо ken, либо к = п. В случае ken имеем к С п, откуда
к С п + 1. В случае А; = п очевидно, что к С п + 1. Итак, п + 1
транзитивно. По принципу индукции заключаем, что каждое порядковое
натуральное число транзитивно. □
28
ГЛАВА 1. ОСНОВАНИЕ
Приведенная теорема позволяет описать нам натуральные числа
следующим образом:
0 = 0, 1 = {0}, 2 = {0,1}, 3 = {0,1,2},
п + 1 = {0,..., п} \—{т е ш\ т ^ п}
для каждого пей. Доказательство этого факта мы отложим пока до
главы 2, в которой мы в общем виде (для всех ординалов) докажем
ряд полезных свойств порядковых чисел (в частности натуральных)
таких, какг например, вполне упорядочение их отношением
принадлежности.
Об арифметических операциях (сложение и умножение) на
натуральных числах речь пойдет в следующей главе (§2.3)г когда мы
будем заниматься построением арифметики ординалов.
Ранее мы уже рассматривали на произвольных множествах такие
операции, как объединение, пересечение, разность, произведение
двух множеств. Все эти операции мы относим к арифметике
множеств. Теперь мы хотим пополнить список арифметических
операций на множествах сложением и умножением.
§L6 Суммы и произведения упорядоченных
множеств
Пусть {Lx}xec — проиндексированное множество множеств.
Определение 1.10. Множество
U Ы х Lx
хес
называется прямой суммой (или дизъюнктным объединением)
множеств Lx по множеству С и обозначается Y^LX.
с
Пусть далее (С, <с) — линейно упорядоченное множество и {<х
| х е С} — множество линейных порядков на множествах LX1 так что
для каждого х £ С множество Lx линейно упорядочено отношением
<х-
На прямой сумме Y^LX мы рассмотрим отношение -<;, удовлетво-
с
ряющее следующим условиям:
/ ч /74 Iх <с V или
(ж, а) -< (у, Ь) & {
\х = у Ла <х b (a,b е Lx)
§1.6. СУММЫ И ПРОИЗВЕДЕНИЯ МНОЖЕСТВ
29
для любых (х, а), (у, b) <EJ2LX.
с
Пара (Yl Lx, -< ) называется канонической суммой (или просто
суммой) линейно упорядоченных множеств по линейно
упорядоченному множеству, а отношение -< в этом случае называется
каноническим (линейным) порядком. Несложно проверяется следующее
утверждение о сумме линейно упорядоченных множеств.
Теорема 1.13. Сумма линейно упорядоченных множеств по линейно
упорядоченному множеству линейно упорядочена.
Если мы теперь предположим, что все линейные порядки <х суть
вполне упорядочения множеств LX1 а <с — вполне упорядочение
множества С, тог введя аналогично термин суммы вполне
упорядоченных множеств по вполне упорядоченному множеству, легко
показать усиление предыдущей теоремы, а именно
Теорема 1.14. Сумма вполне упорядоченных множеств по вполне
упорядоченному множеству вполне упорядочена.
Следующий вопрос, который мы здесь рассмотрим, — это
произведения множеств. Ранее мы уже говорили о прямом произведении
двух множеств. Теперь же мы хотим обобщить это понятие на
произвольный набор (множество) множеств. Как определить, например,
произведение множеств Д В и С? Можно воспользоваться
понятием упорядоченной пары, и на ее основе построить упорядоченную
тройку как ((а, 6), с), где а Е A, b Е В, с Е С. Нетрудно показать, что
существует множество всех таких троек (оно равно (А х В) х С).
Однако уже в этом случае видно «неравноправное» вхождение
компонентов тройки, ибо мы могли бы определить тройку как (а, (Ь, с))
и получить в итоге, вообще говоря, совершенно иное прямое
произведение трех наших множеств. Для того, чтобы нам не приходилось
выбирать и, кроме того, легко обобщить понятие упорядоченной
пары до упорядоченного набора (кортежа), мы поступим следующим
образом. Каждый упорядоченный набор элементов мы будем
рассматривать как функцию, определенную на некотором
упорядоченном множестве (например, числовая последовательность в анализе).
Это позволит нам задавать сколь угодно большие упорядоченные
наборы множеств. Перейдем к определению.
Вновь рассмотрим множество {Lx}xec проиндексированное
множеством С.
30
ГЛАВА 1. ОСНОВАНИЕ
Определение 1.11. Множество
Y[Lx:=\f\(f:C^ [J Lx) Л (Ухе С: f(x)eLx)\
с I хес )
называется прямым произведением множеств Lx по множеству С.
На вопрос — пусто или нет это множество — мы не можем пока
дать определенный ответ за исключением того случая, когда С = п,
т. е. когда индексирующее множество является натуральным
числом. При С — п мы можем доказать существование хотя бы одной
функции, являющейся элементом произведения, при бесконечных
С — нет, и этот вопрос мы отложим до § 2.4 об аксиоме выбора.
Теперь же мы предположим, что произведение не пусто, и перейдем
к изучению его свойств.
Функции, являющиеся элементами прямого произведения
множеств, называются кортежами. Если /\ая любого х е С имеем Lx — L
при некотором множестве L, то вместо П Lx используют символ Lc
с
(Йех в [10] предлагает символ СЦ, который, в сущности, обозначает
множество всех функций из С в L. Заметим, что поскольку все Lx
одинаковы, то при любом сколь угодно большом множестве С мы
можем доказать существование функции из С в L, т. е. что
множество Lc не пусто.
В качестве примеров приведем следующие: W1 — множество всех
п-ок вещественных чисел, W — множество всех
последовательностей вещественных чисел, 2Ш, где 2 = {0,1}, — множество всех
булевых (двоичных) последовательностей.
Предположим далее, что на каждом множестве Lx задан
линейный порядок <Х1 а на множестве С задано вполне упорядочение <с.
Определим на множестве ЦЬХ отношение -< следующим образом:
с
&ая любых f,g &ПЬХ положим
с
f f Зж е С : f(x) <х д{х) и
9 [VzeC: (z<cx^f(z)=g(z)).
Пара (П Lx,^ ) называется каноническим произведением (или
просто произведением) линейно упорядоченных множеств по вполне
упорядоченному множеству, а отношение -< — каноническим
(линейным) порядком. Справедлива следующая
Теорема 1.15. Произведение линейно упорядоченных множеств по
вполне упорядоченному множеству линейно упорядочено.
§1.6. СУММЫ И ПРОИЗВЕДЕНИЯ МНОЖЕСТВ
31
Доказательство. Для тогог чтобы установить, что -< есть линейный
порядок, очевидно, надо показать, что отношение -< антирефлексив-
но, транзитивно и связно.
1) Покажем антирефлексивность -<;. Если предположить / -< /, то
из (i.i) получим, что существует х е С такой, что f(x) <х f(x), что
противоречит антирефлексивности линейного порядка <х.
2) Покажем транзитивность -<;. Пусть / -<; д и д -<; h. Тогда
существуют х,у е С такие, что f(x) <х д(х), д(у) <у h(y) и j\ah любого
z е С из z <с х следует f(z) = g(z) и из z <с у следует g(z) = /i(z).
Обозначим через а минимум множества {х,у}, т. е. а = min{x,?/}.
Нетрудно проверить, что в этом случае f(a) <а h(a), т.к. имеют
место неравенства f(a) ^а д(а) и д(а) ^а h(a), причем по крайней мере
одно из неравенств строгое. Для любого z <с а имеем z <с х и z <с у
и, следовательно, f(z) = g(z) = h(z). Итак, / -< h.
Пункты 1) и 2), в доказательстве которых мы использовали
только линейное упорядочение множества С и частичное упорядочение
множеств ЬХ1 показывают, что произведение частично
упорядоченных множеств по линейно упорядоченному множеству есть
частично упорядоченное множество. Можно также показать, что снятие
условия связности с отношения <с не позволит нам доказать этот
факт.
3) Покажем теперь связность отношения -<. Пусть /, д е ЦЬХ.
с
Пусть также f ф д. Нам необходимо показать, что либо / -< д, либо
Выделим в множестве С множество В, составленное из всех таких
х е С, &ая которых f{x) Ф д(х). Ясно, что В ф 0 (иначе бы функции
/ и д были бы равны). В силу того, что <с суть полное
упорядочение, существует х = mini?. Понятно, что, во-первых, f(x) ф д(х),
а во-вторых, ^^ая каждого z <с х имеем f(z) = g(z). Теперь, в силу
связности отношения <х получим: f(x) <х д(х) или д(х) <х f(x). Если
f(x) <х д(х), то и / -< д, если д(х) <х f(x), то д -< /. Таким образом,
отношение -< связно, и теорема доказана. □
Для того, чтобы добиться полного упорядочения прямого
произведения множеств, не достаточно предположить дополнительно, что
<х суть вполне упорядочения множеств LX1 как это было в случае
суммы множеств. Необходимо также предположить, что множество
С конечно, или, не теряя общности, что множество С есть
натуральное число. Сформулируем этот результат в виде теоремы.
Теорема 1.16. Произведение вполне упорядоченных множеств по на-
32
ГЛАВА 1. ОСНОВАНИЕ
туральному числу является вполне упорядоченным множеством.
Проверку этой теоремы мы предлагаем читателю.
В качестве примера скажем, что на основании этой теоремы
нетрудно указать полное упорядочение такого множества, как ип.
Для того, чтобы убедиться в том, что условие конечности
множества С в общем случае мы снять не можем, приведем один простой
пример. Рассмотрим произведение 2й (множество всех булевых
последовательностей) с каноническим линейным порядком -<;.
Выделим в этом множестве подмножество В последовательностей Д(п),
определяемых формулами:
п ^ к
п > к
Нетрудно проверить, что fk -< fm тогда и только тогда, когда т < к
(здесь символ < обозначает порядок на натуральных числах).
Понятно, что в таком множестве нет наименьшего элемента (т. к. в и
нет наибольшего), а значит, 2Ш невозможно вполне упорядочить
канонически.
§ L7 Классы множеств
В этом параграфе мы рассмотрим понятие класса, которое,
вообще говоря, не принято формализовывать в ZF, но поскольку, как
показано в [7], введение понятия класса в теорию множеств не
приводит к противоречию, более того, обогащает теорию множеств, то
мы намерены также воспользоваться и этим понятием. Образно
говоря, класс — это произвольный определяемый набор множеств.
Точнее говоря, если у нас имеется некая формула (р(х) языка ZF, то
терм {х\ (р(х)} является классом. Каждое множество является
классом (т.к. А = {х\ х е А} &ая любого множества А), но не каждый
класс является множеством (об этом пойдет речь ниже). Классы,
не являющиеся множествами, мы называем собственно классами.
Для обозначения классов мы используем новый сорт переменных —
каллиграфические латинские буквы Л,..., Z, — и константы 2J и Я.
Мы также оставляем за собой право использовать некоторые
специальные символы (например, Card, CardT или Щ &ая обозначения
некоторых конкретных классов. Все эти символы будут определены
нами в дальнейшем.
§1.7. КЛАССЫ МНОЖЕСТВ
33
В связи с введением классов нам понадобятся еще несколько
соглашений /\ая записи формул, а именно:
z е {х\ <p(x)}:=(p(z),
{х\ <р(х)} = {х\ ф(х)} :=Vx (р(х) ^ Ф(х),
А = {х\ (р(х)} :=Vx х ^ А ^ <р(х),
{х\ <р(х)} = А := Ух (р(х) <^> х е А,
где переменная А не входит в формулу <р(х). Эти соглашения
позволяют нам распространять стандартные теоретико-множественные
отношения е и = на классы, правда, с некоторыми
ограничениями. Так, мы никогда не можем использовать запись {х\ (р(х)} е X,
поскольку в общем случае класс не является множеством; мы
никогда не можем ставить символ класса под квантор или в качестве
аргумента формулы, поскольку все эти подстановки возможны лишь
j\ah множеств.
Ранее, когда мы использовали во введении терм {х\ <р(х)}, мы не
определяли j\ah него никаких правил, находясь в рамках наивной
теории множеств, и считали его как обозначение множества. Однако
с появлением аксиом ZF нам пришлось отказаться от использования
этого терма в общем виде, а пользоваться только его частным
случаем {х\ х е Ал<р(х)}. Теперь же мы вновь намерены использовать это
обозначение, но уже не ^^ая множеств, а ^^ая классов, а
приведенные правила, собственно, показывают, что все наши рассуждения,
содержащие понятие класса, мы можем без труда формализовать в
ZF.
Другими словами, классы нам потребовались /\ая упрощения
записи утверждений на языке ZF, точно так же, как сокращения
формул типа х С у или х ф у. Если, например, у нас имеется достаточно
большая формула (р(х) \—{х е А) Л (х е В) V (х е С) и т.п., то мы
можем определить класс %\—{х\ (р(х)}, и в дальнейшем вместо этой
длинной формулы писать коротко х е ЗС.
Рассмотрим примеры собственно классов. Пусть 9J:={x| х = х}.
Класс 9J — это класс всех множеств, и множеством он быть не
может, т. к., предполагая что 9J есть множество, мы придем в
противоречие с теоремой 1.3, из которой следует, что 9J ^ 9J. Аналогично
класс Расселла {х\ х ф х} не является множеством по той простой
причине, что он совпадает с 9J в силу аксиомы регулярности S7.
Нетривиальным примером собственно класса является класс всех
транзитивных множеств. Пусть Т:={х| х — транзитивно}.
Предположим, что 7 является множеством. Тогда существует множество
О Н. И. Казимиров
34
ГЛАВА 1. ОСНОВАНИЕ
р = UT. Покажем, что множество S(p) транзитивно. Действительно,
из того, что х е S(p) следует хер или х — р. Если х е р, то
существует транзитивное множество t такое, что х & t, тогда х С £,
откуда х С р и, следовательно, х С 5(р). Если же х = р, то очевидно,
что х С S(p). Итак, S(p) транзитивно, поэтому S(p) е Т и £(р) С р.
Противоречие. Таким образом, Т не является множеством.
Подклассом класса X называется любой такой класс £, что ^^ая
каждого множества х е £ имеем х е X. Если подкласс £
является множеством, то его мы называем подмножеством класса ЗС Для
классов, как и для множеств, мы используем все сокращения /\ая
формул, определенные нами во введении, и почти все сокращения
^^ая термов, а именно: X П £, X U £, ЗС \ £, U3C, Ехр(ЗС), причем под
классом Ехр(ЗС) мы понимаем класс всех подмножеств класса X.
Понятия последующего класса и пары классов уже
некорректны в случае собственно классов, ибо элементами класса могут быть
множества и только множества.
На классах мы также можем рассматривать отношения как
классы пар множеств, в частности мы можем ввести в рассмотрение
прямое произведение классов. Поэтому в дальнейшем (см. главу
2), когда мы будем доказывать, например, вполне упорядочение
некоторого класса, мы фактически будем проверять следующие
свойства. Пусть X — класс, и на этом классе задано отношение
31 :={(ж, у) : ср(х, у)}. Тогда отношение 31 называется вполне
упорядочением, если:
1) Ух е X : ~}х31х (антирефлексивность);
2) Ух, y,z е X : х31у Л у*Лг —» x3lz (транзитивность);
3) Ух, у е X : х = yV xOly V yOlx (связность);
4) /\ая любого подмножества А С ЗСГ А ф 0, существует такой х е А,
что для любого у Е А имеем x3fy или х — у.
Аналогичные определения можно привести и для всех остальных
видов отношений, какие мы рассматривали в § 1.4.
Под отображением J : X —» £ класса ЗС в класс £ мы понимаем
класс jF С ЗСх£ такой, что для каждого х е X существует у е £ такой,
что (х, у) е Э^ и всякий раз из (х, у), (х, z) е ? следует у = z.
Понятие отображения — это естественное представление понятий
функции и определяемого отображения в терминах теории множеств с
классами. Действительно, если формула (р(х, у) определяет [х \-> у) —
отображение, то класс J — {(х, у)\ ср(х, у)} является отображением из
класса X = {х\ Зу (р(х,у)} в класс £ = {у\ Зх ср(х,у)}. Если же / есть
функция из А в В, то полагая X = А, £ = В, J — f, получаем, что jF
есть отображение из X в £.
§1.7. КЛАССЫ МНОЖЕСТВ
35
Для отображения jF формулы &(х) = у или у = Э^(х), как и в случае
функции, означают попросту, что (х, у) е Эг.
Для отображений так же, как и для функций, вводятся понятия
инъективного, сюръективного и биективного отображения,
суперпозиции отображений, обратного отображения, образа и прообраза,
сужения отображения на подкласс или на подмножество.
Покажем одно фундаментальное свойство, которое мы будем
впоследствии неоднократно использовать при доказательстве теорем.
Пусть X — некоторый класс, Y — множество.
Теорема 1.17. Если J есть инъективное отображение класса X в
множество Y', то класс X есть множество.
Доказательство. Выделим в множестве Y подмножество Z как
область значений jF, т.е. положим Z — {у е Y\ Зх е X : &(х) =
= у}. Тогда отображение jF : X —» Z биективно и, следовательно,
обратимо. Отображение Эг_1 : Z —» JC, обратное к jF, сюръективно,
откуда в силу аксиомы подстановки S8 получаем, что класс X есть
множество. □
На этом мы завершаем рассмотрение оснований теории
множеств. Подведем некоторые итоги наших построений. В этой
главе мы попытались построить формальную аксиоматическую теорию
множеств, в аксиомах которой мы зафиксировали все основные и
вполне очевидные требования к множествам. Придерживаясь
строгих правил языка ZF, мы сумели определить в рамках теории
множеств практически все основные математические понятия такие,
как отношение, функция, отображение, прямое произведение
множеств, натуральные числа и прочее. Мы ввели в рассмотрение
понятие класса, с помощью которого можно довольно компактно и
интуитивно понятно записывать многие громоздкие формулы
языка ZF.
Что дает нам такой подход? Во-первых, точность всех выводов
теории и отсутствие всех известных парадоксов теории множеств.
Во-вторых, объемность теории в том смысле, что в теорию
множеств Цермело—Френкеля можно погрузить практически все
математические рассуждения. В-третьих, за долгие годы тщательных
исследований математикам не удалось обнаружить в ZF ни одного
противоречия, что вселяет в нас большую уверенность в
непротиворечивости этой теории.
3*
Глава 2
ОРДИНАЛЫ
§2Л Определение и свойства ординалов
Одно из самых часто используемых в теории множеств понятий
— это порядок, илиг точнее, полный порядок элементов
некоторого множества. Представим себе множество некоторых элементов,
отвлекаясь от их природы:
О О О О ••• О О-
0 12 3 гс-2 гс-1
Натуральные числа, проставленные снизу, отмечают порядковый
номер каждого элемента, устанавливая тем самым взаимно
однозначное соответствие между натуральным числом п и нашим
множеством. Если мы изменим порядок элементов, отвлекаясь опять же от
их природы, то после перенумерации вновь получим ту же картину.
Действительно, j\ah конечных множеств при перестановке
элементов их абстрактный порядок (или порядковый тип) не меняется. Но
посмотрим, как обстоит дело с бесконечными множествами.
Возьмем, к примеру, последовательность чисел 1 — 1/п, упорядоченных
по возрастанию, т. е. обычным способом, присвоив им в качестве
номеров натуральные числа:
О О ОО ••• •
0 12 3
Теперь перенесем нулевой элемент в «конец» этого ряда, и после
перенумерации с нуля получим
о о о... О-
0 12 из
Последнему элементу в качестве «номера» мы присвоили и. Здесь
уже имеется последний элемент, хотя количество элементов не из-
§2.1. ОПРЕДЕЛЕНИЕ И СВОЙСТВА ОРДИНАЛОВ
37
менялось, т. е. между тем и другим множеством можно
установить взаимно однозначное соответствие. Чтобы быть более
точными, вместо первого примера последовательности {1 — 1/п}™=1
возьмем множество и с обычным порядком, а вместо второго примера
упорядоченного множества рассмотрим множество S(u) = и U {и},
где отношение принадлежности устанавливает вполне
упорядочение, причем и в этом множестве является наибольшим элементом.
Биекцией между этими множествами будет, например,
t( \ \п + 1, пей,
f(n) = < / : S(u) о и.
10, п — и,
Продолжая далее процесс «переброски» элементов из «начала» в
«конец» в нашем примере, мы будем получать все новые и новые
порядковые конструкции или, как мы далее будем говорить,
порядковые типы.
Эта особенность бесконечных множеств была впервые
подмечена Кантором (см. [1]) в его трудах по теории множеств. Тогда он
ввел понятие порядкового типа вполне упорядоченного множества
как некоего объекта, получаемого путем абстрагирования от
природы элементов этого множества. Мы же воспользуемся методом фон
Неймана /\ая определения порядковых типов, который
заключается в построении специальных полностью упорядоченных множеств,
называемых нами ординалами и обладающих весьма
привлекательными свойствами, причем /\ая каждого полностью упорядоченного
множества найдется и только один ординал, являющийся его
порядковым типом.
Определение 2.1. Ординалом (или порядковым числом) называется
всякое множество X, обладающее свойствами:
X транзитивно и любой элемент х е X транзитивен.
Для обозначения ординалов мы будем использовать, как правило,
греческие буквы, поэтому условимся всюду в дальнейшем любую
греческую букву, кроме (р и ф, понимать как обозначение
ординала, если не оговорено противное. Через Ord обозначим класс всех
ординалов. Рассмотрим теперь основные свойства ординалов.
/2.1. Пустое множество 0 есть ординал.
В дальнейшем, когда 0 мы будем использовать как ординал, мы
будем называть его нулевым ординалом, обозначая его 0.
/ 2.2. Каждый элемент ординала есть ординал.
38
ГЛАВА 2. ОРДИНАЛЫ
Доказательство. Пусть х е а. Тогда х транзитивен. В силу
транзитивности а получим х С а, откуда и каждый элемент у е х, будучи
элементом а, также транзитивен. □
/ 2.3. Любое натуральное число п е и, а также множество и
являются ординалами, что следует из теоремы 1.12 и предыдущего
свойства.
/ 2.4. Если а — ненулевой ординал, то 0 е а.
Доказательство. Из аксиомы регулярности (S7) следует, что
существует х е а такой, что х П а = 0. Так как х С а, то х П а = х, откуда
х = 0 и, следовательно, 0 е а. □
/ 2.5. Если а — ординал, то 5(a) — ординал.
Доказательство. Пусть х е £(а)г тогда либо х G а, либо х = а. В
любом случае х С а в силу транзитивности а. Кроме того, /\ая любого
х е 5(a) множество х транзитивно, т. к. х е а или х = а. П
Ранее мы уже использовали принцип индукции для натуральных
чисел, т.е. на множестве и. Теперь мы докажем более общий
принцип /\ая всех ординалов.
Теорема 2.1. Пусть (р(х) — формула языка ZF. Если для любого а из
того, что У/3 е а : (р(/3), следует (р(а), то тогда для любого а имеем
<р(а).
Доказательство. Предположим, существует а такой, что ](р(а).
Рассмотрим множество X = {/3 е а\ ~|<р (/?)}. Если это множество
пусто, то У/3 е а : <р(/3)г откуда <р(а). Противоречие.
Пусть Х/0. Тогда по аксиоме регулярности S7 существует /3 е X
такой, что /3 П X = 0. Для ординала /3 верно следующее.
а) /3 С а, т.к. /3 е а и а транзитивен.
б) /\ая любого 7 € /3 имеем ^(7)г т. к. /3 П X = 0.
Но тогда по условию теоремы получаем <р(/3). Противоречие. П
Доказанную теорему называют обычно трансфинитной
индукцией или просто индукцией. Индукция используется достаточно часто
при доказательстве теоретико-множественных фактов и других
теорем, лежащих в основаниях математики.
Замечание 1. Если у нас имеется некоторый непустой класс
ординалов X (т. е. X С Ord), а формула (р, указанная в теореме имеет вид
х е X —» ф(х), то мы говорим об индукции на классе ординалов. В
§2.1. ОПРЕДЕЛЕНИЕ И СВОЙСТВА ОРДИНАЛОВ
39
этом случае для проверки условий теоремы, очевидно, достаточно
брать ординалы а и /3 только из класса X. Так мы поступаем,
например, при доказательстве теоремы 3.19, используя индукцию на
классе бесконечных кардиналов.
Проверка условия теоремы при а = 0 (а в случае индукции по
классу ординалов X при а = minX) обычно осуществляется
отдельно и называется базой индукции. Проверим, что условие
теоремы при а = 0 равносильно формуле ср(0). 1 По условию мы имеем
(У/3 GO: (р(/3)) —>> (р(0). Воспользуемся нашими определениями
сокращенной записи формул (см. введение), и перепишем условие иначе:
(У/3 : /3 е 0 —» (р(/3)) —» <р(0). Импликация /3 е 0 —» <р(/3) истинна
в силу ложности посылки при любом ординале /3, поэтому
исходная формула равносильна следующей ф —» <р(0), где ^ обозначает
какую-либо истинную формулу, например, /3^0. Ну а тогда наша
исходная формула равносильна ^(0), что вытекает уже из свойств
импликации.
Заметим, что индукцию можно проводить не только на классе
ординалов, но также на любом его подклассе или подмножестве, а
также, в более общем виде, на любом вполне упорядоченном классе,
только вместо ординала 0 надо брать минимум этого класса, а вместо
ординалов брать исключительно элементы данного класса.
Докажем теперь одно из основных, на наш взгляд, свойств
ординалов.
Теорема 2.2. Класс Ord вполне упорядочен отношением
принадлежности.
Доказательство. Антирефлексивность е следует из аксиомы
регулярности, и была уже нами не раз доказана.
Транзитивность е на ординалах вытекает из транзитивности
ординалов.
Для доказательства связности е на ординалах рассмотрим
формулу (р(а, /3) := а <Е /3 V а = /3 V /3 <Е а.
Нам необходимо показать УаУ/3 (р(а, /3). Для этого докажем
истинность формулы ф(а) \—У/3 (р(а,/3) индукцией по а. Предположим, что
для любого j е а истинно '0(7). Теперь докажем индукцией по /3
истинность (р(а,/3) (при фиксированном а). Предположим, что (p(a,j)
при любом j £ /3. Итак, фактически у нас имеется следующее пред-
1 Часто в книгах по теории множеств (например, [13]) в условие теоремы об
индукции добавляют требование (р(0), которое, вообще говоря, излишне.
40
ГЛАВА 2. ОРДИНАЛЫ
положение: (V7 € ol : (p(j,/3)) Л (V7 е /3 : <р(а, 7))? из которого надо
вывести ср(а,/3).
Если а = /3, то все очевидно. Пусть а ф /3. Тогда а \ /3 ф 0 или
^\а / 0. Рассмотрим первый вариант. Пусть j & а\ /3. Тогда из
предположения получаем: (p(j, /3), т. е. j е /3 V 7 = /3 V /3 е 7- Случай
7^/3 исключается по выбору нашего j. Таким образом, j = /3V/3 е 7-
Из транзитивности а и того, что j £ а, получаем /3 е <% т. е. <р(а, /3).
Рассмотрим второй вариант. Пусть j е /3 \ а. Из предположения
получаем тогда <р(а, 7)г причем случай j е а исключается. Поэтому
имеем а е 7 v ^ = 7- Так или иначе, из 7 € /3 в силу транзитивности
/3 получим а е /3, т. е. <р(а, /3).
Тем самым мы доказали V/3 (р(а, /3). Теперь индукцией по а
заключаем, что VaV/3 (р(а,/3).
Итак, связность £ на ординалах показана. Осталось показать, что в
любом непустом множестве ординалов существует минимум. Пусть
В — непустое множество ординалов. По аксиоме регулярности
существует /30 е В такой, что /30 П В = 0. Тогда /\ая любого /3 £ Б
получаем либо /30 = /3, либо /30 е /3, т.к. вариант /3 е /30г очевидно,
исключается. Итак, /30 = mm В. □
/ 2.6. Из только что доказанной теоремы следует, что каждый
ординал вполне упорядочен отношением принадлежности.
В дальнейшем, когда мы будем говорить о принадлежности как
об отношении порядка на ординалах, вместо символа е мы будем
писать <, а формула а > /3 будет равносильна по определению
формуле /3 < а. Как обычно, рассматриваются и равносильные
формулы а ^ /3 и /3 ^ а нестрогого неравенства. В соответствии с
определениями из §1.4 пара (а, <), где а — ординал, < — отношение
принадлежности, называется вполне упорядоченным множеством.
Условимся /\ая ординалов вместо пары (а, <) писать просто сам
ординал а, относя к нему понятие вполне упорядоченного множества.
/ 2.7. а < /3 <^> а С /3(а ^ /3 <^> а С /3).
Доказательство. Если а < /3, тоаС/Зв силу транзитивности /3.
Пусть а с /3. Предположим, что ] (а < /3). Тогда /3 ^ а, откуда /3 С а
в силу транзитивности а. Противоречие. □
/ 2.8. Если А — множество ординалов, то в классе Ord существует
sup А и он равен и А.
§2.1. ОПРЕДЕЛЕНИЕ И СВОЙСТВА ОРДИНАЛОВ
41
Доказательство. Пусть х — UA Множество х есть ординал, т. к. для
каждого z е х существует а е А такой, что z е а, поэтому, во-первых,
z транзитивно, а во-вторых, z С а С х, откуда х транзитивно.
Покажем, что х = sup А.
а) Для любого а е А имеем а С х, откуда по свойству 2.7 а ^ х,
т. е. х является верхней гранью /\ая А.
б) Пусть 7 — верхняя грань /\ая А. Так как /\ая любого а е А верно
или а ^ 7г то ЛАЯ любого а е А по свойству 2.7 получим а^, откуда
х С 7г т. е. по свойству 2.7 или х ^ j.
Итак, х — точная верхняя грань А. □
/ 2.9. Не существует наибольшего ординала.
Доказательство. Если а = maxOrd, то S(a) С а. Противоречие. П
/ 2.10. Класс Ord не является множеством.
Доказательство. Если Ord — множество, то и Ord есть ординал по
свойству 2.8, причем, очевидно, UOrd = max Ord, что противоречит
свойству 2.9. □
Определим два основных типа ординалов.
Определение 2.2. Ординал а называется последующим, если
существует множество х такое, что а = S(x). В противном случае ординал
а называется предельным, если только а > 0.
Несложно показать, что класс предельных ординалов и класс
последующих ординалов не ограничены в Ord, т. е. не являются
множествами.
/ 2.11. а есть последующий ординал тогда и только тогда, когда
sup а < а.
Доказательство. Во-первых, ссылаясь на свойство 2.8, заметим, что
^^ая любого ненулевого ординала а
sup а = VJa — (J я,
причем sup а есть ординал.
Во-вторых, покажем, что утверждение а < sup а ложно при любом
ненулевом ординале а. Пользуясь свойством 2.7, получим
sup а = \J хС [J х С а. (2.1)
х£а хСа
42
ГЛАВА 2. ОРДИНАЛЫ
Итакг пусть а есть последующий ординал. Тогда существует
ординал /3, такой, что а = S(/3).
Тогда sup а = Ua = (U/3) U /3 = /3 по (2.1). Следовательно, sup а < а.
Обратно, пусть sup а < а. Рассмотрим ординал S^supa). Имеем
S(supa) = (Ua) U {Ua} С а (2.2)
по неравенству (2.1) и по предположению.
По определению sup а &ая любого /3 < а: /3 < (sup a) U {sup а} =
= £(supa).
Поэтому
а С £(supa). (2.3)
Окончательно из (2.2) и (2.3) имеем а = £(supa)r то есть а —
последующий ординал. □
Из доказательства этого свойства вытекают следующие два
критерия последующего и предельного ординалов.
/2.12. а есть последующий ординал тогда и только тогда, когда а =
= £(supa); а есть предельный ординал тогда и только тогда, когда
а = sup а.
§ 2,2 Рекурсивные определения.
Порядковые типы
Одна из часто встречающихся в математике конструкций —
рекурсия. Например, выбрав определенным образом вещественную
функцию / и число а, мы можем рассматривать последовательность
{xn}%Loi определяемую равенствами: х0 = a, xn+i = f(xn), пей.
Последнее равенство принято называть рекурсивным. Вообще, всякая
рекурсия подразумевает построение последовательности путем
указания зависимости элементов данной последовательности от
элементов с меньшими номерами. При этом (в общем случае) «номера»
не обязаны быть исключительно натуральными числами, они могут
быть и бесконечными ординалами.
Пусть X — класс, в котором мы хотим построить (рекурсивно)
некоторую трансфинитную последовательность (т. е. отображение
из Ord в X). Пусть также задано отображение J : Ехр(ЗС) —» X. При
помощи этого отображения мы и определим переход в рекурсии от
§2.2. РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ. ПОРЯДКОВЫЕ ТИПЫ 43
элементов с номерами меньше а, где а — ординал, к элементу с
номером а следующим образом:
ха = 3({хр\ /3 < а}), х0 = ^(0).
Корректно ли такое определение? Ответ на этот вопрос дает
следующая
Теорема 2.3. (О рекурсивных определениях).
Пусть X есть класс и задано отображение J : Ехр(ЗС) —» X. Тогда
можно определить отображение S : Ord —» X такое, что
VA е Ord : 3(A) = F({S((5)| S < А}). (2.4)
Доказательство. Для того, чтобы доказать теорему, нам
необходимо сконструировать такую формулу (р, которая определяла бы
отображение из Ord в X, удовлетворяющее (2.4)- Для этого мы сначала
рассмотрим формулу
ф(К) := За е Ord : (h : а -> X) Л У/3 < а : ОД = Э^Л/З).
Заметим, что всякое отображение h : а —>> X является функцией
по аксиоме подстановки, поэтому формула ф построена корректно.
Полагая далее *К — {h\ ф{Н)}, мы видим, что класс *К не пуст, т.к.,
например, функция h — {(0, 9^0))} является элементом *К. Более того,
класс *К линейно упорядочен отношением с. Действительно, пусть
h, N е *К и а — dom(h), а' — dom(h'). Для определенности положим,
что а ^ а'. Легко установить (по индукции), что h!\a — h, откуда
следует h С h!.
Обозначим далее S = U JC. Поскольку класс *К линейно упорядочен
отношением с и состоит из функций, то S является отображением.
Заметим также, что отображение S определено /\ая всех ординалов.
Именно, если предположить, что а — наименьший из ординалов,
/\ая которых S не определено, то h = S € <К- Полагая далее Ы —
— hu{(a, &(ha))}, замечаем, что Ы е *К, ибо Ы удовлетворяет формуле
ф. Таким образом, S С h'. Противоречие.
Теперь определим формулу ср(а,х) так:
(р(а, х) \— 3h е *К : /i(a) = х.
Нетрудно проверить, что S = {(а, х)| <р(а, х)}. Итак, формула ср(а,х)
определяет отображение S : Ord —>> ЗСГ причем для каждого ординала
а имеем 3(a) = Эг(3^)г поскольку для каждого а существует функция
h е 'К такая, что S|s(a) =Ли /i(a) = &(ha). П
44
ГЛАВА 2. ОРДИНАЛЫ
Теперь мы видим, что наш пример с вещественной
последовательностью {хп}, приведенный в начале параграфа, есть частный
случай трансфинитной рекурсии. Действительно, рассмотрим класс
X = Ж х и. Построим jF : Ехр(ЗС) —» X так: &ая каждого подмножества
A CRxu, являющегося функцией А : S(n) —» Ж при некотором пей,
положим 3(A) = (f(A(n)), S(n)), &ая всех прочих A CR х и положим
3(A) = (а, 0). Здесь функция / и число а те, которые были упомянуты
в начале параграфа. Теперь нетрудно проверить, что отображение
S : Ord —» ЗСГ существование которого доказано в теореме, обладает
следующими свойствами:
9(п) = (хп, п) при п < и, 9(a) = (а, 0) при а ^ и.
Построение рекурсивных определений (точнее, рекурсивно
определяемых отображений) — одна из самых часто возникающих задач
не только в теории множеств, но также в арифметике, топологии и
т.д. Чаще всего эту теорему применяют ко множествам, т.е. в
случае, когда класс X является множеством, но иногда (см., например,
главу 3, теорему 3.8, где X = Card^) приходится использовать и
более общий ее вариант, который был только что доказан. В текущей
главе мы еще неоднократно возвратимся к данной теореме.
Определение 2.3. Пусть (X, <х) — вполне упорядоченное
множество. Если между X и некоторым ординалом А существует
порядковый изоморфизм, т.е. такая биекция f : А —> X, что при любых
а < /3 < А имеем f(a) <х f(ft), то ординал А называется порядковым
типом (X, <х)г и /\ая него в этом случае используется обозначение
|(Х,<х)|илиОЫ(Х,<х).
Поскольку 0x0 = 0, то любое отношение на 0 совпадает с 0.
Поэтому по определению также положим |(0, 0)| = 0.
Теорема 2.4. Любое вполне упорядоченное множество имеет
единственный порядковый тип.
Доказательство. Пусть непустое множество X вполне упорядочено
отношением <х. Построим функцию F : Ехр(Х) ч!по
следующему правилу: /\ая любого собственного подмножества А с X положим
F(A) = minX \ А, в случае А — Х положим F(A) = minX.
По теореме о рекурсивных определениях существует
отображение S из Ord в X такое, что 9(a) = F(9a) при любом а е Ord.2
2Напомним, что символ За обозначает образ ординала а относительно
отображения д.
§2.2. РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ. ПОРЯДКОВЫЕ ТИПЫ 45
I Покажем существование порядкового типа X.
Пусть а е Ord и S«Cl. Пусть также /3 < а.
1а) Покажем, что в этом случае S(/3) < S(a).
Действительно, S/3 С За, откуда Х\3<^ С X\S/3f откуда S(/3) ^ S(a)'
а поскольку S(/3) е 3<% то S(/3) ^ 3(a)' откуда S(/3) < 3(a).
16) Покажем, что существует ординал А такой, что ЗА = X.
В самом деле, если предположить, что это не верно, то из 1а)
следует, что S есть инъективное отображение из Ord в X, откуда по
теореме 1.17 получаем, что Ord будет множеством. Противоречие.
Через А обозначим наименьший из таких ординалов.
1в) Покажем, что S действует инъективно с А в X.
Действительно, по определению А при любом а < А имеем $а С
X, откуда в силу 1а) &ая любых /3 < а < А получим S(/3) < S(<^)r т.е.
S|a — инъекция.
1г) Из 1а), 16) и 1в) следует, что S|a осуществляет порядковый
изоморфизм ординала А и множества X. Итак, А = |(Х, <х)\-
II Покажем, что порядковый тип вполне упорядоченного
множества определяется единственным образом.
Пусть ординалы А ^ Г являются порядковыми типами (Х,<х)-
Легко показать, что в этом случае существует порядковый
изоморфизм / : А —>- Г.
Предположим, что / не является тождественной функцией, и
через а обозначим наименьший из таких ординалов, /\ая которых
f(a) ф а. Если предположить, что f(a) < а, то существует 5 < а
такое, что f(5) = f(a), что нарушает инъективность /. Итак, f(a) > а.
Тогда /\ая любого 5 < а имеем f(5) < а, а /\ая любого 5 ^ а, 5 е А,
получим f(5) > а.
Итак, а £ /А = Г, что противоречит тому, что а < А < Г, т. е. a G Г.
Следовательно, / есть тождественное отображение, откуда А = Г, и
теорема доказана. □
О фундированности классов.
В § 1.7 нами было введено понятие класса как определяемой
совокупности множеств. Классами, например, являются 9J (класс всех
множеств) и Ord (класс всех ординалов). Отметим, что аксиома
регулярности (фундирования) S7, которая наводит достаточно строгий
порядок на множествах, была нами сформулирована /\ая множеств.
Поэтому возникает вопрос: насколько справедливо подобное
утверждение ^^ая классов, упорядочены ли они столь же строго как
множества?
46
ГЛАВА 2. ОРДИНАЛЫ
Ответ на этот вопрос содержится в следующей теореме.
Теорема 2.5. Если X — непустой класс, то существует множество
X е X такое, что X П X = 0.
Доказательство. Пусть X — непустой класс. Предположим, что &ая
любого X е X имеем X П X ф 0. Для доказательства теоремы
построим специальную последовательность множеств, которая сведет
фундированность классов к фундированности множеств.
Так как X ф 0Г то существует А0 е X, тогда множество А0 П X
непусто. Построим отображение J из класса Exp(Exp(JC)) в класс
Ехр(ЗС) по правилу: /\ая любого непустого множества А С Ехр(ЗС)
положим
ПА)= UU(*n3a
аеАхеа
&ая пустого множества: jF(0) = А0 П X.
По теореме о рекурсивных определениях существует
отображение S : Ord —» Ехр(ЗС) такое, что ^^ая каждого ординала а имеем
2(a) = $($а). В силу нашего предположения о нефундированности
класса X легко показать, что при любом а е Ord множество 2(a)
непусто.
Рассмотрим сужение отображения S на множество и. По
аксиоме подстановки класс {S(^)| пей} есть множество. Обозначим
через Хп множество $(п) при каждом пей. Тогда X = U Хп есть
множество по аксиоме объединения, кроме того, X СХ.
Для произвольно выбранного х е X существует п такое, что
х е Хп. По нашему предположению х П X ф Ф. Кроме того, легко
проверить, что х П X С Xn+i, т.е. хПК С I, откуда х П ЗС С х П X,
откуда х П X ф ®. Получено противоречие с аксиомой регулярности
/\ая множества X. □
§ 2,3 Арифметика ординалов
Когда мы даем определение некоторому объекту (множеству),
называя его числом, то это накладывает определенные обязательства,
ибо над числами принято осуществлять как минимум две операции:
сложение и умножение. Следуя данной традиции, мы вводим
вспомогательный инструментарий на классе ординалов, который будет
рассмотрен в данном параграфе и который, опять же по традиции,
будет назван арифметикой ординалов.
§2.3. АРИФМЕТИКА ОРДИНАЛОВ
47
Пусть у нас имеется ненулевой ординал Аг индексирующий
множество ординалов {as}seA- На всех ординалах мы рассматриваем
одно и то же отношение полного упорядочения — отношение
принадлежности. Тогда мы можем определить каноническую сумму
ординалов as по ординалу А такг как мы определяли каноническую
сумму вполне упорядоченных множеств по вполне
упорядоченному множеству в § 1.6. Из теоремы 1.14 вытекает, что каноническая
сумма ординалов as по ординалу А есть вполне упорядоченное
множество. А это означает, что у канонической суммы ординалов
существует единственный порядковый типг который тоже является
ординалом.
Определение 2.4. Суммой ординалов as в порядке А называется
порядковый тип их канонической суммы по ординалу А. Сумма
ординалов as в порядке А обозначается символом Y1 ®5-
В том случае, когда ординал А является натуральным числом или
ординалом и, &ая обозначения суммы ординалов мы допускаем
использование стандартных математических символов, например,
оо
Для наглядного представления суммы ординалов можно
воспользоваться картинкой:
[о о о ...)[о о о ...)[о о о ...)...
ао а\ «2
При сложении ординалы выстраиваются «друг за другом» и
образуют новый порядковый тип. Нетрудно проверить, что в случае,
когда а0 и а\ являются натуральными числами, их сумма, как сумма
ординалов, совпадает с обычной суммой натуральных чисел.
Перейдем к определению произведения ординалов. Рассмотрим
множество ординалов {as}seA- Поскольку все ординалы вполне
упорядочены, то мы можем определить каноническое произведение
ординалов as по ординалу А. В соответствии с теоремой 1.15 это
произведение будет линейно упорядоченным множеством. Для его вполне
упорядоченности приходится предполагать, что ординал А есть
натуральное число. Поэтому положим далее А = п. Тогда по теореме
1.16 каноническое произведение ординалов as по ординалу п будет
вполне упорядоченным множеством, j\ah которого существует
единственный порядковый тип, являющийся ординалом.
48
ГЛАВА 2. ОРДИНАЛЫ
Определение 2.5. Произведением ординалов а$ в порядке п
называется порядковый тип их канонического произведения по ординалу
п. Произведение ординалов as в порядке п обозначается символом
П <%5i либо одним из следующих стандартных символов:
г=0
Здесь мы определили пока только конечное произведение
ординалов. В дальнейшем мы определим и бесконечные произведения,
пользуясь теоремой о рекурсивных определениях.
Произведение двух ординалов a0c*i (при п — 2) можно представить
так:
[[ оц )[ оц )[ оц ) ••• )
ао
При произведении ординалов а0 и а\ ординал ai последовательно
повторяется в том порядке, который диктует ординал а0. Если а0 и
а\ есть натуральные числа, то их произведение совпадает с обычным
произведением натуральных чисел.
Без доказательства приведем простейшие свойства суммы и
конечного произведения ординалов.3
/ 2.13. Сложение вообще говоря не коммутативно, т.к., например,
и + 1 = S(u), а 1 + и = и.
/ 2.14. Сложение ассоциативно: (а + /3) + j = а + (/3 + j).
/ 2.15. Нулевой ординал есть нейтральный элемент по сложению:
а + О = 0 + а — а.
/ 2.16. Действует закон сокращения слева: если а + /3 = а + j, то
Р = ъ
/ 2.17. Закон сокращения справа не действует. Например, 1 + и =
= 2 + cj, но 1 ф 2.
/ 2.18. Произведение ординалов вообще говоря не коммутативно.
Так, например, и • 2 = и, но 2 • и ф и.
33аметимг что для формальной проверки равенства порядковых типов двух
множеств, на которой основаны доказательства этих свойств, достаточно
установить порядковый изоморфизм между этими множествами, который как
правило очевиден из структуры множества, определяющего результат сложения или
умножения ординалов, интуитивно же эти свойства легко установить, пользуясь
графическим представлением суммы и произведения,.
§2.3. АРИФМЕТИКА ОРДИНАЛОВ
49
/ 2.19. Произведение ассоциативно: (a/3)j = a(/3j).
/ 2.20. 1 есть нейтральный элемент по умножению: 1 • а = а • 1 = а.
/ 2.21. Действует правый дистрибутивный закон: (а + /3)7 = aj + /3j.
/ 2.22. Левый дистрибутивный закон не действует. Такг например,
2{и + 1) = (ш + 1) + (ш + 1) = (ш + (1 + ш)) + 1 = (ш + и) + 1, но 2и + 2 =
= (о; + о;) + 2.
/ 2.23. Монотонность: если а > 0, то /3 ^ а/3 и /3 ^ /За.
/ 2.24. Правая дистрибутивность в общем виде:
Если в этом равенстве положить а^ = 1 при любом 5 G А, то легко
доказать следующее утверждение.
Если &ая любого 5 е А имеем од = /Зг то J] а^ = Д • /3.
Для определения произвольного произведения ординалов нам
потребуется теорема о рекурсивных определениях 2.3 иг кроме
того, несколько новых обозначений. Во-первых, через Ordi обозначим
класс ненулевых ординалов. Во-вторых, /\ая каждой упорядоченной
пары (а, Ъ) через сох(а, Ъ) будем обозначать левую ее координату, а
через со2(а, Ъ) обозначим правую ее координату. Наконец в-третьих,
j\ah всякого подмножества В в прямом произведении классов % х L
через ttiB обозначим множество {cois| s е В}, а через 7г2Б
обозначим множество {co2s| s е В}. ttiB и тт2В называются соответственно
левой и правой проекциями множества В.
Теорема 2.6. Для любого отображения 3 : Ord —» Ordi существует
отображение 7 : Ord —» Ordi такое, что:
1) 3>(0) = 1;
2) P(a + 1) = Р(а) •%);
3) если а — предельный, то 7(a) = sup ^(7).
Доказательство. Построим отображение J : Exp(Ordi х Ordi) —»
Ordi х Ordi по правилу: рф51 множества В С Ordi х Ordi положим:
[(1,0), Б = 0;
Э^-В) = < (sup7Ti^, SUp7T25), SUp7T25 0 7Г2Б;
[(sup7Ti^ • J(sup7T25), SUp7T2i? + 1), SUp7T2i? £ 7Г2Б.
4 Н. И. Казимиров
50
ГЛАВА 2. ОРДИНАЛЫ
Тогда по теореме о рекурсивных определениях существует
отображение S из Ord в Ordi х Ordi такое, что
3(а) = Я(9а), aeOrd.
Теперь введем отображение 7 : Ord —» Ordi по правилу:
VaG Ord : У (a) = coiS(a).
а) Из определения отображения J видно, что если определен
sup7r2i?r то coi^(B) ^ sup7Ti5. Пусть а < /3. Так как Ъ{р) £ S/?r то
sup7TiS/3 ^ coi S(a)r откуда coi S(/3) = coi ^(3/3) ^ coi S(a)r т. е.
отображение 7 монотонно возрастает.
б) Покажем индукцией, что при любом а е Ord имеем со2 9(a) = а.
Предположим, что оно верно при любом /3 < а.
Тогда 7т29а = а. Из определения J видно, что если sup а е а, то
со2 З^З^) = sup а + 1 = а, если же sup а 0 а, то sup а = а и со2 3^3^) =
= sup а = а. Здесь было использовано свойство 2.12 ординалов из
§2.1.
в) Докажем индукцией, что отображение 7 и есть искомое.
Действительно, 3(0) = 3^0) = (1,0), т.е. У(0) = 1. Пусть при любом j < а
отображение 7 удовлетворяет выводу теоремы. Покажем, что 7
будет искомым и j\ah а.
Пусть а = /3 + 1. Тогда в силу монотонности 7 получим supiriSa =
= 7(/3). В силу пункта б) 7r2Sc^ = ol и, следовательно, sup7r2S<^ = /3 G
7г23^. Тогда по определению отображения jF получим У (а) = У(/3) •
•ад-
Пусть а — предельный ординал. Снова в силу монотонности 7
получим sup7riSc^ = sup 7(7). Из б) следует, что 7r2Sc^ = ol и sup7r2S<^ =
= ol 0 7г23<^. Тогда из определения jF заключаем, что У (а) = sup ^(7).
Итак, 7 является искомым отображением. Теорема доказана. □
Определение 2.6. Отображение 7, зависящее от отображения 3 и
существование которого только что было доказано, называется
продукционным отображением с порядком 3.
Продукционное отображение служит ^^ая построения
произведений ординалов.
Определение 2.7. Пусть есть множество ординалов А,
проиндексированное ординалом А и функция / есть индексация. Если 0 е А, то
0 называется произведением ординалов из А в порядке I.
§2.4. АКСИОМА ВЫБОРА
51
Если 0 0 А, то продолжим индексирующую функцию / (она
действует сюръективно из А на А) до какого-либо отображения 3 из
Ord в Ordi (например, положим 3(a) = 1 при а ^ А). И пусть У
обозначает продукционное отображение с порядком X Тогда ординал
У(А) называется произведением ординалов из А в порядке А.
В том и другом случае произведение обозначается
п ад-
Произведение ненулевых элементов ординала 5(A) в
естественном порядке (т. е. в качестве индексирующего множества берется
порядковый тип множества ненулевых ординалов из 5(A)г которым
является сам ординал 5(A) при А ^ и, и п при А = п) называют
факториалом ординала А и обозначают А!г т.е.
А! = П *
6es(A)\{0}
Легко проверить, что данное понятие факториала /\ая
натурального числа совпадает с обычным понятием факториала.
Замечание 2. В случае, когда А = 0Г т. е. множество А пусто и
проиндексировано нулевым ординалом, по определению получим
П 1(5) = У(0) = 1.
5еА
Более наглядные правила /\ая подсчета произведения ординалов
таковы:
• произведение нуля сомножителей есть 1;
• если известно произведение а сомножителей, то умножив его
на (а + 1)-й сомножитель, получим произведение (а + 1)-го
сомножителя;
• если ординал а — предельный и известны произведения /3
сомножителей j\ah каждого /3 < а, то супремум этих
произведений и есть произведение а сомножителей.
§ 2Л Аксиома выбора
Аксиома выбора, о которой здесь пойдет речь, появилась в связи с
одной не вполне очевидной проблемой. Представим себе, что у нас
4*
52
ГЛАВА 2. ОРДИНАЛЫ
имеется несколько непустых множеств Хь ... ,Хп, и из каждого из
этих множеств необходимо выбрать по одному элементу хь...,хп
(xi е Xi), образовав при этом новое множество С = {хь ... ,хп},
которое называется сечением множества множеств {Хь ..., Хп}. Такой
выбор, казалось быг не представляет сложности. Но что если
имеется бесконечный набор исходных множеств? Как построить
функцию, которая каждому из этих множеств ставила бы в соответствие
его собственный элемент? Как оказалось, это сделать невозможно,
если мы находимся в рамках аксиом ZF! Сформулируем теперь
аксиому выбора (АС):
Для любого множества X, если множество UX не пусто,
существует функция f : X —> UX такая, что при любом
х е X если х ф 0, то f(x) е х, при этом f называют
функцией выбора для множества X.
На вопрос о том, почему АС называют именно аксиомой, отвечают
следующие теоремы метаматематики.
Теорема 2.7. (Курт Гёдель, 1936). Невозможно опровергнуть аксиому
выбора (в символах: Con(ZF)—)► Con(ZF+AC)).
Теорема 2.8. (Поль Кбэн, 1963). Невозможно доказать аксиому
выбора (в символах: Con(ZF)^ Con(ZF+]AC)).
Здесь символ Con обозначает совместность (непротиворечивость)
аксиоматики, указанной в скобках, а выражение ZF+AC обозначает
аксиоматику, полученную добавлением аксиомы выбора АС к
аксиомам ZF, соответственно, ZF+] АС обозначает аксиоматику,
полученную добавлением отрицания аксиомы выбора к аксиомам ZF.
Таким образом, аксиома выбора не зависит от остальных аксиом
теории множеств, и может быть принята как еще одна аксиома
нашей теории. Но поскольку она встречает неодобрение многих
математиков (в особенности с появлением в последнее время не менее
привлекательной аксиомы детерминированности AD,
противоречащей АС), мы не будем рассматривать ее как еще одну аксиому ZF,
а /\ая теории ZF+AC введем специальное обозначение ZFC. Следуя
Куратовскому [9], все утверждения, которые мы будем доказывать
в рамках теории ZFC, мы будем отмечать знаком °, выставляя его
перед ключевым словом утверждения, например, °Теорема.
Кроме аксиомы выбора иногда используют разные ее частные
случаи. Так, например, аксиома счетного выбора АС^ гарантирует
§2.4. АКСИОМА ВЫБОРА
53
существование функции выбора / : X —» UX лишь для счетных
множеств X (т.е. таких множеств X, что low, см. стр. 19). Эта
аксиома хороша темг что она выводима как из АСГ так и из ADr и с ее
помощью нельзя получить все те «парадоксальные» выводы,
которые дает обычная аксиома выбора (некоторые из этих выводов мы
рассмотрим в конце данного параграфа), но тем не менее можно
получить большинство теорем анализа.4
Как оказалось, существует много эквивалентных аксиоме выбора
весьма ценных утверждений (см. [9]). Здесь мы приведем только
два, ибо они понадобятся нам в дальнейшем. Это теорема Цермело
0 полном упорядочении и лемма Цорна.
Теорема 2.9. Следующие утверждения эквивалентны в рамках
теории ZF:
1) АС (аксиома выбора);
2) ZT (теорема Цермело): каждое непустое множество может
быть вполне упорядочено;
3) ZL (лемма Цорна): в любом частично упорядоченном непустом
множестве, если любая его цепь ограничена, имеется
максимальный элемент.
Доказательство. Покажем, что АС —» ZT —» ZL —» АС.
1 Покажем, что из аксиомы выбора вытекает теорема Цермело.
Пусть X — непустое множество, / — функция выбора на
множестве Ехр(Х), а функция F : Ехр(Х) —» X действует по следующему
правилу: для каждого А С X F(A) = f(X\A).
Из теоремы о рекурсивных определениях (см. теорему 2.3)
следует, что существует отображение 9 : Ord —» X такое, что при любом
ординале a 9(a) = F(9a).
la) Пусть 9/3 С X (собственное подмножество) при некотором
ординале /3 и ординал а < /3. Покажем, что в этом случае 9(a) ф 9(/3).
Действительно, 9(/3) = F(9/3) = f(X \ 9/3) и множество X \ 9/3 не
пусто, поэтому 9(/3) 0 9/3. С другой стороны, как легко видеть, 9(a) €
9/3, откуда 9(a) ф9(/3).
16) Покажем, что существует ординал А такой, что 3|д действует
из А на X сюръективно.
4Более подробно об аксиоме выбора и аксиоме детерминированности см. в
[8, 11].
54
ГЛАВА 2. ОРДИНАЛЫ
Допустим, что это не такг т. е. при любом ординале А имеем ЗА С
X. Тогда, как видно из la) г &ая ординалов А7 ф А" получим З(А') ф
= 3(А"). Таким образом, имеется инъекция с класса ординалов в
множество, откуда легко показать (по теореме 1.17), что Ord есть
множество. Противоречие.
Итак, существует ординал А, с которого 3 действует сюръективно
на X. В дальнейшем через А будем обозначать наименьший из таких
ординалов.
1в) Очевидно, А > 0, т. к. X не пусто. Покажем, что функция д =
= 3|д действует из А в X инъективно.
Действительно, пусть а < /3 < А, тогда да и д/3 есть собственные
подмножества X (иначе А не был бы наименьшим из ординалов, с
которых S действует сюръективно на X). Теперь, из 1а) легко
получить, что д{а) Ф д(/3), откуда следует инъективность д.
1г) Из 16) и 1в) заключаем, что функция д есть взаимно
однозначное соответствие между X и А. Полагая теперь /\ая любых a, b е X :
а <х Ъ <^> д~1{а) < 9~1{Ъ), получаем полное упорядочение множества
X, &ая которого Ord(X, <х) = А.
II Покажем, что из теоремы Цермело вытекает лемма Цорна.
Пусть X — частично упорядоченное отношением < непустое
множество, в котором каждая цепь ограничена. Необходимо показать,
что при выполнении теоремы Цермело в X есть максимальный
элемент.
Из теоремы Цермело следует, что на X можно задать отношение
полного порядка. Обозначим это отношение <С. Пусть
QA = {х g Х\ Va е А : а < х} &ая всех А С X.
Рассмотрим функцию F : Ехр(Х) —» X такую, что
где символ min обозначает минимум множества по отношению <С.
Это различие необходимо, т. к. у нас задано два отношения порядка
на одном и том же множестве X.
По теореме о рекурсивных определениях (см. теорему 2.3)
существует отображение 3 из Ord в X такое, что при любом ординале а
имеем Q(a) = F(Qa).
Легко видеть, что при ординалах А7 < А" имеем ЗА7 С ЗА" и,
кроме того, Q^A" ^ ^зл'-
§2.4. АКСИОМА ВЫБОРА
55
Па) Покажем, что если Г1ЗА„ ф 0, то З(Д') < S(A").
Поскольку множество Q^A" не пусто, то из определения F видно,
что 3(Д") G ^дд//. Тогда для любого а е ЗА" имеем а < S(A")r в
частности, З(Д') < S(A").
Нб) Покажем, что существует ординал А такой, что Q$A = 0.
Действительно, предположим, что это не так. Тогда j\ah любых
двух ординалов А7 < А" имеем З(Д') < 3(Д") из Па), т.е. 3 есть
инъективное отображение из Ord в X, откуда по теореме 1.17 Ord
будет множеством. Противоречие.
Пв) Через Д обозначим теперь наименьший из тех ординалов,
существование которых доказано в Пб). Покажем, что ЗА есть цепь в
X. Для этого достаточно показать связность отношения < на
множестве ЗА-
Пусть х, у е ЗД- Тогда существуют ординалы а, /3 е А такие, что
х = 9(a), у = 3(/3)- Возможны только три варианта: а < /3 или а = /3
или /3 < а. В случае а — (3 имеем х — у.
Пусть а < /3. Ясно, что множества Q$a и fiS/5 не пусты, т. к. в
противном случае А не был бы наименьшим из таких ординалов,
^^ая которых Q$A = 0. Тогда из Па) х < у. Аналогично в случае /3 < а
доказывается, что у < х.
Итак, < есть отношение линейного порядка на ЗДг т. е. ЗА — цепь
в X.
Пг) Пусть элемент с е X ограничивает цепь ЗА- Покажем, что с
есть максимальный элемент в X.
Предположим, что существует с' е X такой, что с < с'. Тогда ^я
любого а е ЗА имеем а ^ с < с\ т. е. а < с\ откуда следует, что
с' е ^ддг что противоречит тому, что Q$A = 0.
Итак, в X есть максимальный элемент.
III Покажем теперь, что из леммы Цорна вытекает аксиома
выбора.
Пусть множество X таково, что UX ф ф. ¥[ пусть выполнена лемма
Цорна. Построим /\ая множества X функцию выбора.
Через D обозначим множество всех функций выбора / : А —» UA
таких, что АСХи UA ф 0. Множество D не пусто, ибо /\ая А = {х0},
х0 ф 0, функция выбора существует всегда. Множество D частично
упорядочено отношением с собственного вложения множеств.
Ша) Покажем, что в D каждая цепь ограничена.
Пусть $ — цепь в D. Через /0 обозначим множество U#, а через
А0 обозначим объединение всех таких подмножеств А С X, что в
$ существует функция выбора с областью определения А. Заметим,
что ^^ая всякого х е А0 существует функция / е $ такая, что / :
56
ГЛАВА 2. ОРДИНАЛЫ
А —» UА, х е А. При этом в случае х ф 0 имеем /(х) £ х, а значит,
пара (x,f(x)) есть элемент множества /0. Это означает, что если /0
— функция, то она непременно будет и функцией выбора.
Пусть (х,х'), (х,х") е /о- Из определения /0 видно, что существуют
функции /', f" е # такие, что /'(х) = х', f"(x) = х". Так как $ — цепь,
то мы можем выбрать наибольший из элементов /', /", обозначив
его /. Тогда f(x) = х' и f(x) = х", откуда х' = х". Итак, /0 — функция
выбора ^^ая множества AQ.
Функция /о является элементом D и ограничивает цепь £.
Шб) Найдем теперь функцию выбора ^^ая X.
Как видно из Ша), множество D удовлетворяет условиям леммы
Цорна. Тогда в D существует максимальный элемент. Обозначим
его (£. £ является функцией выбора с областью определения А, где
А С X. Предположим, что существует х0 е X \ А, х0 ф Ф. Тогда
функция £ не определена в точке х0. Пусть у0 е х0. Рассмотрим
множество Си {(х0,2/о)}- Легко показать, что это множество будет
функцией выбора, большей (в смысле вложения), чем (£. Получено
противоречие с максимальностью (£.
Итак, £ есть функция выбора ^^ая X, и теорема доказана
полностью. □
Приложения аксиомы выбора
Здесь мы приведем несколько довольно интересных с нашей
точки зрения следствий из аксиомы выбора, хотя тем самым мы
покажем лишь ничтожную часть той роли, которую играет аксиома в
современной математике.
Прежде всего надо вспомнить, что когда мы рассматривали
прямое произведение множеств в § 1.6, мы не могли гарантировать
существование хотя бы одного элемента в множестве ЦЬХ. Аксиома
с
выбора позволяет это сделать. Действительно, пусть I \ С —> {Lx}xeC
есть индексация, т. е. 1{х) — Ьх &ая любого х е С. Рассмотрим какую-
нибудь функцию выбора / : {Ьх}хеС —>• U Lx. Тогда, очевидно, су-
хес
перпозиция f о I будет элементом прямого произведения ЦЬХ1 т.к.
с
f о / : С —> U Lx и, кроме того, (/ о I)(x) е Lx &ая каждого х е С.
хес
Рассмотрим еще несколько следствий аксиомы выбора.
°Теорема 2.10. Пусть А — непустое множество, R0 — отношение
порядка на А. Тогда найдется отношение R D R0f которое линейно
упорядочивает А.
§2.4. АКСИОМА ВЫБОРА
57
Доказательство. Через X обозначим множество всех отношений
порядка на А, содержащих R0. Множество X частично упорядочено
отношением с собственного вложения.
Пусть 7 — цепь в X. Покажем, что она ограничена в X.
Пусть Q = иУ. Очевидно, для любого S е 7 имеем S С Q. Легко
проверить, что Q — отношение частичного порядка на А. Поэтому
цепь 7 ограничена.
Тогда по лемме Цорна в X есть максимальный элемент, обозначим
его R. Покажем, что это линейный порядок. Так как R — частичный
порядок, то достаточно показать его связность. Предположим, что R
не связно, т. е. существуют а,Ь е А такие, что ] (aRb) Л(а^ Ь)Л] (bRa).
Пусть S = {(х,у)\ (х,у е А) Л ((xRa Л bRy)V(x = а Л bRy)V(xRa Л у =
— Ь)\/(х — а /\ у — 6))}, R' — RUS. Покажем, что R' будет отношением
частичного порядка на А.
1) антирефлексивность: пусть xR'x, т.к. R антирефлексивно, то
xRa и bRx, или х = а и bRx, или xRa и х = 6, или х — а м х — Ь. В
любом случае получим противоречие с предположением.
2) транзитивность: пусть хД'у и уД7^. Возможны только четыре
варианта:
а) (xRy) Л (yRz), откуда xRz и, следовательно, xi?7z;
б) (xRy)A(ySz), откуда (xRy)/\(yRa)/\(bRz), или (xRy)/\(y = a)A(bRz),
или (xRy) Л (уДа) Л (г = 6), или (xRy) Л (у = а) Л (z = b). В любом из
этих случаев получим или (хДа) Л (bRz), или (хДа) Л (z = 6), откуда
xSz и, следовательно, xi?7z;
в) (х5у) Л (yRz). Так же, как в пункте б), можно показать, что xSz,
откуда xR'z.
г) (xSy) Л (ySz). Здесь легко показать, что в любом случае получим
bRa, что невозможно по предположению.
Итак, R' — частичный порядок на А, причем R с R', т.к. aSb (и
значит, aR'b) и в то же время ](aRb). Получено противоречие с тем,
что R — максимальный элемент в X.
Окончательно имеем: R — линейный порядок на А. □
Определение 2.8. Множества X и Y назовем равномощными, если
X о Y, т. е. если существует биекция / : X —» Y
В теории ZFC будем называть множество конечным, если оно рав-
номощно некоторому натуральному числу п, в противном случае
назовем множество бесконечным. В главе 3 в рамках теории ZFC
будет доказано, что множество бесконечно тогда и только тогда, когда
оно равномощно некоторому своему собственному подмножеству.
Без доказательства приведем следующий факт.
58
ГЛАВА 2. ОРДИНАЛЫ
°Теорема 2.11. Пусть А — бесконечное множество, а Ж —
некоторый набор его подмножеств (не обязательно всех), равномощных
А. Тогда существует подмножество Z С А, равномощное А и
своему дополнению А\ Z, обладающее тем свойством, что для любого
X еЖ
znx^tt л (гфх^x\zфщ,
и такое, что его дополнение обладает этим же свойством.
°Следствие 2.12. Если в теореме 2.11 положить А = R, Ж —
семейство непустых совершенных множеств5, то получим, что
существует множество Z CR, имеющее с каждым совершенным множеством
общую точку, и его дополнение обладает тем же свойством6.
Базис Гамеля.
Множество ICK называется независимым, если для любого
конечного набора ненулевых элементов хь ..., хп е X и любых рацио-
п
нальных чисел гъ ... ,гп сумма Yl х%г% обращается в нуль тогда и толь-
г=1
ко тогда, когда все г^ равны нулю. Например, множество {л/2, \/3}
независимо.
Легко показать, что если В — цепь независимых множеств (по
вложению), то ее предел UB также есть независимое множество.
Поэтому из леммы Цорна вытекает следующая
°Теорема 2.13. В Ж существует максимальное независимое
множество.
Определение 2.9. Максимальное независимое множество
называется базисом Гамеля.
Пусть Н — базис Гамеля. Вполне очевидна
п
°Теорема 2.14. Для любого х е К\{0} верно равенство х — J2 uk, где
г=1
ri £ Q \ {0}, h е Н, и это разложение единственно.
Доказательство. Если х не представимо в таком виде, то множество
Н U {х} независимо в противоречии с максимальностью Н. Если же
п т
г=1 г=1
5Такие множества равномощны Ж, см. Куратовский Топология, т.1г «Мир», М.,
1966, т.2, «Мир», М., 1969.
6Можно доказать, что это множество неизмеримо по Лебегу.
§2.4. АКСИОМА ВЫБОРА
59
при различных наборах ^ и &• и не равных нулю т^т\, то множество
{&i,..., &n,&i,...,&JJ
зависимо, откуда зависимо и множество Я. Противоречие. □
Аксиома выбора вместе с привлекательными выводами,
подобными только что приведенным фактам или тем теоремам, которые
эквивалентны ей (в ZF)r обладает и многими «странными»
следствиями, доказывающими существование разного рода «экзотических»
множеств. Некоторые из них мы сейчас покажем, а более богатый
обзор следствий аксиомы выбора можно найти в [8, 11].
°Теорема 2.15. Существует вещественная аддитивная не
непрерывная функция.
Доказательство. Пусть Я — базис Гамеля, х0 G Я. В силу теоремы
2.14 /\ая каждого х е Ж \ {0} существует единственное разложение
по элементам базиса Гамеля. Естественно, элемент х0 может как
входить в это разложение, так и не входить.
Определим функцию / : Ж —» Ж так: если х0 входит в разложение
х с коэффициентом г, то полагаем f{x)=r, если же х — 0 или х0 не
входит в разложение х, то полагаем f(x) = 0. Легко проверить, что
/\ая любых x,j/Gl имеем f(x + y) = f(x) + f(y) ив то же время
функция / разрывна, т. к. принимает только рациональные значения. □
°Теорема 2.16. (Пример Витали). Существует неизмеримое по
Лебегу множество в Ж.
Доказательство. На множестве Ж введем отношение ~ следующим
образом. Положим х ~ у в том и только в том случае, когда х —
— у есть рациональное число. Нетрудно проверить, что отношение ^
есть отношение эквивалентности на Ж. Каждый класс
эквивалентности имеет вид a + Q, где а е Ж, Q — множество рациональных чисел.
Очевидно, что каждый класс содержит точки из отрезка [0; 1].
Пользуясь аксиомой выбора, построим множество М, собрав в нем ровно
по одной точке с отрезка [0; 1] из каждого класса эквивалентности.
Покажем, что множество М С [0; 1] неизмеримо по Лебегу.
Обозначим Мг = М + г, где г е Q П [-1; 1], и пусть S = [j{Mr\ г е
Qfl[—1; 1]}. Множества Мг попарно не пересекаются, поэтому в силу
счетной аддитивности меры Лебега /i получим:
us = Y1 рмт>
reQn[-l;l]
60
ГЛАВА 2. ОРДИНАЛЫ
откуда следует, что при /j,M = 0 имеем fiS = 0Г а при /j,M > 0 получим
jiS = осг т. к. jiMr = jiM при любом г е Q П [—1; 1].
Ясно, что для любой точки а е [0; 1] существует рациональное г
такое, что а + г е М, причем г е [—1;1]. Поэтому [0; 1] С S, откуда
вытекает, что jjlS > 0, а значит, jjlS — ос, т. е. //М > 0.
С другой стороны, объединение всех множеств Мг содержится в
[—1; 2], откуда вытекает, что /j,S < ос, т. е. /j,M = 0. Противоречие.
Итак, множество М не измеримо по Лебегу. □
Одним из наиболее удивительных следствий аксиомы выбора
является т. н. «парадоксальное» разбиение сферы, построенное Хаус-
дорфом.
°Теорема 2.17. (Хаусдорф). Существует разбиение сферы S на
попарно непересекающиеся множества X, Y, Z, Q, которые обладают
следующими свойствами:
(i) X, Y, Z и Y U Z переходят друг в друга вращением сферы;
(п) множество Q счетно.
Доказательство. Рассмотрим две оси а и b вращения сферы S.
Рассмотрим группы вращений {1,р} и {l,q,qq}, где р — вращение на
180° вокруг оси a, q — вращение на 120° вокруг оси Ь. Эти
группы можно свободно перемножить и получить некоторую группу G
вращений сферы.
Каждый элемент этой группы есть некторое слово, составленное
из букв l,p,q. В записи слов мы, естественно, исключаем
последовательности букв рр и qqq, поскольку они заменимы посредством
тождественного вращения 1.
Оси а и b можно выбрать так, что разные слова описывают разные
вращения. Действительно, допустим, что это не так и предположим,
что j\ah любых осей а и b найдутся два разных слова W и V,
описывающих одно и то же вращение, тогда слово WV-1, в котором мы
удалим все последовательности букв рр и qqq, является
тождественным вращением, но это слово, очевидно, не тривиально (поскольку
W ф V). Обозначим через t угол между осями а и Ь. Для данного
нетривиального слова, являющегося тем не менее тождественным
преобразованием сферы, существует лишь конечное множество
допустимых значений угла t. Всего слов — счетное множество. Тогда
всего значений угла t — счетное множество. Противоречие.
Далее считаем, что угол t между осями а и b выбран так, что
никакое нетривиальное слово не может быть равно 1, т.е. что разные
слова дают разные вращения.
§2.4. АКСИОМА ВЫБОРА
61
Ключевой момент: разобьем группу G на три непересекающихся
подмножества А, В, С таких, что
Ар = В U С, Aq = B, Aqq = С.
Очевидно, что можно в А собрать слова, оканчивающиеся на р, в В
— оканчивающиеся на pq, в С — на pqq, и отдать 1 в Ar q — в В, qq
— в С.
На сфере S существует лишь счетное множество точек,
остающихся неподвижными при некотором вращении д е G, поскольку
каждое вращение имеет ровно две неподвижные точки, а всего
вращений в G счетное множество. Обозначим через Q множество всех
таких точек.
Теперь введем отношение эквивалентности на множестве S \ Q
так, что каждый класс эквивалентности — это орбита, порожденная
группой G, точнее, положим ^^ая х,у е S \Q х эквивалентно у
тогда и только тогда, когда у — х * д при некотором вращении д е G.
Далее с помощью аксиомы выбора построим множество М,
содержащее ровно по одной точке из каждого класса эквивалентности, и
положим X = М*А, У = М * Б, Z = М * С.
Нетрудно видеть, что множества X, Y, Z, Q попарно не
пересекаются и удовлетворяют (i) и (п), поскольку
У = М*В = М * (Aq) = (М * A)q = Xq, Z = Xqq,
FUZ = M*(BUC) = M* (Ар) = (M * A)p = Xp,
Q счетно. □
В заключение сформулируем парадокс Банаха—Тарского. На
подмножествах пространства М3 определим отношение ^ следующим
образом: положим X ~ у тогда и только тогда, когда существует
такое разбиение X — Х\ и • • • U Хп множества X на конечное
число попарно непересекающихся множеств и такое разбиение У —
— Yi U • • • U Yn на то же самое число попарно непересекающихся
множеств, что Xi конгруэнтно Yi аая каждого i = 1,..., п.7
Нетрудно проверить, что отношение ^ является отношением
эквивалентности на Ехр(М3), причем, если X не пересекается с X', Y
не пересекается с Y', X ~ у, X' ~ У, то X и X' ~ У и Y'. Имея
в распоряжении перечисленные свойства отношения ~ и теорему
7Напомнимг что два множества в арифметическом конечномерном
пространстве конгруэнтны, если и только если они переходят друг в друга
преобразованиями поворота и переноса.
62
ГЛАВА 2. ОРДИНАЛЫ
Хаусдорфаг в рамках теории ZFC можно доказать следующее
утверждение.
°Теорема 2.18. (Банах—Тарскийг 1924). Замкнутый шар В3 может
быть разбит на два непересекающихся множества В3 = X и Y так,
что В3 ~ X, В3 ~ У.
Иными словами, пользуясь аксиомой выбора, замкнутый шар В3
можно разбить на конечное число частей такг что после некоторой
перестановки этих частей получим два шара того же радиуса.
Понятно, что все части, на которые «разрезается» исходный шар В3,
не измеримы по Лебегу.
Глава 3
КАРДИНАЛЫ
В предыдущей главе мы занимались изучением различных видов
вполне упорядочений множеств, точнее, мы рассмотрели
некоторые свойства специальных множеств, моделирующих все
возможные полные порядки элементов на множествах, отвлекаясь от их
природы. Эти множества мы назвали ординалами.
Теперь же мы намерены пойти еще дальше, и рассмотреть такие
модели множеств, которые отражают лишь «количество» элементов
в множествах, отвлекаясь уже и от порядка этих элементов. Мы
построим специальный класс множеств, называемых кардиналами,
которые и будут нашими моделями «количеств», или, как принято
говорить, мощностями.
Классы ординалов и кардиналов — это два уникальных
класса множеств, предназначенных /\ая отображения двух основных
свойств абстрактных множеств: порядка и количества элементов.
Перейдем теперь непосредственно к изучению кардиналов.
§ЗЛ Мощность множества, Алефы
Для того, чтобы уметь сравнивать «количества» элементов в
множествах, необходимо сначала научиться определять множества с
одинаковым «количеством» элементов. Для этого мы пользуемся одним
особым видом функции — взаимно однозначным соответствием (би-
екцией). Мы говорим, что два множества равномощны, если между
ними существует взаимно однозначное соответствие (см. опр. 2.8).
Для множеств с конечным (натуральным) количеством элементов
это определение вполне естественно. Для всех прочих множеств мы
принимаем точно такое же определение.
64
ГЛАВА 3. КАРДИНАЛЫ
Следующая теорема является простым достаточным признаком
равномощности двух множеств.
Поскольку в одних источниках (см.г например, [12]) эта
теорема называется теоремой Кантора—Бернштейнаг а в других
(например, [13]) — теоремой Шредера—Бернштейна, мы будем называть
эту теорему теоремой Кантора—Бернштейна—Шредера,
сокращенно обозначая CBS.
Теорема 3.1. (CBS) Для любых двух непустых множеств А и В если
существуют инъекции f : А —» В и д : В —» А, то эти множества
равномощны.
Доказательство. Рассмотрим функцию Я : Ехр(А) —» Ехр(А),
определяемую следующей формулой:
Н(Х) =А\д[В\ fX] для всех X С А.
Предположим, что существует корень уравнения Н(Х) — X —
некое множество Х0. Посмотрим, какими свойствами оно обладает.
Обозначим через Y0 множество В \ fX0. Поскольку Н(Х0) = Х0, то
gY0 = А\Х0. Таким образом, сужения функций f\Xo и g\Yo действуют
на непересекающихся подмножествах множеств А и В, но тем не
менее «покрывают» эти множества целиком.
Точнее, рассмотрим обратную к g\Yo функцию, определенную на
множестве A\XQ, обозначив ее h. Имеем: h : А\Х0 —>> У0 — биекция,
f\x0 : Х0 ^ B\Yq — тоже биекция. Тогда объединение этих функций
h U /|х0 есть биекция из А в В.
Итак, доказательство теоремы свелось к поиску корня уравнения
Н{Х) — X. Назовем множество X хорошим, если X С Н(Х), и через
Z обозначим объединение всех хороших множеств.
Нетрудно проверить, что функция Н монотонна по вложению
множеств, т.е. если X С Y, то Н{Х) С H(Y). Пусть z е Z. Тогда
существует хорошее множество X такое, что z е X. Кроме того,
имеем Н(Х) С H(Z) и X С Н(Х). Отсюда заключаем, что z е H(Z),
и это верно ^^ая любого z е Z. Таким образом, Z — хорошее
множество.
Чтобы показать, что Z и есть корень нашего уравнения, надо
проверить обратное вложение, т. е. что H(Z) С Z. Допустим, что это
не так. Тогда существует х е H(Z) \ Z. Рассмотрим множество Zf =
— Z \J {х}. Это множество не может быть хорошим, т.к. иначе оно
бы содержалось в Z. Поэтому Z' % H(Zf). Ясно, что H(Z) С H(Zf),
поэтому Z' % H(Z). С другой стороны, Z С H(Z). Следовательно, точ-
§3.1. МОЩНОСТЬ МНОЖЕСТВА. АЛЕФЫ
65
ка х — единственная точка множества Zj', не попадающая в H(Z).
Получено противоречие с темг что х е H(Z).
Итакг H(Z) С Z} откуда H(Z) = Z, т.е. Z — искомое множество.
□
Отметим без доказательства несколько полезных следствий этой
теоремы.
Следствие 3.2. Множества Z, Z х Z и Q равномощны и.
Следствие 3.3. Множество R, отрезок [0; 1] и полуинтервалы [0; 1),
(0; 1] равномощны интервалу (0; 1).
Введем, наконец, понятие кардинала.
Определение 3.1. Ординал г называется кардиналом (или
кардинальным числом), если ^^ая любого ординала а < т не верно, что
а о т.
Итак, мы видим, что кардинал — это в первую очередь
порядковое число. Но из всех равномощных друг другу порядковых
чисел кардинал является наименьшим таким числом, реализуя как бы
наиболее «емкий» из всех возможных порядков j\ah данного
«количества» элементов. Выбор таких уникальных множеств в качестве
кардиналов определяется, во-первых, замечательными свойствами
самих ординалов (их транзитивностью и вполне упорядоченностью),
а во-вторых, тем, что в качестве мощностей мы берем вполне
конкретные объекты теории множеств, т. е. множества.
Теперь нам следует договориться об обозначениях кардинальных
чисел, используемых на протяжении всей главы. Через Card мы
будем обозначать класс всех кардиналов. Ясно, что Card С Ord,
поэтому класс кардиналов также вполне упорядочен отношением
принадлежности, как и класс ординалов. Знак < /\ая кардиналов будет
использоваться в точности с той же целью, с какой он используется
на классе ординалов. Итак, кардиналы мы можем сравнивать, и это
сравнение есть отношение принадлежности, вполне
упорядочивающее кардиналы.
Если т есть какой-либо кардинал, то через CardT мы будем
обозначать класс всех кардиналов, не меньших, чем т.
Ранее мы условились «по умолчанию» использовать греческие
буквы, кроме ср, ф и и, &ая обозначения произвольных ординалов.
Теперь же мы условимся, что все греческие буквы, начиная с Л и до
конца алфавита, исключая, как обычно, (р, ф и и, обозначают
кардиналы, если не оговорено противное. Буквы ip и ф, как и прежде,
Э Н. И. Казимиров
66
ГЛАВА 3. КАРДИНАЛЫ
зарезервированы нами для обозначения формул, а и есть символ-
константа, обозначающий множество натуральных чисел.
Кардинал т мы называем бесконечным, если т ^ и. В противном
случае кардинал называется конечным, и его мы обозначаем точно
так же, как натуральные числа.
Рассмотрим теперь некоторые свойства кардиналов.
/3.1. Бесконечный кардинал является предельным ординалом.
Доказательство. Предположим, что это не так, и пусть г = S(a),
т ^ и. Покажем теперь, что ординалы а и S(а) равномощны. Если
предположить, что а < и, то отсюда получим т < и, т.е. кардинал т
конечен. Противоречие. Поэтому а ^ и. Пусть / : S(a) —> а и
[О, j = a.
Нетрудно убедиться в том, что / есть взаимно однозначное
соответствие между S(a) и а. Но а < т — S(a). Тогда по определению
кардиналов т не является кардиналом. Противоречие. □
/ 3.2. Ординал и и все натуральные числа являются кардиналами.
/ 3.3. Ординалы S(uj), S(S(u))1 S(S(S(u)))1 ... не являются
кардиналами.
Определение 3.2. Если между множеством X и кардиналом т
существует взаимно однозначное соответствие, то кардинал т называется
мощностью множества X. При этом мы используем для г
следующие обозначения: ||Х||, CardX.
По определению положим также, что мощность пустого
множества 0 есть нулевой кардинал.
Очевидно, что для каждого кардинала т имеем ||т|| = т.
/ 3.4. Мощность множества определяется однозначно.
Доказательство. Если г = ||Х|| и £ = ||Х||, то т и £ равномощны.
Если предположить, что т < £, то £ не есть кардинал (по определению).
Аналогично исключается вариант £ < т. Следовательно, £ = т. □
/ 3.5. Если а — ординал, иг — его мощность, то т ^ а.
/ 3.6. Множество X можно вполне упорядочить тогда и только
тогда, когда оно имеет мощность.
§3.1. МОЩНОСТЬ МНОЖЕСТВА. АЛЕФЫ
67
Доказательство. Пусть (X, <) — вполне упорядоченное множество,
тогда для него существует единственный порядковый тип а.
Обозначим через А множество всех таких ординалов /3 ^ а, что а о /3.
Пусть 7 = mm А. Тогда, очевидно, j о а и ^^ая любого /3 < j не верно,
что /3 о 7- Поэтому 7 — кардинал. Нетрудно видеть, что ||Х|| = j.
Обратно. Если ||Х|| = т, то существует биекция / : X —» т. Тогда
положим ^^ая любых х, у е X х ~< у тогда и только тогда, когда
/(х) < /(у). Итак, (X, -<) — вполне упорядоченное множество. □
Используя это свойство и теорему 2.9, несложно доказать
следующий факт.
Теорема 3.4. Аксиома выбора АС эквивалентна утверждению:
каждое множество имеет мощность.
Следующая теорема показывает существование неравномощных
бесконечных множеств, более того, с ее помощью можно построить
бесконечно много попарно неравномощных множеств.
Теорема 3.5. (Георг Кантор). Ехр(Х) ft X.
Доказательство. Для пустого множества X теорема очевидна. Пусть
Х/0. Предположим, что существует биекция / : X —» Ехр(Х). Пусть
А = {х е Х\ х £ f(x)}. Очевидно, А е Ехр(Х). Пусть а = f~l(A) (ведь
/ — биекция). Как связаны а и А? Здесь ситуация, аналогичная
парадоксу Расселла.
Допустим, что а е А. Тогда по определению множества А получим
а ^ /(а), но /(а) = А. Противоречие.
Предположим, что а £ А. Тогда вновь по определению множества
А имеем а е /(а), вновь противоречие. Итак, Ехр(Х) ft X. □
Следствие 3.6. Если существует мощность Ехр(Х), то существует
мощность X и \\Х\\ < ||Ехр(Х)||.
°Следствие 3.7. Не существует наибольшего кардинала.
Доказательство. Если г — наибольший кардинал, то в силу АС
существует мощность Ехр(т), которая превосходит т в противоречии
с максимальностью кардинала т. □
Заметим, что без аксиомы выбора утверждение о
несуществовании наибольшего кардинала или равносильное утверждение о том,
что Card — не множество, вообще говоря не доказуемы.
5*
68
ГЛАВА 3. КАРДИНАЛЫ
Пользуясь теоремой Кантора и известным фактом анализа о томг
что Ж о Exp(tj),1 легко видеть, что и ft М, более того, в рамках
теории ZFC справедливо неравенство: и < \\Щ\.
Нетрудно доказать следующий признак сравнения мощностей.
/ 3.7. Если у множеств А и В существуют мощности, то \\А\\ ^ ||-В||г
если выполнено хотя бы одно из условий:
1) существует инъекция f : А—> В]
2) существует сюръекция / : В —» А.
/ 3.8. Если А — множество кардиналов, то UA — кардинал, причем
\jА = sup А в классе Card.
Доказательство. По аналогичному свойству ординалов получаем,
что UА — ординал, причем UA = sup А. Осталось показать, что UA —
кардинал.
Пусть а < UA и а равномощен UA Очевидно, существует г е А
такой, что а < т. Пусть £ = ||а||. Тогда £ ^ а < т. Кроме того,
т С и А. Поскольку а о UA и £ = ||а||г то существуют биекции из
UA в а и из а в £. Это означает, что существует биекция из UA
в £, а значит, существует инъекция из т в £. С другой стороны,
тождественная функция на £ будет инъекцией из £ в г. Тогда по
теореме CBS получим £ = т. Противоречие. Итак, UA — кардинал.
□
Введем следующее обозначение. Через т+ будем обозначать
наименьший из кардиналов, больших т, если такой кардинал
существует. В теории ZFC кардинал т+ существует /\ая любого кардинала т,
кроме того, справедлива следующая
°Теорема 3.8. (Об алефах2).
Существует и единственно отображение К : Ord —» Card^ такое,
что:
1) K(0)=cj;
2) ЦБ (а)) = tt(a)+;
3) если а — предельный, то К (а) = sup К (7).
1г1ри доказательстве этого факта аксиома выбора не используется!
2Алеф — N — первая буква древнееврейского алфавита.
§3.1. МОЩНОСТЬ МНОЖЕСТВА. АЛЕФЫ
69
Доказательство. Пусть jF : Exp(Card^) —» Card^ и &(А) = sup А, если
sup А ^ А, и З^А) = (supA)+, если sup А е А для любого непустого
подмножества А с Card^, 3^0) = о;.
Тогда по теореме о рекурсивных определениях существует
отображение К из Ord в Card^ такое, что К (а) = З^Ка).
а) Пусть а < /3, тогда ^ С КД откуда К (а) ^ К(/3). К (а) е К/3.
Предположим, К (а) = К(/3), тогда К(/3) е К/3, откуда З^К/З) е К/3, что
противоречит определению jF. Итак, К (а) < К(/3).
б) К(0) = Зг(0) = и.
в) Так как К[S(а)] в силу монотонности К, доказанной выше, имеет
максимум, равный К(а), то ^(^[^(а)]) = К(а)+, откуда N(£(a)) = К(а)+.
г) Для предельного ординала а имеем sup а = а (см. свойство
ординалов 2.12). Если Ка имеет максимальный элемент, то в силу строгой
монотонности К, доказанной в а), а также имеет максимальный
элемент, откуда sup а е а. Противоречие.
Итак, в Ка нет наибольшего элемента, следовательно, З^Ка) =
= supKa, откуда К(а) = sup N(7).
д) Единственность отображения К, удовлетворяющего 1)—3),
легко проверяется по индукции. □
Условимся везде далее вместо К (а) для рассмотренного в теореме
отображения К писать NQr т.е. используем индекс. Такое
обозначение бесконечных кардинальных чисел было введено еще Кантором.
Этим, собственно, и объясняется название теоремы: об алефах.
°Теорема 3.9. Отображение К, существование которого доказано в
теореме 3.8, биективно.
Доказательство. 1) Инъективность К следует из пункта а)
доказательства предыдущей теоремы.
2) Покажем сюръективность К. Предположим, что К не сюръек-
тивно, и через г обозначим наименьший из кардиналов, не
принадлежащих образу К Ord. Очевидно, т > и.
Пусть X = {£| о; ^ £ < т}. В силу монотонности К легко показать,
что множество А = {а\ Ка е X} является ординалом. Тогда если А
— предельный ординал, то supX 0 X и в то же время supX ^ т,
поэтому supX = т. Но supX = Кд по теореме 3.8, поэтому т е К Ord.
Противоречие.
Если А — последующий ординал, то supX е X, откуда т = (supX)+
+. Но А = S(supA) (по свойству 2.12 ординалов), откуда Кд =
= (К8ирд)+ = (supX)+ = т, откуда снова получаем т е К Ord.
Противоречие.
70
ГЛАВА 3. КАРДИНАЛЫ
Следовательно, К сюръективног и теорема доказана. □
Итак, любое бесконечное кардинальное число можно представить
как Ка при некотором ординале а, если мы принимаем аксиому
выбора.
Как мы знаем, существуют предельные и последующие
ординалы. Они составляют два достаточно богатых по свойствам подкласса
класса Ord. Каждый кардинал является ординалом, поэтому и
ненулевые кардиналы можно разделить на два класса, отнеся к первому
классу кардиналы, являющиеся предельными ординалами, а ко
второму — кардиналы, являющиеся последующими ординалами.
Однако, как показывает свойство 3.1, такое разбиение кардиналов на
классы весьма примитивно, ибо первый класс совпадет с классом
Card^, а во второй войдут все конечные ненулевые кардиналы.
Поэтому j\ah кардиналов используют иной способ разбиения на
специальные классы, а именно:
Определение 3.3. Кардинал т называется изолированным, если
существует кардинал £ такой, что т = £+, в противном случае
ненулевой кардинал т называется предельным.
Действуя по аналогии с доказательством только что приведенной
теоремы, нетрудно установить следующий факт.
°Теорема 3.10. Для любых ненулевого ординала а и непустого
множества ординалов А справедливо следующее:
1) а — предельный ординал тогда и только тогда, когда #а —
предельный кардинал;
2) а — последующий ординал тогда и только тогда, когда tta —
изолированный кардинал;
3) %иРА = SUpK7.
Поэтому кардинал #Ш1 как и кардинал и, является предельным
кардиналом, а все кардиналы Кп изолированы при п > 0.
Приведенные теоремы об отображении К из класса ординалов в
класс кардиналов показывают, что если Card — не множество, то К
есть порядковый изоморфизм между этими классами, т. е. взаимно
однозначное соответствие, сохраняющее порядок. На самом деле
существует гораздо более общая теорема об изоморфизме некоторых
классов, не являющихся множествами, и класса ординалов, а
теорема об алефах является лишь ее частным случаем благодаря аксиоме
выбора.
§ 3.2. КОНЕЧНЫЕ И БЕСКОНЕЧНЫЕ МНОЖЕСТВА. СН 7Л
Теорема 3.11. (Об изоморфизме классов).
Пусть собственно класс X вполне упорядочен отношением-классом
-< и удовлетворяет условию:
для каждого у е % класс {х е % : х -< у} есть множество.
Тогда классы % и Ord изоморфны (т. е. можно определить взаимно
однозначное отображение из X в Ord, сохраняющее порядок).
В частности, Любые два собственно класса ординалов порядково
изоморфны.
Мы не будем приводить здесь доказательство этой теоремы, т. к.
оно практически повторяет доказательство теоремы об алефах и
использует построение необходимого отображения по трансфинитной
рекурсии. Мы предлагаем читателю попробовать доказать
приведенную только что теорему.
§ 3,2 Конечные и бесконечные множества.
Континуум-гипотеза
Мы уже довольно часто пользовались понятиями конечного и
бесконечного множества, и даже определили конечные и
бесконечные кардиналы. Введем теперь определение j\ah произвольных
множеств.
Определение 3.4. Множество X называется бесконечным, если оно
обладает бесконечной мощностью, т. е. существует кардинал т\ т —
— \\Х\\, т ^ и. Множество X называется конечным, если оно обладает
конечной мощностью, т.е. существует п: п — \\Х\\.
Множество X называется счетным, если ||Х|| = и.
Множество X называется не более чем счетным, если ||Х|| ^ и.
Каждое множество либо конечно, либо бесконечно, либо
утверждение о существовании его мощности недоказуемо в ZF. Аксиома
выбора позволяет исключить этот третий случай и говорить, что
каждое множество либо конечно, либо бесконечно. Бесконечные
множества обладают следующим свойством, отличающим их от
конечных.
Теорема 3.12. Если X — бесконечное множество, то для любого
множества а мощности множеств X \ {а}, X и X и {а} равны.
72
ГЛАВА 3. КАРДИНАЛЫ
Доказательство. Пусть ||Х|| = т, г ^ и, и пусть а ^ X. Нетрудно
показать, что множество X и {а} равномощно тогда ординалу S(r).
Между ординалом S(r) иг легко установить взаимно однозначное
соответствие, как мы это уже делали при доказательстве свойства
3.1 кардиналов. Поэтому ||Хп{а}|| = т. Для а е X теорема очевидным
образом справедлива.
Пусть теперь Y = X \ {а}, а е X. Понятно, что используя полное
упорядочение X, которое можно задать при помощи взаимно
однозначного соответствия множества X и кардинала тг можно вполне
упорядочить и множество Y. Поэтому мощность Y существует. Если
Y конечно, то понятно, что X тогда также конечно — противоречие.
Если Y бесконечно, то по только что доказанному мы получим, что
||У|| = \\Y U {а}\\, т.е. ||У|| = \\Х\\. При а £ X теорема также
очевидна. □
Итак, мы видим, что при «выбрасывании» одной (или
нескольких) точек из бесконечного множества мощность этого множества
сохраняется. Таким образом, каждое бесконечное множество
равномощно некоторому своему собственному подмножеству. На этом
признаке базируется другое определение конечных и бесконечных
множеств, принадлежащее Дедекинду.
Определение 3.5. Множество X называется бесконечным по
Дедекинду, если оно равномощно некоторому своему собственному
подмножеству, в противном случае множество X называется конечным
по Дедекинду.
Определение Дедекинда не подразумевает наличия у множества
мощности, и потому любое множество либо конечно по Дедекинду,
либо бесконечно по Дедекинду. При выполнении аксиомы выбора
оба определения совпадают, при отрицании АС могут существовать
такие множества, которые не имеют мощности, но тем не менее
бесконечны (или конечны) по Дедекинду. Оба эти факта вытекают
из следующей теоремы.
Теорема 3.13. Если множество X конечно, то оно конечно по
Дедекинду. Если множество X бесконечно, то оно бесконечно по
Дедекинду.
Введем теперь обозначение: с = ||М||, если существует мощность
множества Ж всех вещественных чисел. Понятно, что Ж бесконечно
по Дедекинду, ибо Ж о [0,1], а если мы предполагаем существование
мощности с (мощности континуума), то Ж будет и просто
бесконечно. В силу следствий к теореме Кантора мы можем сказать даже,
§ 3.2. КОНЕЧНЫЕ И БЕСКОНЕЧНЫЕ МНОЖЕСТВА. СН 73
что с > и, т.е. континуум несчетен. И здесь возникает новый
вопрос: насколько вообще кардинал с больше cj? Или: существуют ли
множества мощности т такой, что и < т < с?
Этот вопрос впервые был сформулирован Кантором в конце XIX
века. Сам Кантор неоднократно пытался отыскать несчетное
множество мощности меньше с, «прореживая» известные
континуальные множества, строя нигде не плотные множества вещественных
чисел. В результате появились канторовы совершенные множества,
но все они оказались континуальными. На основании всех своих
исследований Кантор предположил, что не существует такого
множества. Его гипотеза в наших обозначениях формулируется в виде
равенства и+ — с, которое называется гипотезой континуума или
континуум-гипотезой и обозначается СН.
Введем следующее обозначение: через Т мы обозначим мощность
множества Ехр(т). Объясняется такое обозначение следующим
образом. Когда мы определяли прямое произведение множеств в
общем виде (см. §1.6), мы ввели также понятие возведения
множества А в степень-множество В, обозначая через Ав множество всех
функций из В в А. Если мы теперь в качестве множества А
рассмотрим ординал 2 = {0,1}, то 2В будет множеством всех функций,
определенных на Б и принимающих значения 0 или 1. Нетрудно
установить взаимно однозначное соответствие между 2В и Ехр(Б),
выбирая j\ah каждой функции из 2В прообраз единицы. Поэтому
|| Ехр(Б)|| = ||2Б||, откуда и появилось обозначение: 2^в^ := || Ехр(Б)||.
В частном случае, когда В — т получим, что мощность Ехр(т) равна
2Т.
Мы уже упоминали ранее, что мощность континуума такова же,
как мощность множества всех подмножеств натурального ряда,
т. е. с = ||Ехр(о;)|| или, в силу наших обозначений, с = 2Ш. Тогда
континуум-гипотеза выражается равенством и+ — 2Ш.
Аналогично, рассматривая вместо кардинала и произвольный
бесконечный кардинал г, сформулируем обобщенную континуум-
гипотезу (GCH): т+ = 2Т.
На сегодняшний день известно, что как континуум-гипотеза, так
и обобщенная континуум-гипотеза не зависят как от аксиом ZF, так
и от аксиом ZFC. Точнее, справедливы следующие теоремы.
Теорема 3.14. (Курт Еёдель, 1936).
Con(ZF)^ Con(ZF+CH), Con(ZF)^ Con(ZF+GCH),
Con(ZF)^ Con(ZFC+CH), Con(ZF)^ Con(ZFC+GCH).
Теорема 3.15. (Поль Коэн, 1963).
74
ГЛАВА 3. КАРДИНАЛЫ
Con(ZF)-> Con(ZF+]CH)r Con(ZF)-> Con(ZF+]GCH)r
Con(ZF)-> Con(ZFC+]CH)r Con(ZF)-> ConZFC+]GCH).
Следует однако отметить, что GCH влечет аксиому выбора АС [7].
Отсюда следует, что теория ZF+GCH+]AC противоречива. То есть
мы не можем сказать, что АС не зависит от аксиом ZF+GCH.
Более подробное рассмотрение проблем, связанных с доказательством
непротиворечивости СН и GCH с аксиоматикой Цермело—Френкеля,
можно найти у П. Коэна в [7] или в Справочной книге по
математической логике [8].
Итак, кроме аксиомы выбора существуют и другие утверждения
о свойствах множеств, которые можно сформулировать в рамках
языка ZF, но невозможно ни доказать их, ни опровергнуть в ZF.
На самом деле, в силу теоремы Гёделя о неполноте [4] таких
утверждений можно найти бесконечно много. В § 3.5 мы рассмотрим еще
несколько подобных утверждений.
§ 3,3 Предельные теоремы о мощностях.
Теорема о квадрате
В этом параграфе все теоремы мы будем доказывать в теории ZFC.
Первая теорема, которую мы здесь докажем, по сути является
переформулировкой леммы Цорна.
°Теорема 3.16. (Принцип сквозной цепи). В любом частично
упорядоченном множестве существует сквозная цепь.
Доказательство. Пусть (X, <) — частично упорядоченное
множество. Предположим, что в X существует неограниченная непустая
цепь С. Тогда эта цепь и будет сквозной, ибо j\ah нее не существует
элемента а е X такого, что при любом с е С имеем с < а.
Предположим теперь, что в X любая цепь ограничена. Тогда в
силу леммы Цорна в X существует максимальный элемент а. Но
тогда множество {а} является сквозной цепью в X. □
Пусть С — цепь множеств по вложению, т. е. (С, с) является
линейно упорядоченным множеством. Пределом цепи С мы называем
объединение UC ее элементов. Ясно, что /\ая любого А е С имеем
А С иС, поэтому \\А\\ ^ || U С\\ аая любого А е С. Но как указать
более точную оценку /\ая мощности предела цепи С?
Следующая теорема позволяет нам ответить на этот вопрос.
§3.3. ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ. ТЕОРЕМА О КВАДРАТЕ 75
°Теорема 3.17. (О мощности предела цепи). Пусть С — цепь
множеств по вложению и для каждого множества А е С имеем \\А\\ < т.
Тогда \\UC\\ ^ т.
Доказательство. Пусть X = UC. Рассмотрим множество $ всех би-
екцией между множествами А е С и их мощностями £ < т, а именно,
$={f: f:A^Z,AeC,Z<T,f- биекция}.
Ясно, что это множество не пусто. Кроме того, оно частично
упорядочено отношением с. Так что в силу принципа сквозной цепи в $
существует сквозная цепь (£. Обозначим С — {dom(/) : / е <£}. С
— непустая подцепь цепи С. Поскольку (£ является цепью биекций,
то ее предел /0 = U<£ также есть биекция между UC = dom(/0) и
U/Geran(/) = ran(/o). Ясно, что dom(/0) С X, ran(/0) С т.
Предположим теперь, что dom(/0) ф X. Это означает, что в цепи С
существует элемент А такой, что А % dom(/0). Поскольку dom(/0) —
это предел цепи С", то очевидно также А % В &ая каждого В е С Но
тогда в силу линейной упорядоченности С по вложению получаем,
что ^я каждого В е С имеет место В d А, откуда dom(/0) С А и,
более точно,
dom(/0) С A (3.i)
ввиду предположения о том, что А % dom(/0).
Покажем теперь, что гап(/0) есть кардинал, меньший т.
Действительно, поскольку для каждого / е <£ имеем ran(/) е Card, то ran(/0) =
= U/Geran(7) также есть кардинал по свойству кардиналов 3.8. При
этом
ran(/o) = ||dom(/0)||^||A||<r. (3.2)
Обозначим теперь В — А \ dom(/0)r D — т\ гап(/0). Оба эти
множества не пусты согласно (3.1) и (3.2). Если \\В\\ ^ \\D\\, то
существует инъекция из D в В. Тогда, используя биекцию /0г нетрудно
построить инъекцию из т в А, откуда по теореме CBS получаем
\\А\\ = т. Противоречие. Итак, ||Б|| < \\D\\ ^ т. Пусть h : В —» D —
инъекция. Обозначим через а порядковый тип ran(/i), hi : ran(/i) —>>
[ran(/0); ran(/0)+oa) — порядковый изоморфизм, где через +0
обозначена сумма ординалов. Индукцией нетрудно проверить, что /\ая
каждого /3 е ran(/i) имеет место hi(/3) ^ /3. Тогда из того, что ran(/i) С т,
следует, что ran(/0) + 0а ^ т. Тогда, как нетрудно видеть, множество
/ = /о U (hi о К) является биекцией между А и гап(/0) + 0а.
76
ГЛАВА 3. КАРДИНАЛЫ
Итакг / е $ и / является верхней гранью для (£, причем, / ^ (£, т. к.
dom(/) = A D dom(/0). Это противоречит тому, что цепь (£ сквозная.
Итак, предположение о том, что dom(/0) ф X, приводит к
противоречию, следовательно, dom(/0) = X. Далее, поскольку /0 — инъекция
в т, то ||Х|| ^ т, то и требовалось проверить. □
Условие теоремы \\А\\ < т для каждого А е С существенно.
Действительно, рассмотрим изолированный кардинал т+. Этот кардинал
сам является цепью по вложению своих элементов-ординалов.
Если кардинал т бесконечный, то среди ординалов а е т+, понятно,
существуют ординалы мощности т, причем, поскольку т+ является
предельным ординалом, то т+ является пределом цепи своих
элементов. Для каждого а е т+ имеем ||а|| ^ т, но нестрого неравенства
добиться нельзя, а мощность предела цепи т+ больше т.
Следующая теорема позволяет представлять любое бесконечное
множество в виде предела цепи его подмножеств меньшей
мощности.
°Теорема 3.18. Пусть X — бесконечное множество. Тогда найдется
цепь С его подмножеств такая, что UC = X и для любого А е С
имеем \\А\\ < \\Х\\.
Доказательство. Для бесконечного множества X рассмотрим
множество 7 всех его подмножеств меньшей мощности, т. е.
3>={ЛеЕхр(Х)|||Л||<||Х||}.
Очевидно, что 7 не пусто и частично упорядочено отношением
С. Тогда в 7 найдется сквозная цепь £. Через А* обозначим предел
этой цепи. Очевидно, что А* С X, поэтому ||А*|| ^ ||^||-
Предположим, что \\А*\\ < \\Х\\. Тогда существует а е X \А*.
Рассмотрим множество Aq = А* и {а}. Если множество А* конечное, то
множество А0 также конечное, откуда ||А0|| < ||^||- Если же
множество А* бесконечное, то ||А0|| = ||^4*|| < ||^||- Итак, в любом случае
А0 е 7 и ограничивает цепь £, не будучи элементом этой цепи, т.е.
цепь £ не может быть сквозной. Противоречие.
Поэтому ||А*|| = \\Х\\. Пусть / : А* —» X суть биекция. Построим
цепь С как образ цепи £ по функции /, т. е.
C = {fA\AeE}.
Нетрудно видеть, что в силу биективности / эти цепи порядково
изоморфны по вложению. Кроме того, для любого А е £ имеем
||Л|| = ||/^4||г поэтому все элементы цепи С имеют мощность меньше
\\Х\\. А поскольку UC = /[и£], то UC = X. Теорема доказана. □
§3.3. ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ. ТЕОРЕМА О КВАДРАТЕ 77
Доказательство этой теоремы интересно темг что его можно
использовать в наивной теории множеств, т. к. мы не используем здесь
определение кардинала и ординала по фон Нейману. С
использованием теории ординалов и кардиналов в смысле фон Неймана эту
теорему легко доказать, рассматривая биекцию между множеством
X и кардиналом т.
Из этой теоремы, в частности, следует, что отрезок [0,1]с1
можно представить как предел возрастающей цепи множеств мощности
меньше с, а в случае принятия континуум-гипотезы, — счетных
множеств. Эта цепь, разумеется, не может быть счетной, иначе мы бы
пришли к противоречию, например, со счетной аддитивностью
меры Лебега.
Следующая теорема позволяет нам вычислять мощности
конечных прямых произведений бесконечных множеств.
°Теорема 3.19. (О квадрате). Если т — бесконечный кардинал, то
\\т х т\\ = т.
Доказательство. Воспользуемся трансфинитной индукцией на
классе бесконечных кардиналов.
Предположим, что ^^ая каждого бесконечного кардинала £ < т,
если таковой имеется, утверждение теоремы справедливо, т.е. ||£ х
х £11 = Н£1|г и покажем это равенство ^^ая т.
Во-первых, отметим, что поскольку ||а|| < г &ая любого ординала
а < т (это следует из определения кардинала), то /\ая каждого
ординала а < т имеем \\а х а\\ = ||а||, если а ^ и, и \\а х а\\ < и, если а —
натуральное число. В любом случае j\ah а < т имеем \\а х а\\ < т.
Во-вторых, кардинал т есть предельный ординал, поэтому т =
= sup г = U а, откуда нетрудно получить, что
т х т = [J аха,
т. е. множество т х т является пределом цепи множеств а х а, где
а < т.
Теперь по теореме 3.17 о мощности предела цепи получаем, что
\\т х т\\ ^ т. С другой стороны, очевидно, что \\т х т\\ ^ т, а значит,
т х т имеет мощность т. Теорема доказана. □
°Следствие 3.20. Для любого бесконечного множества X имеем \\Х х
хХ\\ = ||Х||.
°Следствие 3.21. Если множество X бесконечно, а множество Y
таково, что \\Y\\ ^ \\Х\\, то \\Х х У|| = ||Х||.
78
ГЛАВА 3. КАРДИНАЛЫ
Доказательство. Поскольку X х Y С X х X, то очевидно, что \\Х х
х У|| <С \\Х х Х|| = ||Х||. С другой стороны, \\Х х У|| ^ ||Х||. П
°Следствие 3.22. Если множество X бесконечно, п е и, п > 0, то
\\Хп\\ = \\Х\\, что несложно проверить математической индукцией
по п.
Как частный случай отметим, что ||сс;п|| = и, ||Rn|| = с, п > 0.
°Теорема 3.23. (О сумме). Пусть имеется множество {Xi}ieI и для
каждого i е I имеем \\Xi\\ ^ т. Кроме того, \\1\\ ^ т, а кардинал т
бесконечный. Тогда
£*
<т,
\JXi
iei
< г.
Доказательство. Поскольку ||Х^|| ^ г для каждого i G /f то
можно построить инъекции fa : Xi —> т. Аналогично можно построить
инъекцию д : I —> т. Теперь рассмотрим функцию F : ^2Xi —» т х
х тг определяемую следующей формулой: F(i,x) — (g(i),fa(x)) ААЯ
(г,х) е {г} х Х{. Нетрудно убедиться в том, что F есть инъекция из
Y;Xi в т х т. Поэтому
£*
^ Пт х г|
г.
Вторую часть утверждения теоремы легко доказать, построив
сюръекцию из Xi^i в U 1^. □
/ iei
°Следствие 3.24. Не более чем счетное объединение не более чем
счетных множеств не более чем счетно.
§ 3,4 Арифметика кардиналов
В § 2.3 мы изучали арифметику ординалов — сложение и
умножение. Здесь мы намерены рассмотреть сложение, умножение и
возведение в степень кардиналов. Поскольку &ая доказательства
большинства равенств данного параграфа требуется существование
мощностей рассматриваемых множеств, то все утверждения здесь
мы будем считать теоремами ZFC, а не ZF, хотя некоторые свойства
можно доказывать и без аксиомы выбора.
§3.4. АРИФМЕТИКА КАРДИНАЛОВ
79
Пусть имеется множество кардиналов {т^еАг
проиндексированное множеством А.
Сложение.3
Через Y1 тг обозначим мощность множества (J {i} х т^.
ieA ieA
Определение 3.6. Символ Y1 ^% называется суммой кардиналов Ti по
ieA
множеству А.
Для А = 0 положим Yl Ti — 0.
ieA
Для ||А|| < и мы используем обычные математические обозначе-
п
ния суммы, например, Y1 Ч или г + <^ + \- х-
г=1
Если мы обратим внимание на определение суммы ординалов, то
увидим, что сумма кардиналов в смысле сложения ординалов (ведь
кардиналы являются ординалами) вообще говоря отлична от
суммы кардиналов, поэтому эти понятия следует различать. Кроме
того, сумма кардиналов обладает гораздо большим числом обычных
арифметических свойств сложения, чем сумма ординалов. Для
натуральных чисел, как нетрудно проверить, сумма кардиналов
совпадает с обычной суммой натуральных чисел. Рассмотрим некоторые
свойства сложения кардиналов.
/ 3.9. (коммутативность) т + ^ = <^ + т.
/ 3.10. (обобщенная коммутативность) Если функция / : А —» А
является перестановкой множества А, т. е. биекцией из А в А, то
^2п = 1^&, где& = T/(i),
ieA ieA
т. е. сумма кардиналов не зависит от перестановки слагаемых.
/ 3.11. (нейтральный элемент) т + 0 = т.
/ 3.12. (монотонность) Если А С В и /\ая ieA имеем т^ <^, то
Е^Еб-
ieA ieB
/ 3.13. (ассоциативность) т + (£ + х) — (т + 0 + Х-
большинство свойств сложения, умножения и возведения в степень
кардиналов приведены здесь без доказательств ввиду не особой их сложности. Эти
доказательства можно найти, например, в [9, 14].
80
ГЛАВА 3. КАРДИНАЛЫ
/ 3.14. (обобщенная ассоциативность) Если А — U Bj и для j ф jf
имеем Bj П By = 0Г то
ieA jex \ieBj
Из теоремы о сумме 3.23 нетрудно получить следующие свойства
сложения кардиналов.
/ 3.15. т + ^ = тах{т, £}, если хотя бы один из кардиналов т или £
бесконечен.
/ 3.16. Если Ti ^ т для любого i е А и \\А\\ ^ т, то Y, Ъ ^ т.
ieA
/ 3.17. Если множество кардиналов {т^ел имеет максимум или т^ ^
\\А\\ для любого г е А иг кроме тогог хотя бы один из кардиналов
sup^ или \\А\\ бесконечен, то Y1 Ъ — maxjsupr^ ||А||}.
ieA г
Умножение.
Определение 3.7. Произведением кардиналов т^ по множеству А при
А ф 0 называется мощность прямого произведения кардиналов т^ по
множеству А:
ieA
h\(f:A^[JTt)A(\/ieA: /(г) е тг)\
I ieA )
Для А = 0 полагаем ]\ п — 1.
ieA
Доопределение произведения в случае пустого множества А (как
и суммы) производится лишь для единообразия записи формул
арифметических равенств с кардиналами.
Произведение кардиналов, как и сумма, отличается от
произведения ординалов как определением, так и свойствами. Для
обозначения конечных произведений мы также будем использовать обычные
п
математически символы такие, как П Ъ или т£... %.
г=1
Рассмотрим некоторые свойства произведения.
/ 3.18. (коммутативность) т£ = £т.
/ 3.19. (обобщенная коммутативность) Если функция / : А —» А
является перестановкой множества А, то
г<ЕА г<ЕА
§3.4. АРИФМЕТИКА КАРДИНАЛОВ
81
т. е. произведение кардиналов не зависит от перестановки
сомножителей.
/ 3.20. (нейтральный элемент) т • 1 = т.
/ 3.21. (умножение на ноль) г • 0 = 0 и, более общог если при
некотором г е А имеем т^ = 0Г то ]\ п — 0.
/ 3.22. (монотонность) Если А С В, &ая каждого i е А имеем т^ ^ &
и &ая г е В\А имеем ^ > 0Г то
/ 3.23. (ассоциативность) т(£х) — (т0х-
/ 3.24. (обобщенная ассоциативность) Если А — \J Bj и &ая j ф f
имеем Bj П Bj> = 0Г то
Из теоремы о квадрате 3.19 несложно получить следующее
свойство.
/ 3.25. т£ ... х = тах{т, £,..., х} ЛЛ51 любого конечного набора
кардиналов, если хотя бы один из них бесконечен и все они больше
0.
Следующие свойства отражают связь сложения и умножения
кардиналов.
/ 3.26. Если ^^ая любого г е A ri = rf то Е ^ = т
геА
/ 3.27. (дистрибутивность) (г + £)х = тх + £х-
/ 3.28. (обобщенная дистрибутивность)
г<ЕА / г'<ЕА
/ 3.29. (теорема Ю. Кенига) Если рфя i е А имеем ъ < &, то
Доказательство. В соответствии с определениями суммы и
произведения кардиналов рассмотрим множества
S=\J{t}xTt, P=h\(f:A^{j£t)A(VteA: /(t)e&)}-
Ь H. И. Казимиров
82
ГЛАВА 3. КАРДИНАЛЫ
Необходимо показать, что не верно ||5|| ^ ||Р||-
Для начала определим проектор щ \ Р —> £i, полагая щ{$) — /(г)
^я каждого / е Р. Рассмотрим произвольную функцию t : S —>• Р.
Ее сужение £|{г}хтг есть функция из {г} х т^ в Рг а суперпозиция ^ =
= ^г ° ^|{г}хтг является функцией из {i} х Ti в &. Поскольку т^ < £ir то
функция gi не может быть сюръекцией, поэтому существует xi е ^
такой, что для любого z G ^ не верно, что <^(г, г) = а^.
Рассмотрим функцию / е Р такую, что для любого г е A f(i)=Xi.
Ясно, что при любых (г, г) е 5 не верно, что *(г, г) = /, т.к. иначе
получилось бы, что gi(i,z) = xi в противоречии с выбором х^.
Итак, любая функция £ : S —> Р не может быть сюръекцией,
поэтому не верно, что ||5|| ^ ||Р||- Тогда ||5|| < ||Р||. □
Возведение в степень.
Определение 3.8. Степенью А кардинала г называется мощность
множества всех функций из Л в г, если кардиналы Лиг отличны от
нуля, обозначаемая тл. Для остальных случаев полагаем: т° = 1, если
т > 0, и 0Л = 0 при любом Л (в частности 0° = 0).
Рассмотрим некоторые свойства степени.
/ 3.30. Если /\ая любого г е А т^ = т, то П Ч — ^"А" при А ф 0.
/ 3.31. тл+^ = тх-т».
/ 3.32. (гОЛ = тх • ел.
/3.33. (г^ = га^
/ 3.34. Если г^иА^^тогЧ^
/3.35. ||Exp(X)|| = 2llxH.
Это свойство свидетельствует о том, что введенное нами ранее
обозначение 2Т теперь приобрело арифметический смысл.
/ 3.36. По теореме Кантора т < Т.
/ 3.37. По теореме о квадрате тп — т &ая бесконечного т.
/ 3.38. Если 2 ^ т ^ Л и и ^ Л, то тл = 2Л.
Доказательство. 2Л ^ тл ^ Лл ^ (2Л)Л = 2ЛЛ = 2Л. П
Теперь мы вспомним про отображение К, «нумерующее»
ординалами кардиналы в порядке возрастания, и приведем следующие
рекурсивные формулы.
§ 3.5. ТИПЫ КАРДИНАЛОВ. АКСИОМЫ БЕСКОНЕЧНОСТИ 83
°Теорема 3.25. (рекурсивная формула Хаусдорфа) Для любых
ординалов а, /3 и натурального числа п имеет место равенство:
где сумму а + п следует понимать как сумму ординалов.
Доказательство этой теоремы использует понятие конфинального
характера кардинала (см. следующий параграф) и достаточно
сложно, поэтому мы не приводим его здесь.4
Как следствие из этой теоремы (при а = 0) нетрудно доказать
рекурсивную формулу Бернштейна:
§ 3,5 Типы кардиналов.
Высшие аксиомы бесконечности
Ранее мы уже имели дело с двумя разновидностями (или типами)
кардиналов — с изолированным кардиналом и предельным. В этом
параграфе мы рассмотрим еще несколько типов кардиналов.
Пусть г — бесконечный кардинал. Очевидно, что т можно
представить в виде суммы Y1 Ъ, где кардиналы т^ и Л не превосходят т.
При А = т можно даже положить т^ = 1 < т, а если при некотором
i п = т, то можно положить Л = 1 < г. Более интересный случай
возникает, когда мы хотим потребовать условие т^ < т &ая любого
i е Л и Л < т.
Определение 3.9. Конфинальным характером кардинала г
называется наименьший из кардиналов Л таких, что существует множество
кардиналов {т^еЛг п < т, удовлетворяющее равенству т — Y, Ч-
iex
Конфинальный характер кардинала т обозначается cf(r).
Кардинал т называется регулярным, если cf(r) = т, в противном
случае (cf (г) < т) кардинал т называется сингулярным.
Итак, мы разделили класс Card^ бесконечных кардиналов на два
подкласса — регулярных и сингулярных кардиналов. Например,
кардинал и регулярен, а кардинал К^ сингулярен.
°Теорема 3.26. Если т ^ и, то т+ — регулярный.
4Это доказательство можно найти в [9].
6*
84
ГЛАВА 3. КАРДИНАЛЫ
Доказательство. Предположим, что т+ сингулярен. Тогда т+ = Y1 Ъ,
где Ti < т+ и Л < т+, Л = cf(r+). Тогда г^ гг Л ^ т, откуда Е ^ ^ ^"2 =
г<ЕА
= т. Противоречие. □
Если мы принимаем аксиому выбора, то благодаря этой теореме
нетрудно показать, что класс регулярных кардиналов неограничен
в классе Card, т. е. является собственно классом. Действительно, /\ая
каждого регулярного кардинала г кардинал т+ также регулярен.
Покажем, что и класс сингулярных кардиналов является собственно
классом. Для произвольного кардинала Ка мы можем рассмотреть
последовательность кардиналов Ка+П и кардинал Na+a;. Этот
кардинал есть сумма всех кардиналов Ка+Ш а потому cf(Na+a;) = и, т.е.
кардинал Na+a; сингулярный. Это означает, что и класс сингулярных
кардиналов неограничен в классе Card, и потому является
собственно классом.
Из любого кардинала (и в частности сингулярного) можно
довольно просто получить регулярный кардинал.
°Теорема 3.27. Кардинал cf (г) регулярен при любом т ^ и.
Доказательство. Очевидно, что cf(r) ^ и, так что мы можем
говорить о его регулярности.
Предположим, что cf(r) сингулярный. Введем обозначения: Л =
= cf(r), /и = cf(A). /и < А ^ г по предположению. Тогда
r = Y^Ti, А = ^А^, Ti<r, Xj < A.
Используя закон обобщенной ассоциативности нетрудно
проверить равенство
jefikeXj
где i(j,k) осуществляет взаимно однозначное соответствие между
множеством (J {j} х Xj и кардиналом Л по определению суммы кар-
диналов.
Рассмотрим одно произвольное слагаемое ^ = Yl Ti(j,k)- Очевидно,
ke\j
что ^j ^ т, т. к. Ti(j^) < т и Л ^ т. Если допустить £j = т, то мы
получим представление кардинала т через меньшее, чем Л = cf(r),
число слагаемых, что невозможно по определению cf(r). Поэтому
О < г.
§ 3.5. ТИПЫ КАРДИНАЛОВ. АКСИОМЫ БЕСКОНЕЧНОСТИ 85
Но тогда имеем т = J2 €ji т-е- вновь кардинал т представлен в
виде суммы с меньшим, чем Л = cf(r), числом слагаемых, ибо мы
предположили, что \i < А. Противоречие.
Итак, cf(cf(r)) = cf(r), т.е. конфинальный характер регулярен. □
°Теорема 3.28. Для любого т е Card^ имеем т < cf(2T).
Доказательство. Пусть Л = cf(2T), 2Т = Y1 Ч, где Ч < 2Т при любом
iex
i е Л. Предположим, что А ^ т.
Воспользуемся теперь теоремой Кенига, из которой следует, что
2т = ^>г < (2Т)Л = 2Т'Л = 2Т,
г<ЕА
что невозможно. Поэтому г < Л, т. е. г < cf(2T). □
Из этой теоремы вытекает, что и < cf(c), в частности множество Ж
вещественных чисел невозможно представить как счетное
объединение множеств мощности меньше с.
Если мы принимаем континуум-гипотезу, то cf (с) = с, т. е. с суть
регулярный кардинал. Если мы принимаем обобщенную континуум-
гипотезу, то каждый кардинал Т регулярен.
Заметим, что конфинальный характер кардинала мы определяем
через сумму кардиналов меньшей мощности. Это означает, что из
существования кардинала т мы можем доказать существование его
конфинального характера, более того, все операции сложения
кардиналов, не превосходящих г, вполне определимы без аксиомы
выбора лишь при условии существования кардинала т. Поэтому наше
определение регулярности и сингулярности кардинала допустимо
формулировать в ZF.
Известно [8], что аксиоматике ZF не противоречат следующие
утверждения:
а) с — изолированный кардинал;
б) с — сингулярный кардинал;
в) с — предельный регулярный кардинал.
Рассмотрим еще несколько типов кардиналов.
Определение 3.10. Кардинал т > и называется слабо
недостижимым, если он предельный и регулярный.
Бесконечный кардинал г называется доминантным (или сильно
предельным), если /\ая каждого кардинала £ < г имеем 2^ < г.
Доминантный регулярный несчетный кардинал называется сильно
(или строго) недостижимым.
86
ГЛАВА 3. КАРДИНАЛЫ
Все сильно недостижимые кардиналы образуют подкласс класса
ординалов, а потому могут быть «занумерованы» ординалами в
порядке возрастания в силу теоремы 3.11. Эти кардиналы принято
обозначать 1па, где а — ординал. Поскольку до сих пор не удалось
доказать или опровергнуть существование строго недостижимых
кардиналов, то утверждение о существовании 1п0 называют аксиомой
и обозначают SI (от Strong Inaccessibility). Кардинал In0 мы будем
называть далее первым строго недостижимым кардиналом.
Насколько безопасна SI в смысле непротиворечивости теории,
полученной присоединением этой аксиомы к ZF или ZFC, не известно,
однако справедлива следующая
Теорема 3.29. Невозможно доказать, что аксиому SI невозможно
опровергнуть (в символах: Con(ZF)/> Con(ZF+SI)).
Но даже если принять аксиому существования первого строго
недостижимого кардинала, то этого оказывается недостаточно /\ая
доказательства существования других строго недостижимых
кардинальных чисел. Поэтому j\ah каждого ординала а можно ввести свою
аксиому S\a о существовании а-то строго недостижимого
кардинального числа.
Рассмотрим еще один тип кардиналов.
Определение 3.11. Кардинал т называется измеримым (по Уламу),
если на нем можно определить меру Улама, т. е. такую функцию
m : Ехр(т) —» 2, что
1) m(r) = 1;
2) ^^ая любого а < т имеем т({а}) = 0;
3) если X = {Хп}^=0 — последовательность попарно
непересекающихся подмножеств кардинала т, то
оо
т(иХ) = $>(ХП).
п=0
На сегодняшний день не известно, противоречит ли утверждение
о существовании измеримого кардинала аксиомам ZF. О величине
первого измеримого кардинала, если таковой существует, можно
судить по следующему результату Тарского.
Теорема 3.30. Первое измеримое кардинальное число больше первого
строго недостижимого.
§ 3.6. УНИВЕРСАЛЬНЫЕ МНОЖЕСТВА. МЕТОД МОДЕЛЕЙ 87
Существует еще несколько типов кардиналов.5 Обо всех этих
кардиналах известно только, что они намного больше всех тех
кардиналов, существование которых можно доказать в ZF.
Аксиомы о существовании кардиналов таких специфических
типов, как строго недостижимые или измеримые, возникшие в
результате неудачных попыток доказать или опровергнуть существование
таких кардиналов, называются высшими аксиомами бесконечности,
т. к. постулируют существование очень больших кардиналов.
§ 3,6 Универсальные множества.
Метод моделей
Подобно тому, как раньше, в главе 2 мы ввели класс специальных
множеств — ординалов, заметно облегчивших понимание самой
теории множеств, как позже мы вводили класс кардинальных чисел
(в текущей главе), так теперь мы введем новый класс множеств,
обладающих не менее интересными свойствами как с точки зрения
теории множеств, так и с позиции математической логики.
Напомним обозначение из §1.7: через 9J мы обозначаем класс
всех множеств.
Теорема 3.31. Существует и единственно отображение S из Ord в
2J, удовлетворяющее свойствам:
1) 3(0) = 0;
2) 3(a) = Ехр(3(/3)), где а = S(P);
3) 3(a) = U 9(Р)г если а — предельный ординал.
(3<а
Доказательство. Построим отображение J : Exp(9J) —» 9J по
следующему правилу: jF(0) = 0 и рфя любого множества А ф 0
ЭГ(А) = lUA' еСЛИ UA^ А'
|Exp(LL4), если и А е А.
По теореме о рекурсивных определениях существует
отображение S из Ord в 9J такое, что при любом а е Ord
S(a) = 2(Sa), где За = {3(/3)| /3 < а}.
5См.г например, [8].
88
ГЛАВА 3. КАРДИНАЛЫ
Докажем трансфинитной индукцией, что для множеств 3(a)
выполняются условия теоремы 1)—3). Действительно, 3(0) = 3^0) = 0,
так что при а = 0 множество 3(&) удовлетворяет 1) —3).
Предположим, что условия 1)—3) выполнены j\ah любого а < Д.
Теперь нам необходимо показать, что 3(A) также подчиняется этим
условиям. В рамках нашего предположения докажем следующие
свойства $(а)\
I. ^ая любых множеств х, у и любого а < А из х е у G 9(a) следует
х е S(a);
II. для любых /3 < а < А имеем 3(/3) С S(a)-
Доказательство первого свойства проведем трансфинитной
индукцией по а < А. Очевидно, что /\ая а = 0 это свойство
справедливо. Предположим, что оно справедливо ^^ая любого /3 < а.
Пусть х е у G S(a). Возможны два случая:
а) а = 5(/3), откуда в силу нашего предположения 3(a) = Ехр(3 (/?)).
Тогда у С 3(/3)г откуда х е 3(Р)- Для любого z е х по предположению
индукции имеем z е 3(/?)г откуда следует х С 3(/?)г т.е. х е S(a)-
б) а — предельный. Тогда g(a) = |J S(/3)r откуда существует /3
(3<а
такое, что у е 9(/3). В силу предположения индукции получим х е
3(/3), откуда жб8(а).
Итак, свойство I доказано. Теперь покажем справедливость
свойства II. Доказательство также проведем трансфинитной индукцией
по ненулевым а < А. Очевидно, что при а = 1 утверждение истинно,
т.к. 3(0) = 0 С 3(1). Пусть оно истинно ^^ая всех а < а0. Возможны
два варианта:
а) а0 = S(a). Тогда 3(^о) = Ехр(3(а))г т.е. 3(a) е 3(^о)г откуда в силу
свойства I 3(a) С З(с^о)- А по предположению индукции 3(Р) С З(с^)
при любом /3 < а. Тогда и при любом /3 < а0 получим 9(13) С З(с^о)-
б) а0 — предельный. Тогда S(c^o) = U 9(/3), откуда очевидно
(3<а0
9(13) С З(с^о) при любом (3 < а0.
Итак, свойство II доказано. Вернемся к доказательству свойств
1)—3) ^^ая ординала А. Здесь снова рассмотрим два возможных
варианта:
а) А = S(5). В силу доказанного свойства II легко показать, что
U з(т) = s(5),
7<А
откуда по определению отображения jF имеем 3(A) = Ехр(3(5)).
б) А — предельный. Если предположить, что U 3(т) ^ ЗА, то су-
7<А
ществует 7о такой, что U 3(т) = 3(то)- Так как А суть предельный
7<А
§ 3.6. УНИВЕРСАЛЬНЫЕ МНОЖЕСТВА. МЕТОД МОДЕЛЕЙ 89
ординал, то £(7о) < А. В то же время 3(£(7о)) = Ехр(3(то)) по
предположению индукции, откуда заключаем, что Exp(S(7o)) С S(7o)r что
невозможно. Итак,
U 3(7) £ зд,
7<А
поэтому 3(A) = F(SA) = U 3(т).
7<А
Итак, &ая а = А условия 1)—3) также справедливы.
Следовательно, 3(a) и есть искомое отображение.
Докажем его единственность. Допустим, что отображение Л(а)
также удовлетворяет 1)—3). Найдем наименьший из ординалов, j\ah
которых 3(a) ф УС (а) и обозначим его А. Ясно, что А > 0, т.к. 3(0) =
= 0 = 1К(0). Если А = S{8), то
3(A) = Ехр(3(£)) = Ехр(ЗД) = ЩА).
Противоречие. Если А — предельный, то
3(A) = (J S(7) = (J ЗД = ЩА).
7<А 7<А
Противоречие. Итак, отображение $(а) единственно. Теорема
доказана. □
Определение 3.12. В дальнейшем условимся вместо 3(a) писать 9JQ.
Всякое множество %За мы будем называть а-ым универсальным
множеством или, короче, а-ым универсумом или универсумом, а класс
ii={9Ja| aeOrd}
всех универсумов будем называть универсальным классом.
Следствие 3.32. Из приведенного доказательства теоремы легко
видеть, что построенное отображение Q(a) строго монотонно, т.е.
для любых а < /3 имеем 3(a) С 3(/3) или, в силу наших обозначений,
Следствие 3.33. Если х е 9Ja, то х С 9JQ.
Доказательство. Пусть х е %За. В силу предыдущего следствия х е
V3S(a) = Exp(9Ja). Тогда х С 9Ja. □
Следующая теорема выражает одно из основных свойств
универсумов и одновременно показывает, что класс 11 не является
множеством.
90
ГЛАВА 3. КАРДИНАЛЫ
Теорема 3.34. Для каждого множества X найдется такой ординал
а, что X С 9JQ.
Доказательство. Допустим, что это не такг т. е. существует
множество X, не содержащееся ни в одном универсуме. Очевидно, X ф
— 0. Пользуясь теоремой о рекурсивных определениях, можно
задать функцию / : и —» 2J, удовлетворяющую равенствам:
Д0)=Х, /(n + l) = U/(n), пей.
Обозначим далее через Т(Х) объединение области значений
функции /. Понятно, что Т(Х) есть множество (это множество
называют транзитивным замыканием множества X). Поскольку из
того, что Y е f(n), следует Y С f(n + 1), то /\ая всякого множества
Y е Т{Х) имеем Y С Г(Х), т.е. множество Г(Х) транзитивно (см.
определение 1.9). Кроме того, очевидно, X С Г(Х), откуда в
частности следует, что множество Т(Х) не пусто. Рассмотрим теперь
множество
М = {Y е Т(Х) U {Х}\ Уа е Ord : Y % ЗД.
Понятно, что X е М, поэтому М не пусто. Тогда по аксиоме
регулярности существует Z е М такое, что ZnM = 0. Из транзитивности
Г(Х) следует, что Z С Т(Х). Очевидно, Z Ф 0, ибо для пустого
множества имеем 0 С 2Jo, а потому 0 ^ М. Нетрудно видеть, что j\ah
каждого z е Z существует ординал а такой, что z е 9Ja-6
На множестве Z зададим функцию r(z), ставящую в соответствие
элементу z е Z наименьший из таких ординалов а, что z е %За.
Теперь через /3 обозначим sup г (г). Покажем, что Z С QJ^. Действи-
тельно, пусть z е Z. Тогда г(z) ^ /3, откуда в силу монотонности
универсумов по вложению (следствие 3.32) получим 91ф) С QJ^. Но
тогда z е 9J/3- Таким образом, Z С 2^, что противоречит тому, что
Z е М. П
В силу теоремы 3.34 корректно следующее
Определение 3.13. Рангом множества X называется наименьший
ординал а такой, что X С 9JQ. Ранг множества X обозначим rank(X).
6Действительно, z Е Z, поэтому z Е Т(Х), но тем не менее z £ М, поэтому
существует а такой, что z С %Ja, тогда z Е %3s(a)-
§ 3.6. УНИВЕРСАЛЬНЫЕ МНОЖЕСТВА. МЕТОД МОДЕЛЕЙ 91
В частности 0 есть множество 0-го ранга, натуральное порядковое
число п есть множество n-го ранга, ординал и есть множество ранга
и. Вообще, &ая любого ординала а его рангом будет он сам.7
Теорема 3.35. Если т — строго недостижимый кардинал, то для
любого а < г имеем ||9Ja|| < т, если только указанная мощность
существует.
Доказательство. Допустим, что это не так, и через а обозначим
наименьший ординал такой, что ||9Ja|| ^ т, а < т. Очевидно, что
а > 0, поэтому а либо последующий, либо предельный. Заметим
также, что из существования мощности %За следует существование
мощностей всех универсумов %3р, /3 < а, поскольку ЯЗр С 9JQ.
1) Пусть а = S((3). Но тогда ЯЗа = Exp(9J/5), откуда нетрудно
получить, что ||9Ja|| = 2^, где £ = ||2Т/з||- В силу выбора ординала а
мощность /3-го универсума меньше т, т.е. ^ < т. Но тогда из
доминантности т следует 2^ < т в противоречии с тем, что ||9Ja|| ^ т.
2) Пусть теперь а предельный. Тогда S0a — (J SO р. Поскольку
(3<а
\№а\\ ^ ^r то существует инъекция / : т —» 9Ja. Обозначим X# =
= {7 e т| /(7) e 91/з}г /3 < <% — прообраз универсума SJ^
относительно функции /. Понятно, что \\Хр\\ существует и \\Хр\\ ^ ||21/з|| < т
в силу выбора а. Тогда т — {] Хр. Отсюда и из теоремы о сумме
(3<а
мощностей вытекают неравенства:
г<£П*/»11^||а|| = <г,
(3<а
что противоречит регулярности кардинала т. □
Теперь мы установим один немаловажный факт из
математической логики, касающийся совместности теорий ZFC и ZFC+SI.
Именно, методом построения модели мы докажем в следующей теореме,
что совместность теории ZFC+SI влечет совместность ZFC. Этот
пример приводится здесь не только как математический результат, он
также является наглядной иллюстрацией метода доказательства
относительной непротиворечивости формальных аксиоматических
теорий путем построения модели.
Поясним коротко суть метода моделей. Пусть у нас имеется
формальная аксиоматическая теория (далее просто теория) Т в языке
первого порядка (как, например, ZF), определенная своими атомар-
7 Мы предлагаем читателю проверить этот факт, пользуясь трансфинитной
индукцией.
92
ГЛАВА 3. КАРДИНАЛЫ
ными формулами cpi(xi,... ,xkl), ..., cpn(xi,... ,xkn) (а в теории
множеств есть лишь единственная атомарная формула —
принадлежность), константами и переменными (в теории ZF, аксиомы которой
мы рассматривали в § 1.1 , существует лишь один сорт переменных,
названных нами множествами), а также набором замкнутых
формул, называемым аксиоматикой этой теории.8
Определение 3.14. Мы говорим, что множество М является
моделью теории Т, если на множестве М заданы такие отношения
i?i(xi,..., xkl),..., Rn{xi,..., хкп), что при замене атомарных формул
(pi,..., (рп теории Т на отношения Дь ..., Rn соответственно и
констант теории Т на некоторые множества, принадлежащие М,
аксиомы теории Т становятся истинными утверждениями на множестве
М (то есть при том условии, что все переменные в полученных
аксиомах пробегают исключительно множество М).
Формулы, полученные в результате указанной замены атомарных
формул и констант, называются интерпретациями формул теории
Т на множестве М.
Замечание 1. Наше определение модели теории имеет несколько
более упрощенный вид, чем это обычно принято в книгах по
математической логике (см., например, [3, 4]). Мы намеренно приводим
такое определение, поскольку нам этого будет достаточно ^^ая
доказательства приводимой ниже теоремы и в то же время это дает
представление читателю о методе моделей доказательства
непротиворечивости аксиоматических теорий.
В том случае, когда Т есть аксиоматическая теория множеств
(например, ZFC+SI), /\а^ построения модели нам необходимо лишь
указать множество-модель и некоторое бинарное отношение R на этом
множестве, которое будет интерпретировать отношение
принадлежности в теории Т. Часто в качестве такого отношения R берут
само отношение принадлежности. Для удобства восприятия мы будем
различать переменные в исходной теории Т и переменные в
модели (то есть переменные, пробегающие исключительно множество-
модель). Для переменных в модели мы будем использовать малые
готические буквы, в то время как переменные теории Т, следуя
идеологии §1.1, будут обозначаться малыми латинскими буквами.
Таким образом, если в качестве отношения R, моделирующего
отношение принадлежности, мы выбираем само же отношение
принадлежности, то атомарной формуле х е у теории Т соответствует
Более подробное и строгое изложение см. в [3], глава 2.
§ 3.6. УНИВЕРСАЛЬНЫЕ МНОЖЕСТВА. МЕТОД МОДЕЛЕЙ 93
формула у е t), в которой переменные у, t) пробегают исключительно
множество М.
Предположим теперь, что мы построили модель М теории Т. Если
теория Т противоречива, то в ней можно найти такую формулу (р,
которая выводима в теории Т вместе с ее отрицанием (т. е. ]ср также
выводима в Т). Очевидно, в этом случае интерпретации формул ср и
~\<р выводимы в рамках модели М. Тогда модель М приводит к
противоречию. Таким образом, из совместности теории множеств (ZFC,
ZF, ZFC+SI, ZFC+CH и т. п.), в которой мы строили модель, вытекает и
совместность теории Т. Поскольку здесь совместность теории
множеств, в которой строится модель теории Т, играет основную роль
при доказательстве непротиворечивости Т, то совместность теории
Т называют относительной.
На сегодняшний день большинство результатов по
непротиворечивости теорий являются именно относительными. При этом
непротиворечивость самой исходной теории множеств (как правило это
ZF или ZFC) считается истиной, ибо на протяжении нескольких
десятилетий интенсивных исследований в ней не было получено ни
одного парадокса.
Перейдем, наконец, к упомянутой выше теореме, в которой мы
построим модель /\ая теории ZFC в некоторой более сильной теории
— ZFC+SI. Данная модель, понятно, является также и моделью ZF,
однако в совместности ZF мы все же более уверены, чем в
совместности ZFC+SI, поэтому не стоит считать данную теорему надежным
доказательством непротиворечивости теории Цермело—Френкеля.
Эта теорема является не более чем красивой и наглядной
иллюстрацией метода моделей, описанного в данном параграфе.
°Теорема 3.36. Если г — первое строго недостижимое кардинальное
число, то 9JT — модель ZFC (в символах: Con(ZFC+SI)^ Con(ZFC)).
Доказательство. Итак, в соответствии с изложенной выше
идеологией, предположим, что атомарной формуле х е у теории ZFC
соответствует формула pet) теории ZFC+SI, где переменные р и t)
пробегают исключительно множество 9JT. Теперь нам необходимо
проверить справедливость аксиом ZFC (точнее, их интерпретаций)
в универсуме 9JT. По мере надобности мы будем вводить и другие
готические буквы в качестве переменных, пробегающих множество
9JT.
1) Аксиома экстенсиональности. Здесь нам следует проверить, что
(? = 9)->((?ез)->(9ез)).
94
ГЛАВА 3. КАРДИНАЛЫ
Пусть x,y,z е 9JT. По аксиоме экстенсиональности теории ZFC
+ SI (а онаг понятно, имеет тот же видг что и одноименная аксиома
теории ZFC)r получаем
(х = у)^> (О е z) -л (у е z)),
а поскольку х, у, z е 9JTr то их можно заменить на р, t), з
соответственно, и тем самым получить требуемое утверждение.
2) Аксиома пустого множества. Формально нам следует
проверить формулу
Зи Уз з i и,
а фактически нам надо указать множество, пустое в 2JT.
Поскольку множество 0, определяемое аксиомой пустого множества теории
ZFC+Slr является элементом универсума 9JT (т.к. 0 = 9J0 G 2Jt по
свойствам универсумов), то оног очевидно, не имеет элементов,
принадлежащих 9JT. Таким образом, 0 — пустое в 9JT, что и требовалось.
3) Аксиома пары. Теперь мы уже не будем придерживаться
строго формального доказательства, чтобы не поглотить обилием
логической символики суть доказательства теоремы. Итак, теперь нам
надо проверить, что для любых множеств у, t) е 9JT пара {у, t)} также
есть элемент 9JT.
Поскольку г есть предельный ординал, то 9JT = U 9JQ. Поэтому
существует а < т такой, что у, rj е %3Ш откуда {у, rj} С 9Ja, откуда
{у, rj} е Exp(9Ja) = 9J^(a). А поскольку S(a) < г, то {у, rj} е 9JT.
4) Аксиома объединения. Пусть у G 9JT. Покажем, что Uy G 9JT.
Аналогично предыдущему получаем, что у е 9Ja при некотором а < т.
Поскольку у С %За по следствию 3.33, то для каждого t> е у имеем
d G 9Ja и, значит, d С 9JQ. Поэтому Uy С 9JQ. Тогда Uy е V3S(a)i откуда
Uy е 9JT.
5) Аксиома степенного множества. Пусть у е 2JT. Проверим, что
Ехр(у) е 9JT. Вновь существует а < г такой, что у С 9JQ. Поэтому
Ехр(у) С 9Ja и, следовательно, Ехр(у) е 9Js(a)r откуда Ехр(у) е 9JT.
6) Схема аксиом содержательности. Пусть <р(х) — формула языка
ZF со свободной переменной х. Ее интерпретацией на множестве
9JT является формула ^(у).9 Пусть 21 е 9JT. Покажем тогда, что
множество 23 = {у е 211 ^(у)} суть элемент универсума 9JT.
9Поскольку в языке ZF (см. § 1.1) нет констант и других термов, кроме
переменных, а атомарные формулы как в ZFC, так и в ZFC+SI (в интерпретации на
множестве) имеют одинаковый вид, то для получения интерпретаций формул нам,
понятно, достаточно лишь произвести соответствующую замену переменных.
§ 3.6. УНИВЕРСАЛЬНЫЕ МНОЖЕСТВА. МЕТОД МОДЕЛЕЙ 95
При некотором а < т имеем 21 С 9JQr откуда нетрудно видеть, что
множество 23 есть элемент %3s(a)- Поэтому 23 е 9JT.
7) Аксиома регулярности. Проверка этой аксиомы аналогична
предыдущим.
8) Схема аксиом подстановки.10 Эта схема аксиом говорит о
следующем. Если имеется некая формула ср(х,у) с двумя свободными
переменными х,у, и на некотором множестве А данная формула
определяет [х \-> у)-отображение, т.е. задает функцию, то область
значений этого отображения (функции) есть множество.
Для проверки этой аксиомы в нашей модели теории ZFC нам
необходимо проделать следующее. Вместо формулы (р(х,у) мы
рассмотрим формулу <р(р, t)), в качестве множества А мы возьмем элемент
21 универсума 2JT, на котором ср определяет (у ь-» tj)-отображение,
и докажем, что область значений полученного отображения также
есть элемент 9JT.
Обозначим далее отображение, определяемое формулой ср, через
f. Понятно, что f : 21 —>> 9JT. Понятно также, что ran (f) С 9JT.n
Необходимо показать, что ran (f) е 9JT.
Как и раньше, нетрудно получить, что при некотором а < г
имеем 21 С 9JQ. Отсюда, а также из АС и теоремы 3.35 вытекает, что
||21|| < т. Рассмотрим функцию д : 21 —>> г такую, что g(a) = ran£;(f(a)).
Обозначим через j супремум всех £((a), a е 21. Ясно, что 7 ^ т.
Предположим, что 7 = т. Тогда кардинал т представим как объединение
меньших его ординалов в числе ||21||. Отсюда нетрудно получить, что
т = £Пя(<011, llfl(a)||<r.
Получено противоречие с регулярностью кардинала т. Поэтому
7 < т. Теперь, поскольку &ая каждого a е 21 имеем f(a) С 9Jranfc(f(a))r
то &ая каждого a е 21 в силу монотонности QJ^ по /3 получаем f(a) С
2Ху и, следовательно, f(a) е 9Js(7)- Но тогда ran (f) принадлежит к
универсуму 915(5(7))' который в силу предельности ординала т, есть
подмножество универсума 9JT.
Итак, ran(f) е 9JT.
9) Аксиома бесконечности. Справедливость этой аксиомы в нашей
модели вытекает из того, что и С 9JW, т. е. и е 2Js,(w)r а значит, a; е 9JT.
10) Справедливость интерпретации аксиомы выбора на
множестве 9JT очевидна в силу того, что аксиома выбора присутствует в
10Здесь и только здесь мы используем строгую недостижимость кардинала г и
аксиому выбора!
11 Напомним, что через ran (f) обозначается область значений функции f.
96
ГЛАВА 3. КАРДИНАЛЫ
теории ZFC+SI и тем самым обеспечивает существование функции
выбора на любом элементе универсума 2JT.
Итакг множество 9JT является моделью теории ZFC. Теорема
доказана. □
Построенная модель теории ZFC примечательна по крайней
мере по трем причинам. Во-первых, это модель на множестве. Ведь
пользуясь определением построения модели мы могли бы получить
импликацию Con(ZFC+SI)—^Con(ZFC) более простым путем, а
именно, указав тождественное соответствие формул в этих теориях (при
этом моделью теории ZFC в ZFC+SI стало бы уже не множество, а
класс всех множеств 9J, на вывод указанной импликации это ничуть
не повлияло бы). Однако модель на множестве всегда более
привлекательна с точки зрения математической логики, особенно, если
множество-модель воспринимается в интуитивном смысле. Кроме
того, эта же модель является, очевидно, моделью теории GB+AC,12
поскольку в качестве интерпретации класса на данной модели
достаточно брать некоторое подмножество множества 9JT.
Во-вторых, аксиома выбора в ZFC+SI дает возможность
построить функцию выбора на всем универсуме 9JT. А это означает, что
9JT является моделью для более сильной теории, чем GB+AC, — для
теории GB+GC, где посредством GC мы обозначаем аксиому
глобального выбора, утверждающую, что существует отображение С класса
9J в класс 9J такое, что для каждого непустого множества X имеем
С(Х) е X. Таким образом, аксиома глобального выбора совместима
с теорией множеств и классов (теорией GB), если только с ZF
совместимы одновременно АС и SI (в символах: Con(ZFC+SI)^Con(GB
+ GC)).
В-третьих, поскольку т £ 9JT (г = In0)r в модели 9JT истинно
отрицание SI. Следует также отметить, что определение строго
недостижимого кардинального числа, принадлежащего универсуму,
равносильно этому же определению с условием, что все переменные,
участвующие в определении, пробегают исключительно данный универсум.
Это нетрудно установить, пользуясь транзитивностью универсума.
Таким образом, если аксиома SI совместна с ZFC, то и ее отрицание
также совместно с ZFC (Con(ZFC+SI)^Con(ZFC+]SI)), т.е. SI в этом
случае не зависит от аксиом ZFC.
12Теория GB — это теория Гёделя—Бернайса [7], являющаяся расширением
теории ZF. GB включает конечное число аксиом (в отличие от ZF, в которой
присутствуют схемы аксиом), но содержит два сорта переменных — множества и
классы. Эта теория формализует понятие класса, описанное нами в § 1.7.
Известно [7], что утверждение Con(ZF) равносильно утверждению Con(GB).
Литература
1. Кантор Г. Труды по теории множеств, М., «Наука», 1985.
2. Архангельский А. В. Канторовская теория множеств, МГУ, 1988.
3. Колмогоров А. Н.г Драгалин А. Г. Введение в математическую
логику, М., Изд-во Моск. ун-таг 1982.
4. Колмогоров А. Н.г Драгалин А. Г. Математическая логика.
Дополнительные главы, М., Изд-во Моск. ун-таг 1984.
5. Гильберт Д. Основания геометрии, М.-Л.г Гостехиздат, 1948.
6. Гильберт Д.г Бернайс П. Основания математики, пер. с нем.г М.г
«Наука»г 1982.
7. Коэн П. Теория множеств и континуум-гипотеза, пер. с англ.г
М.г «Мир»г 1969.
8. Справочная книга по математической логике в 4-х частях/Под
ред. Дж. Барвайсаг 4.2 Теория множеств, М., «Наука», 1982.
9. Куратовский К.г Мостовский А. Теория множеств, пер. с англ.г
М.г 1970.
10. Йех Т. Теория множеств и метод форсинга, М., «Мир»г 1973.
11. Кановей В. Г. Аксиома выбора и аксиома детерминированности,
М., «Наука», 1984.
12. Колмогоров А. Н.г Фомин С. В. Элементы теории функций и
функционального анализа, М., «Наука», 1976.
13. Хенл Дж. Введение в теорию множеств, пер. с англ.г М.г «Радио
и связь», 1993.
14. Александров П. С. Введение в теорию множеств и общую
топологию, М., 1977.
/ Н. И. Казимиров
Указатель обозначений
х £у
(р Л ф
ср\/ ф
ср —>► ф
if ^ ф
Ух (р(х)
Зх (р(х)
{а,Ъ}
{а}
аГ\Ь
aUb
Ua
Exp (а)
S(a)
0
cp(x),ip(x,y)
ф(х),ф(х,у)
ZF
(а, b)
АхВ
ran (tp\A)
ran(/)
X ^Y
!\d
f°9
r1
idA
fC
f-lc
x принадлежит у (атомарная формула ZF) 4
отрицание формулы ср 4
конъюнкция формул (р и ф 4
ДИЗЪЮНКЦИЯ формул if и ф 4
импликация (следование) формулы ф из формулы if 4
эквиваленция (равносильность) формул if и ф 4
для любого х истинно ср(х) (квантор всеобщности) 4
существует х, при котором <р(х) истинно (квантор
существования) 4
символ для определения обозначений 5
пара множеств а и Ь 5
одноточечное множество с элементом а 5
пересечение множеств а и 6 5
объединение множеств а и 6 б
объединение элементов множества а б
множество всех подмножеств множества а б
последующее за множеством а множество б
пустое множество б
обозначения формул (утверждений о множествах) 10
обозначение формул с указанием свободных
переменных 10
система аксиом Цермело—Френкеля 10
упорядоченная пара множеств а и Ъ 16
прямое произведение множеств А и В 17
область значений отображения, определяемого
формулой ср, относительно множества А 18
область значений функции / 19
множества X и Y равномощны 19р 57
сужение функции / на множество D 20
суперпозиция функций / и д 20
функция, обратная к функции / 20
тождественная на множестве А функция 20
образ множества С относительно функции / 20
прообраз множества С относительно функции / 20
99
{xi}ia
[a]~,[a]
<
a ^ b
(ДО
supi?,inf В
maxi?, mini?
[a-b]
[a; b), (a; b]
(a;b)
00
0,1,2,3
rc + 1
с
Y\LX
с
R
W1
2Ш
23
Ord
>,>
l(*,OI
SeA
П <*s
seA
coi(a,b)
co2(a,6)
7TiB,7T2B
Ordi
A!
AC
Con(T)
ZFC
множество, проиндексированное множеством / 22
класс эквивалентности элемента а 23
фактор-множество множества А по отношению
эквивалентности ~ 23
частичное, линейное или вполне упорядочение на
множестве или классе 23р 40, 65
то же, что а < 6 V а = Ь 23
частично, линейно или вполне упорядоченное множество
23
точная верхняя и нижняя грани множества В 23
максимум и минимум множества В 23
отрезок 25
полуинтервал 25
интервал 25
множество натуральных чисел, наименьший
бесконечный кардинал 25
обозначения натуральных чисел 28
натуральное число, следующее за п 28
прямая сумма множеств Lx по множеству С 28
каноническое упорядочение на прямой сумме или
прямом произведении множеств 28, 30
прямое произведение множеств Lx по множеству С 29
множество вещественных чисел 30
множество всех n-ок вещественных чисел 30
множество всех булевых (двоичных)
последовательностей 30
класс всех множеств 33
класс всех ординалов 37
симметричные обозначения ^\ая < и ^ 40
порядковый тип вполне упорядоченного множества
(Х,<) 44
сумма ординалов а§ в порядке А 47
произведение ординалов а§ в порядке А 47, 51
левая и правая координаты упорядоченной пары
множеств а и Ь 49
левая и правая проекции множества В в прямом
произведении двух множеств 49
класс ненулевых ординалов 49
факториал ординала А 51
аксиома выбора 52
утверждение о совместности теории Т 52
теория Цермело—Френкеля с аксиомой выбора 52
ч*
100
УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ
ACW аксиома счетного выбора 52
ZT теорема Цермело 53
ZL лемма Цорна 53
Q множество рациональных чисел 58
CBS теорема Кантора—Бернштейна—Шредера 64
Z множество всех целых чисел 65
Card класс всех кардиналов 65
CardT класс всех кардиналов, не меньших г 65
|X||,Card(X) мощность множества X 66
т+ следующий за г кардинал 68
Kq, алеф с ординальным номером а 69
с мощность множества вещественных чисел, континуум
72
СН континуум-гипотеза 73
2Т мощность экспоненты кардинала т 73
GCH обобщенная континуум-гипотеза 73
X) Ч сумма кардиналов Т{ по множеству А 79
П Т{ произведение кардиналов Т{ по множеству А 80
геА
тх степень А кардинала г 82
cf (т) конфинальный характер кардинала т 83
1па а-ое строго недостижимое кардинальное число 86
SI аксиома существования первого строго недостижимого
кардинального числа Irio 86
SIq, аксиома существования а-то строго недостижимого
кардинального числа 86
ЯЗа а-ое универсальное множество (универсум) 89
Я класс всех универсумов 89
гапк(Х) ранг множества X 90
GB аксиоматическая теория множеств Гёделя—Бернайса 96
GC аксиома глобального выбора 96
Предметный указатель
Аксиома выбора 52
— глобального выбора 96
— счетного выбора 52
Аксиоматика ZF 10р 11
Аксиомы равенства 13
Базис Гамеля 58
Биекция 19
Вполне упорядочение 25р 34
Высшие аксиомы бесконечности
87
Грань множества 24
Индекс 22
Индукция 27, 38
Инъекция 19
Кардинал 65
— бесконечный 66
— доминантный 85
— измеримый 86
— изолированный 70
— конечный 66
— предельный 70
— регулярный 83
— сингулярный 83
— слабо недостижимый 85
— строго (сильно) недостижимый
85
Класс 32
Континуум-гипотеза 73
— обобщенная 73
Конфинальный характер
кардинала 83
Кортеж 30
Лемма Цорна 53
Максимальный элемент
множества 24
Максимум множества 24
Мера Улама 86
Метод моделей 91
Множество бесконечное 57р 71
по Дедекинду 72
— конечное 57р 71
по Дедекинду 72
— натуральных чисел 25
— не более чем счетное 71
— последующее б
— регулярное 7
— сингулярное 7
— счетное 71
— универсальное 89
— фундированное 13
Модель теории 91
Мощность множества 66
Образ множества относительно
функции 20
Определяемая часть множества 15
Определяемого отображения
область значений
относительно множества 18
Определяемое отображение 17р
21, 34
Ординал 37
— последующий 41
— предельный 41
Отношение 22
— эквивалентности 23
Отображение 34
102
ПРЕДМЕТНЫЙ указатель
Переменные 4, 14
Подкласс 34
Подмножество класса 34
Порядковый тип 44
Принцип сквозной цепи 74
Прогрессивное множество 26
Произведение вполне
упорядоченных множеств 32
— кардиналов 80
— линейно упорядоченных
множеств 30
— ординалов 47р 51
Прообраз множества
относительно функции 20
Прямое произведение множеств
17, 29
Ранг множества 90
Синглёт б
Степень кардиналов 82
Сужение отображения 21
Сумма вполне упорядоченных
множеств 29
— кардиналов 79
— линейно упорядоченных
множеств 29
— ординалов 47
Сюръекция 19
Теорема Кантора 67
— Кантора—Бернштейна —Шредера
64
— Цермело 53
— о квадрате 77
мощности предела цепи 75
рекурсивных определениях
43
сумме 78
— об алефах 68
изоморфизме классов
ординалов 71
Транзитивное множество 27
Универсум 89
Упорядочение линейное 23
— полное 25р 34
— частичное 23
Упорядоченная пара 16
Фактор-множество 23
Формула 4
— Бернштейна 83
— Хаусдорфа 83
— атомарная 4
Функции область значений 19
определения 19
— сужение 20
Функций суперпозиция 20
Функция 19
— обратная 20
— тождественная 20
Цепь 25
— сквозная 25
Эквивалентность множеств 57
Универсальный класс 89
Николай Игоревич Казимиров
ВВЕДЕНИЕ В АКСИОМАТИЧЕСКУЮ
ТЕОРИЮ МНОЖЕСТВ
Редактор
Подписано к печати xx.xx.2000.
Формат 60 х 90 ^
Бумага типографская №1.
Гарнитура литературная. Высокая печать.
Усл. печ. л. 6.9 Уч.-изд. л. 7
Тираж ххх экз.
Издательство (не опр.)