James M. Henle
An Outline of
Set Theory
Springer-Verlag
New York Berlin Heidelberg
London Paris Tokyo
Дж.Хенл
ВВЕДЕНИЕ
В ТЕОРИЮ
МНОЖЕСТВ
Перевод
с английского
С.И. Травкина
Под редакцией
В.Б. Кузьмина
МОСКВА
«РАДИО И СВЯЗЬ-
1993
<а’к, +	+ ... +	+ ... + (n-
-l))<a3k, + a3-i(n-l)s<a3k, + Qs’°us(k,+ l)-fn((kt + l)‘n3).
10.4
fn+](gn+i(m)) ’°!n+2(Sn+i(gn(m)) ~ l)<fn+2(Sn+1(gn(m))) -fa+I(g„(m)).
10.1. Если для некоторого числа т последовательность gjfm),
gj(m)... могла бы быть продолжена неограничено, то мы бы получили
бесконечно убывающую последовательность ординалов:
Ъ(8з(т))>/^з(т)}>/^4(т))>...,
что невозможно.
5W'
ОГЛАВЛЕНИЕ
Предисловие .	5
Введение...........................	6
ЧАСТЬ I. ЗАДАНИЯ...................10
Глава 1. Логика и теория множеств...............................
Глава 2. Натуральные числа......................................
Глава 3. Целые числа.............................................. ^9
Глава 4. Рациональные числа........................................“*
Глава 5. Действительные числа...................................
Глава 6. Ординалы...............................................
Глава 7. Кардинальные числа.....................................
Глава 8. Универсальное множество ...............................
Глава 9. Выбор и бесконечно малые числа.........................
Глава 10. Теорема Гудстайна........................................3'
ЧАСТЬ II. УКАЗАНИЯ...............................41
Глава 1.	Логика и теория множеств.................................41
Глава 2.	Натуральные	числа........................................44
Глава 3.	Целые числа..............................................45
Глава 4.	Рациональные	числа.......................................47
Глава 5.	Действительные числа.....................................49
Глава 6.	Ординалы.................................................52
Глава 7.	Кардинальные числа.......................................56
Глава 8.	Универсальное множество..................................64
Глава 9.	Выбор н бесконечно	малые числа...........................64
Глава 10. Теорема Гудстайна........................................72
ЧАСТЬ III. РЕШЕНИЯ...........................74
Глава 1. Логика и теория множеств.........................
Глава 2. Натуральные числа................................
Глава 3. Целые числа......................................
Глава 4. Рациональные числа...............................
Глава 5. Действительные числа.............................
Глава 6. Ординалы.........................................
Глава 7. Кардинальные числа...............................
Глава 8. Универсальное множество..........................
Глава 9. Выбор и бесконечно малые числа...................
Глава 10. Теорема Гудстайна...............................
74
76
80
82
86
88
91
96
99
102

УДК 510.22
Федеральная целевая программа книгоиздания России
Хенл Дж. М. Введение в теорию множеств: Пер. с англ. — М.: Радио и связь, 1993.
— 104 с.: ил. — ISBN 5-256-00485-9.
Книга американского ввтора дает современную трактовку теории множеств, охва-
тывая все основные понятия и проблемы теории, на базе которых можно описывать
явления из самых различных областей науки и жизни. Материал рассчитан на доста-
точно быстрое ознакомление неподготовленного читателя с методами и основными по-
нятиями теории множеств и позволяет эффективно использовать их в практической
работе.
~ Книга представляет интерес для научных работников, связанных с использованием
переборных методов при исследовании проблем, не поддающихся аналитическому
решению.
Может быть полезна инженерам, аспирантам и студентам вузов.
Ил. 4. Библиограф. 1 назв.
Редакция переводной литературы
Научное издание
Хенл Д жеймс М.
ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ
Зшедуххций редакцией Ю. Г. Ившаав.	Редактор И. И- Рюмина.
Обложка художника В. ♦. Громове.	Технический редактор А. Н. Золотарева.
Корректор 3. Г. Галушкина.
ИВ N» 2129
ЛР № 010164
Подписано в печать с оригинал-макета 09.06.93 Формат 60*90/16 Бумага типографская № 2
Гарнитура Пресс-Роман Печать офсетная Усл.печ. л. 6,50 Усл.кр-отг. 6,75 Уч.-изд. л. 6,60
Тираж 1000 зкз. Изд. № 23086 Зак. № 970 С-07? 3504
Издательство "Радио и связь". 101000 Москва, Почтамт, а/я 693
Производственно-издательский комбинат ВИНИТИ. 140010, Люберцы, 10, Московской
обл., Октябрьский просп., 403
ISBN 5-256-00485-9 (рус.)	© 1986 by Springer-Verlag, New York Inc.
ISBN 0-387-96368-5 (англ.)	© Перевод на русский язык, примечания.
ISBN 3-540-96368-5 (ием.)	Травкин С.И., 1993
ПРЕДИСЛОВИЕ
Книга задумана как пособие, рассчитанное на один семестр проблемно-
ориентированного курса теории множеств. Несколько необычное сочетание стиля
изложения и объеме книги требует разъяснений.
Как правило, курсы ориентированы либр на аспирантов, либо на специально
подобранные группы студентов. Однако я обнаружил, что опыт, приобретенный в
результате изучения предложенного курса, оказывается полезным для многих
работающих математиков. При создании курса мною был использован
модифицированный вариант известного метода Р.Л. Мура, развитый в последнее
время Д.В. Коэном* 1. Если быть кратким, то суть нового подхода состоит в том, что
группам студентов ежедневно предлагаются задания. Группы выполняют задания, при
необходимости прибегая к помощи преподавателя, и затем на проводимом раз в
неделю аудиторном занятии делают сообщения о результатах исследований. Основной
упор делается на самостоятельную работу студента (хотя получить консультацию у
преподавателя он может на любой стадии проработки задания), что гарантирует успех'
исследования, позволяет прояснить и критически осмыслить полученные результаты и
подвести участников групповой работы к ясному, математически корректному
изложению результатов проведенных исследований.
Такой стиль проработки курса оказывается наиболее подходящим для изучения
теории множеств. Многие темы книги хорошо известны по учебной литературе, но,
несмотря на всю важность (а порой и глубокий смысл) изучаемых теорем, все же
намного важнее оказываются приводящие к ним идеи и методы теории множеств.
Необходимость вести рассуждения о числах и множествах заставляют студента
вникать в природу доказательства, логику и математику. Проводя исследования,
студенты сталкиваются с теми же дилеммами и неопределенностями, с которыми
приходилось иметь дело и первопроходцам в науке. Нвпример, в процессе работы над
некоторыми частями книги студенты обнаружат, что для исследования им
необходимы гораздо более глубокие сведения, чем те, которые они получили ранее.
Им не всегда удается решить поставленные задачи. Однако они приходят к
пониманию сути доказательства, уясняют себе, как организовать и записать его. Если
лекции, прочитанные на ту же тему, мщут казаться студенту скучными и
/томительными, то попытки самостоятельного решения проблемы сопряжены с
азартом и вознаграждением за успех. Предлагаемые задания выглядят знакомыми и
не отпугивают студента, но в то же время они достаточно разнообразны, чтобы
возбудить его интерес.
При разумном использовании в течение одного семестра собранный в книге
материал должен оказаться избыточным. За один семестр мне обычно удается
прорешать со студентами от 35 до 40 заданий. Три последние главы каждой части
независимы от остального материала. Этот материал можно использовать выборочно
или опустить. Можно пропустить или сократить материалы и некоторых других глав,
в частности нескольких последних разделов гл.7.
Прежде всего я выношу благодарность Дейвиду Коэну за примеры применения его
выдающегося метода обучения и моим студентам за их сообразительность и
безотказное чувство юмора. Я надеюсь, что моя вера в эффективность предлагаемого
подхода не зависит ни от выбора преподавателя, который может преуспеть при любом
методе преподавания, ни от уверенности в том, что студент может выдержать любой
режим обучения. Я очень ценю поддержку, оказанную мне Колледжем Смита, и
одобрение со стороны дружного коллектива его математического отделения. Выношу
благодарность и Марсии Грожек за подобранную цитату Теннисона и особую
благодарность Карлосу Ди Приско за его очень своевременные предложения и советы.
Дж.М.Хенл
1 D.W.Cohen. A. Modified Moore Method for Teaching Undergraduate Mathematics. — 
Am. Math. Monthly, V.89, No.7, 1982.
5
ВВЕДЕНИЕ
Возраст теории множеств как ветви математики не более ста лет, но
она заняла уникальное и, можно сказать, критическое положение в
этой науке. Методы и принципы теории множеств пронизывают всю
математику. Результаты, достигнутые в теории множеств, потрясли
миры математического анализа, алгебры и топологии. Простые вопро-
сы о природе множеств раскололи математическое сообщество на
враждующие лагеря, а романтика бесконечных множеств зачаровыва-
ла и бросала вызов философам как никакой другой аспект математики.
НЕМНОГО ИСТОРИИ
Математика - это живой организм, развивающийся в соответствии с
появляющимися запросами и в зависимости от складывающихся
обстоятельств. Поэтому время от времени должна возникать пауза,
когда можно упорядочить сведения и еще раз задуматься о том, что же
все-таки мы понимаем под математикой и как возникают математи-
ческие результаты. Такое случилось в шестом столетии до нашей эры,
когда Евклид был убежден в том, что ему удалось вывести болыпинст^
во из известных к тому времени результатов из пяти основных посту-
латов. И почти такое же положение сложилось к концу девятнадцато-
го столетия. Развившиеся математические структуры и методы остави-
ли Евклида далеко позади, и возникла необходимость выяснить, что
же имеется в виду под понятиями числа, доказательства и существо-
вания.
Поиски основополагающих принципов естественным путем приве-
ли математиков к понятию множества. А в начале двадцатого столе-
тия обнаружилось, что, по существу, все математические теории
можно изложить в терминах теории множеств. Но гораздо существен-
нее то, что при этом на поверхность всплыл целый сонм критических
вопросов, непосредственно касающихся понятия множества.
Понятие множества тогда казалось базисным и несложным. Поэто-
му проблема твердого обоснования математики считалась вопросом
простого сведения к теоретико-множественному представлению. К
сожалению, такой наивный подход к теории множеств вел к непри-
ятностям.
6
Наиболее впечатляющий пример трудностей, возникающих при
таком подходе, был приведен в 1901 г. Бертраном Расселом. В то время
считалось, что любая совокупность объектов, которая допускает
описание, должна быть множеством. Предположим, что так оно и есть,
и обозначим через R совокупность всех множеств, которые не содер-
жат в качестве элемента самих себя. Условимся записывать высказы-
вание ”х есть элемент у” в виде х&у, а то, что ”х не элемент у” - в
виде х^у. Тогда определение множества R можно записать так:
R = {x\x<£x}.
Будет ли R^Rt Если да, т. е. R&R, то по определению множество
R не есть элемент множества R, т. е. R&R. Но если R^R, то R есть
множество, которое не содержит само себя в качестве элемента, и,
значит, R&RI Мы пришли к противоречию, из которого нет выхода,
разве что не считать R за множество.
После возникновения таких проблем потребовались десятилетия
для того, чтобы сформировался набор основных принципов или
аксиом, который, как казалось (и кажется до сих пор), был бы свобо-
ден от парадоксов. Эта система аксиом называется теорией множеств
Цермело-Френкеля или ZF-теорией, названной в честь ее создателей
Эрнста Цермело и Абрахама Френкеля. ZF-теория занимает стратеги-
ческую позицию во всей математике, и все большее число математи-
ков вовлекаются в ее изучение. Отцом современной теории множеств
был Георг Кантор.
НЕМНОГО ФИЛОСОФИИ
Исследования по теории множеств породили многочисленные разно-
гласия в вопросах обоснования математики. Ведь выбор той или иной
системы аксиом в некотором смысле узаконивает понятие математи-
ческой истины. Не все математики согласны сделать тот или другой
выбор. По этому поводу возникали частые и порой горькие диспуты,
особенно относительно существования бесконечных множеств и
использования бесконечных методов.
Некоторые из математиков (платоники) считают, что аксиомы
должны быть либо истинными, либо ложными, другие (формалисты)
утверждают, что истина - понятие относительное, что абсолютной
истины не существует. Они говорят, что аксиомы - это вроде правил
игры. И в данном случае правила выбраны неплохо, поскольку позво-
ляют игрокам исследовать все области математики.
Философские споры о пригодности теории множеств, в частности
теории Цермело-Френкеля, не утихают до сих пор, но уже появилась и
7
другая группа ученых, которые поставили под вопрос сам вопрос о
необходимости обосновывать математику. Они провозглашают, что
математика не нуждается в определении: она просто существует.
Математика - это то, что наша цивилизация понимает под этим сло-
вом. Ее сущность меняется по мере развития и отражает нашу культуру.
НАШИ НАМЕРЕНИЯ
Мы намерены познакомить вас с теорией Цермело-Френкеля и с тем,
как она помогает избежать парадокса Рассела. Преследуя эти цели,
воспользуемся понятием множества для построения таких разделов
математики, как теории натуральных, целых, рациональных и дейст-
вительных чисел.
Мы рассмотрим в различных формах математические аспекты
понятия бесконечности. В процессе этого исследования придется
столкнуться с многими вопросами, которые озадачивали и вели к
разногласиям математиков нашего столетия. Закончим построением
некоторой теории множеств, созданной ради самой теории множеств,
некоторыми новыми аксиомами, некоторыми большими множествами,
некоторыми приложениями бесконечных методов к теории конечных
множеств, дискуссией по поводу аксиомы выбора и введением в
нестандартный анализ.
НАШ МЕТОД
Надо сказать несколько слов о способе организации материала книги.
Основные идеи теории множеств изложены в части I в виде 44 заданий.
Для выполнения заданий потребуется, чтобы читатель проявил себя
как математик. Как правило, в заданиях приведены лишь формули-
ровки теорем и определения, но не доказательства. Иногда опущены
даже определения! Часть II содержит пространные комментарии и ряд
наводящих соображений. Полные, хотя и краткие, решения поставлен-
ных задач приведены в ч. III.
Зачем мы все это делаем?
Мы верим, что нет лучшего способа изучить математику, чем
делать это самим: искать и находить математические факты, система-
тизировать и корректно выписывать найденные результаты. Мы верим
в способность читателя выполнить большую часть предложенной
ему работы, возможно, с помощью руководителя. Мы верим, что
читатель с удовольствием примет наш вызов.
8
ВАШИ ПРИСТРАСТИЯ
Надеемся, что наши пристрастия не сказались на построении курса.
Несмотря на то, что большинство математиков расходятся в мнениях о
роли теории множеств в математике, все же многие из них признают,
тго построение числовых систем методами теории множеств является
значительным достижением в науке и многое раскрывает в природе
математических исследований. Наблюдается и общее согласие о
зажности теоретико-множественных идей для развития математики.
Платоники не будут раздражены экстравагантными требованиями
признать за истину аксиомы Цермело- Френкеля или какие-то другие.
Формалисты должны остаться довольны нашей строгой привержен-
ностью к ZF-теории. Современные философы, возможно, тоже нас
одобрят, поскольку наш метод отражает органический процесс разви-
тия математики. В некоторых случаях читателю придется доказать
приведенные в задании теоремы, в других - найти формулировки
теорем и выявить соответствующие структуры. Время от времени вы
столкнетесь со случаями, когда для того, чтобы справиться с заданием,
например с доказательством теоремы о рациональных числах, потребу-
ется вернуться на несколько шагов назад и доказать теорему сначала
для целых или даже натуральных чисел, а для этого - соответствующую
теорему о множествах, которая раньше не казалась Вам важной. Все
это очень похоже на то, как в действительности развивалась матема-
тика.
2-3504
ЧАСТЬ I
ЗАДАНИЯ
Глава 1
ЛОГИКА И ТЕОРИЯ МНОЖЕСТВ
Наиболее четкие и прекрасные утверждения какой-либо
истины в конце концов должны принять математичес-
кую форму. Как и в арифметике, мы можем настолько
упростить правила философии морали, что одна форму-
ла сможет выразить и то, и другое.
Г. Д. Торо
Цель этого раздела книги - познакомить читателя с логическими
обозначениями и большинством аксиом теории множеств Церме-
ло-Френкеля. Будет показано, как с помощью множеств могут быть
построены такие важные математические объекты, как функции или
отношения. И раз уже мы решили строить математику на основе
теории множеств, то саму теорию множеств построим на основе поня-
тий математической логики.
ЯЗЫК ТЕОРИИ МНОЖЕСТВ,
Основные символы:
=	-	равенство,
е	-	принадлежность,
1	-	не (отрицание),
а, Ъ, с,z -	переменные,
А	-	и,
V	-	или,
-*	-	следует (влечет),
♦*	-	тогда	и только тогда, когда,
V	-	для всех,
3	-	существует,
(,)	-	круглые скобки
ю
Символы используются для формирования высказываний или
построения формул по следующим правилам.
1.	Основные высказывания - это высказывания вида а=Ь, а^Ь
(переменные а и b могут быть заменены любыми другими перемен-
ными).
2.	Составные высказывания; если <р и ф - высказывания, то:
а) 1 <₽ - тоже высказывание и
б)(фЛф),
в)(ф7ф),
г)(ф-Ф) и
д) (ф ** Ф) - тоже высказывания.
Если ф(х) - высказывание, в котором что-то утверждается о пере-
менной х, то:
е)Ух(ф(х)) и
ж) Эх(ф(х)) - высказывания (переменная х может быть замене-
на любой другой переменной).
Приведенные высказывания имеют следующую интерпретацию:
] <р - истинно тогда и только тогда, когда ф ложно;
ф д ф - истинно тогда и только тогда, когда одновременно истинны
оба высказывания Ф и ф;
ф V ф ~ истинно тогда и только тогда, когда при любых х выс-
казывание ф (х) истинное,
Ф -►ф	- истинно тогда и только тогда, когда истинно высказы-
вание ф либо ложно высказывание ф,
ф ф - истинно тогда и только тогда, когда оба высказывания
либо одновременно истинные, либо одновременно
ложные,
Vx(<f(x)) - истинно тогда и только тогда, когда при любых х,
высказывание <f(x) истинное,
Эх(ф(х)) - истинно тогда и только тогда, когда высказывание
ф(х) истинное относительно хотя бы одного х.
Примеры. Выразить, что:
Ь есть одновременно элемент множества d и множества q, можно, записав
(berfAbeq);
р и h различные:
Ip = h;
множество г ие имеет элементов:
11
2'
множество и естьподмножество множества t:
V j (jeu^jet);
множество z состоит ровно из одного элемента:
3i V m(msz*-m = i).
ЗАДАНИЕ 1. В этом упражнении предположим, что существуют
только следующие множества:
a = {b,c}, b = { }, d = {c, е}, е = {Ь}.
Это означает, что множество а состоит только из элементов b и с и что
множество b не имеет элементов вообще, и т.д.
1.	Определите, какие из следующих высказываний истинные:
а)	Ь&е; б) e^b; e)b^d; г) (a&cVc&d); д) (b^c-a^a);
е)	(e^d**d&e); ж) (е^сЛа^с); з) Vx~](x&b); vL)'iq(q^c^-q^a);
к)	Vn(n^e-*n^a);	n)3k(k^d); м) Vs3t(s^t); H)Ys3t(tes);
о) 3hVi((iee-*ieh)A(]h = е)); п) 3g3w((g&er\w^e)r\~\g = w).
2.	Объясните с помощью правил 1 и 2, почему два последних
выражения можно считать высказываниями.
Обозначения. Чтобы обогатить язык £, введем дополнительные
символы: П, U, \, е, <=, ¥=, Ф, {,}.
(аПЬ) - пересечение множеств а и Ь, т. е. совокупность всех элемен-
тов, которые одновременно принадлежат и множеству а, и
множеству Ь.
(cUd) - объединение множеств с и d, т. е. совокупность всех элемен-
тов, которые принадлежат либо множеству с, либо множеству d.
(e\f)	- совокупность всех элементов из множества е, которые не
принадлежат множеству /.
(g-h) - множество g есть подмножество множества h, т. е. любой
элемент из g принадлежит и множеству h.
Gcj) ~ i-собственное подмножество множества;
(i^j, ноЮ =/У.
(k*l) -l(k-l).
(m<£n) ~1(теп).
{о, р, q}~ множество, состоящее только из элементов о, р и q.
Можно понимать эти символы как сокращения в записи высказы-
ваний. Например, высказывание Ух((х^аЛхеЬ)-*хес) теперь можно
записать как а Л Ь^-с.
И еще одно сокращение: высказывание ((фАф)Лх) о высказывани-
ях ср, ф и х будем записывать ф Л ф Л х; аналогичное сокращение будем
использовать и для связки V.
ЗАДАНИЕ 2. При выполнении следующих упражнений предполо-
12
жим, что во всей вселенной существуют только множества:
о = { }> b = {d,a}, с = {а,е), d = {a,e,c), е = {о) и/ = {а, b, с, d, е).
Приведенные ниже высказывания описывают множество х. В каждом
из упражнений множеством х может оказаться только одно из мно-
жеств а, Ь, с, d, е или f. Какое?
а) х^е; б) x*f; в) d=x; r)f^x; д) х^а; е) Vy(y^x); ж) 3zfzexAVw
(w«x^w=z); з) (x^bAx+d); и)1 (х^с^х^Ь); к) V q(x*q); л) е =
= {а,х); м) х = {{ }}; н) (x$d**xo.d); о) 3 h 3J(h^j Л J^dAx^h);
п) Vn 1п<=х; р) 3r(Vu ифг Л г^х); с) 3 v(v^x Л V к(к<=х->к = v));
т) 3q3h3i3j(j^iAi'^hAh^gAg&x); у) 3y3z((y&zAz^x)Ay$x);
ф) 3q 3r3s((q^xAr^xAs^xAq =# rAr±s)Aq * s А V t(t^x~>(t = q Vt*
tV t = s))).
Иногда будем использовать еще более богатый язык £+.
Определение. это язык, полученный из языка £ добавлени-
ем постоянного символа для каждого множества.
НЕСКОЛЬКО АКСИОМ ТЕОРИИ ЦЕРМЕЛО-ФРЕНКЕЛЯ (ZF-ТЕОРИЙ)
Аксиома экстенсиональности. Два множества равны тогда и только
тогда, когда они состоят из одних и тех же элементов.
Аксиома пустого множества. Существует множество, не содержа-
щее элементов.
Аксиома пары. Если си d- множества, то {c,d} - множество.
Аксиома объединения. Если d - множество множеств, то объеди-
нение этих множеств есть множество.
Аксиома степенного множества. Если d - множество, то совокуп-
ность всех подмножеств множества d есть множество, которое называ-.
ется степенным множеством множества d.
Аксиома регулярности. Если d - множество, то либо d = { }, либо в
d найдется элемент Ь, такой, что d П Ь = { }.
В ранних построениях теории множеств затруднения возникали
из-за того, что множеством считалась любая определяемая совокуп-
ность. Принимая следующую аксиому, мы ограничиваемся рассмотре-
нием только таких определяемых совокупностей, которые содержатся
в некотором множестве (и потому не слишком больших).
Аксиома содержательности. Если D - множество, то любая опреде-
ляемая часть D есть множество. Если <р(х) - формула языка £+ , то
совокупность всех элементов х множества D, таких, что <р (х) - истин-
ное высказывание, называется определяемой частью множества D.
Будем записывать это множество в виде
{xeD\<f(x)}.
13
(Аксиома содержательности позволяет назвать эту совокупность
множеством.)
ЗАДАНИЕ 3. Запишите первые шесть аксиом ZF-теории на языке £,
используя любые введенные выше сокращения.
Важное замечание! Языки £ и £+ введены для применения во
вполне определенных ситуациях, и аксиома содержательности дает
первый пример такого применения. В остальных случаях используется
обычный (русский) язык. И хотя некоторая часть наших рассуждений и
может быть переложена на язык £ , но заниматься этим было бы
неразумно. Прочитать написанное оказалось бы не очень просто! По
этой причине вас никто не обязывает выписывать доказательства на
языке £. Доказательства должны быть понятными и такими, чтобы
их можно было оценить, а следовательно, их надо писать на том
языке, который более всего пригоден для этих целей.
ЗАДАНИЕ 4. Докажите следующие теоремы.
1.1.	Теорема. Пусть А и В - множества; тогда А ЛВ - множество.
1.2.	Теорема. Пусть А иВ- множества; тогда AUB- множество.
1.3.	Теорема. Пусть А - множество; тогда {А} - множество.
1.4.	Теорема. Пусть А - множество; тогда А ФА.
13.	Теорема. Пусть А иВ- множества иАеВ; тогда А ФВ.
1.6.	Теорема. Множество, не содержащее элементов, определено
однозначно.
1.7.	Теорема.'Множества, описанные в аксиомах объединения и
степенного множества, определены однозначно.
Обозначения (добавление к языку Z). Пусть Ф - обозначение для
множества { } - единственного множества, которое не имеет элемен-
тов. Для произвольного множества d, определенного аксиомой объеди-
нения, введем обозначение Ud. И пусть P(d) обозначает множество,
определенное аксиомой степенного множества.
ЗАДАНИЕ 5. Задача заключается в том, чтобы по заданным мно-
жествам а и b определить множество, представляющее упорядоченную
пару <а,Ь>. Пара должна быть множеством (все должно быть множест-
вом) и обладать свойством <a,b> = <c,d> тогда, и только тогда, когда
одновременно и а = с, и b = d. Приведем несколько определений:
{a,b}; (ajb)}; {{а}, {&}}; {{а},{а,Ь}}; {а,Ь, {а,Ь}},
но только одно из них верное. Найдите его, докажите, что это действи-
тельно определение множества, и покажите, почему другие определе-
ния неверны.
Определение. А X В - совокупность всех упорядоченных пар
< а,Ь>, таких, что аеВ и Ь^В.
14
Докажите следующие теоремы.
1.8.	Теорема. Пусть А иВ- множества; тогда АХ В - множество.
Обозначения. В качестве сокращений добавим к языку £ обозна-
чения <а,Ь> и А X В.
Определение. Функцией f из множества А в множестве В называет-
ся подмножество в АХ В, такое, что:
а)	если хе А, что существует элемент у, такой, что <х,у> ef;
б)	если <х,у> и <x,z> принадлежат функции [, то у = z.
Обозначение. На языке £ высказывание <х,у> е/ будем записы-
вать в виде/(х) = у.
Определение. Если / - функция из множества А в множество В, то
А называется областью определения функции [. Множеством значений
функции называется множество {y^B\3xf(x) = y}. Функция f называ-
ется взаимно однозначным соответствием в том, и только в том
случае, если всякий раз, когда f (х) = f (у), имеет место равенство
х = у. Функция [ называется отображением на, если область ее значе-
ний совпадает с множеством В. Пусть DS.A, тогда f ID (суждение / на D)
обозначает множество {<х,у> «*/1x^0}.
Докажите следующие теоремы.
1.9.	Теорема. Пусть f - функция; тогда ее область определения есть
множество.
1.10.	Теорема. Пусть [ -функция, D - множество; тогда f | D есть
множество.
1.11.	Теорема. Если f - взаимно однозначное отображение из
множества А в множество В, то f есть взаимно однозначное отобра-
жение из множества В в множество А.
Определение. Отношением R на множестве А называется подмно-
жество в АХ А.
Обозначение. Вместо < a, b>®R на языке £ будем писать aR b.
Определение. Отношение R, определенное на множестве А, назы-
вается рефлексивным, если для всех х из множества А выполняется
xRx. Отношение R называется симметричным, если из xRy следует
yRx. Отношение R называется транзитивным, если всякий раз, когда
xRy и yRz, имеет место xRz. Отношение R называется отношением
эквивалентности тогда, и только тогда, когда оно транзитивное,
рефлексивное и симметричное.
Обозначение. Если R - отношение эквивалентности на множестве
А и аеД, то вместо (beA I aRb} будем писать [а]д (это множество
называется классом эквивалентности элемента а).
ЗАДАНИЕ 6. Докажите следующие теоремы.
1.12.	Теорема. Пусть R - отношение эквивалентности на множест-
ве А и а^А; тогда [а] - множество.
15
1.13.	Теорема. Пусть R - отношение эквивалентности на множест-
ве Айа, Ь^А; тогда либо [aj^lb]# либо [a]Rfl [b]R = <fi.
1.14.	Теорема. Пусть R - отношение эквивалентности на множест-
ве А; тогда совокупность классов эквивалентностей множества А есть
множество.
Глава 2
НАТУРАЛЬНЫЕ ЧИСЛА
В созерцании бесконечности человек достигает величай-
шего добра.
Джордано Бруно
В этой части мы намерены ввести числа 0, 1, 2, определив их в
терминах множеств. Для полноты картины нам надо будет показать,
как складывать и умножать эти числа, и доказать все обычные законы:
коммутативности, ассоциативности и т. д. В таком построении содер-
жится очень важная идея - идея математической индукции.
Однако вначале потребуется аксиома, определяющая достаточно
большое множество, чтобы можно было построить натуральные числа.
Набор до сих пор введенных аксиом слишком слаб для гарантии
существования бесконечного множества.
Определение. Пусть Sfx) = xU {х} для любого множества.
Обозначение. К языку :£ добавим множество S.
Аксиома бесконечности. Существует множество X, такое, что:
1) 0 ®Х; 2) если у ®Х, то S (у) &Х;
3) если у«Х и у=#0, то для некоторого элемента z^X имеет
место у=S(z).
Как подсказывает интуиция, любое множество, которое соответст-
вует этим условиям, будет бесконечным, поскольку в нем должны
содержаться по крайней мере множества 0,	S(($)), S(S(S(0))),
.... Полное обсуждение понятий конечного и бесконечного множеств
отложим до гл. 7.
ЗАДАНИЕ 7. Докажите следующие теоремы.
2.1.	Теорема. Если х - множество, roS(x) - множество.
2.2.	Теорема. Существует только одно множество, удовлетворяю-
щее условиям 1-3.
Определение. Единственное множество, удовлетворяющее услови-
ям 1 - 3, называется множеством натуральных чисел N •
Определение. 0 = 0; 1 =S(0);2 = S(l);3 = S(2);4 = S(3).
16
Выпишите множества 0, 1, 3 и 4, пользуясь только символами
*’{”» и
Докажите следующие теоремы.
2.3.	Теорема. Множество N удовлетворяет аксиомам Пеано:
a)0eN ;
б)	для всех элементов N высказывание S(k) - истинное;
в)	для всех элементов fce М
S(k)*G;
г)	для всех пар элементов j, k^ N
S(j) =S(k) тогда и только тогда, когда] = к.
д)	если ХьМ и 0еХ и если для всех элементов к& М из условия
к^Х следует S(k)^X, то X = Ы 
2.4.	Теорема (Принцип индукции). Если высказывание (р(к)в £
1) истинное относительно 0, и
2) всякий раз, когда оно истинное относительно числа k, к^ N ,
оно оказывается истинным и относительно множества S(k), то выска-
зывание <₽ (к) - истинное относительно всех элементов ke М .
Определение сложениям Сложение можно описать как функцию А
из в N . Можно, например, считать, что 2+3=5 - это другая запись
утверждения А (2,3)=5. Функция А должна обладать по крайней мере
двумя свойствами:
1)	А(<п,0>) = п,
2)	A(<n,S(k)>) = S(A(<n, к>)).
Если за S(fc) принять к+1, то согласно выписанным законам п+0=п
и п+(к+1) = (п+к)+1. Удивительно, что доказать существование такой
функции оказывается совсем непросто.
2.5.	Теорема. Существует функция, удовлетворяющая условиям
1 и 2.
Доказательство теоремы не просто и приведено в конце главы.
Обозначения. Вместо А( <а,Ь >) = с (или еще менее удачной записи
«а,Ь >, с ><=А) будем писать а+ = с.
ЗАДАНИЕ 8. Докажите следующие теоремы.
2.6.	Теорема. Операция + N - ассоциативная.
2.7.	Теорема. S(n) = п+1 при любом n <= N.
2.8.	Теорема. 0+	= п при любом п SN.
ЗАДАНИЕ 9. Докажите следующие теоремы:
2.9.	Теорема. Операция + N- коммутативная.
2.10.	Теорема. 2+ ^2 = 4.
Выбор буквы А дпя обозначения функции мотивирован словом addition - еложе-
те. - Прим. перев;- -	-	...—_—. - -
Ai I Л А о I
Определение умножения. Мультипликативная функция1 М из
N х№ N должна удовлетворять условиям:
i)Mf<n,o>;=o,
2} М( <n, S(k) J = М( <п, к >)+ N п.
2.11.	Теорема. Существует функция, удовлетворяющая условиям
1 и 2.
Обозначение. Вместо М( <а,Ь >) = с будем писать a-Nb = с.
ЗАДАНИЕ 10. Докажите следующие теоремы:
2.12.	Теорема. n-N(m + Np) = (п- Nm)+ N(n-Np) при любых п, т,
Р eN.
ИЗ. Теорема. Для любых п ^^выполняется п-ы1 = п.
2.14.	Теорема. Операция • N - ассоциативная.
ЗАДАНИЕ 11. Докажите следующие теоремы.
2.15.	Теорема. Операция • N - коммутативная.
2.16.	Теорема. (n + Nm)-Np = (n-Np)+N(m-Np)npn любых п, т, ре!Ч
2.17.	Теорема. 2-N2 = 4.
Определение. Отношение R на множестве А называется антиреф-
лексивным тогда и только тогда, когда -\xRx при любых хеА.
Отношение R удовлетворяет условию трихотомии тогда и только
тогда когда для любых х, уеА истинно одно, и только одно из выска-
зываний xRy, yRx или х - у. Отношение R называется частичным
упорядочением, если оно антирефлексивное и транзитивное. Частич-
ное упорядочение называется линейным упорядочением, если выпол-
нено условие трихотомии.
Определение. Относительно любых элементов х, будем
говорить, что х <N у тогда и только тогда, когда существует элемент
k е N, такой, что x+N S(k) = у.
ЗАДАНИЕ 12. Докажите следующие теоремы:
2.18.	Теорема. При любых элементах х, оз того, что х<ыу,
следует х^у.
2.19.	Теорема. Отношение <N задает линейное упорядочение на
множестве N.
ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 2.5.
Определение. Скажем, что функция А суммируема вплоть до
числа т, если она удовлетворяет условиям:
1)	А(<п,0>) = п,
2)	для всех fcem и пе^ выполнено условие A(<n,S(fcJ>J =
= Sf4f<n,fc>A
1 Выбор буквы М для обозначения функции мотивирован словом multiplication — ум-
ножение. —Прим, персе.
18
Сначала докажем, что для любого числа т существует функция,
которая суммируема вплоть до числа т.
Функция из N XNв N есть подмножество b(N XN)x N. Рассмотрим
совокупность множеств «п,0>,п> при всех пеМ , которая есть
определяемое подмножество множества (М x N) х N и, как легко
видеть, удовлетворяет условию 1. Поскольку не существует элемента
кеО, то нет необходимости проверять выполнение условия 2, и,
значит, эта функция суммируема вплоть до числа т.
Теперь допустим, что построена функция, которая суммируема
пплоть по числа т. И пусть А+ означает функцию, состоящую из:
а)	всех упорядоченных пар в А и
б)	всех упорядоченных пар вида <<n,S(m)>, S(A(<n,m>)).
Эти условия гарантируют, что функция А+ суммируема вплоть до
числа S(m), поскольку если k^S(m), то либо kem,
и тогда условие а) показывает, что функция А+ действует так же, как
функция А, либо к=т, но тогда согласно условию б) функция А+ удо-
влетворяет условию 2.
Наконец, пусть А' состоит из всех множеств вида <<n,k>,d>,
таких, что А (<п, к>) =d, где А - некоторое множество, суммируемое
вплоть до числа к.
Понятно, что множество А' удовлетворяет обоим условиям 1 и 2.
Область определения функции А' - все множество N X.N.Единствен-
но, что осталось выяснить, будет ли А' действительно функцией? А
вдруг функции А х и А 2 суммируемы вплоть до
к (или более) и для некоторого числа п окажется, что А1(<п,к>) =
»А2(<п,к>7? Если такое произойдет, то мы получим два различных
значения для А'(<п, к>).
Пусть X будет множеством всех таких чисел к. Покажем, что Х=0
и тем самым что А' - действительно функция. Во-первых, ОеМ\Х
поскольку
Ах(<п,0>)”п =А2(<п,0>).
Далее, если кеМ\Х, то S(k)eN\X, так как A1(<n,S(k)>)s!!S(A1'X
Х(<п,к>)) = S(A2(<n,k>)) = A2(<n,S(k)>). По теореме 2.3в имеем
М\Х =М, и поэтому X = 0.
С помощью очень похожих рассуждений доказывается и тео-
рема 2.11.
19
Глава 3
ЦЕЛЫЕ ЧИСЛА
‘	Бог создал числа. Все остальное дело рук человека.
Леопольд Кронекер
В этой части книги мы построим множество, представляющее положи-
тельные и отрицательные числа. Как и раньше, определим операции
сложения и умножения. В дополнение к свойствам, которыми, как
было доказано, обладает множество 14 получим аддитивные обратные
величины. Ключевая идея построения состоит в использовании клас-
сов эквивалентности.
Начнем с определения отношения ~ на множестве М х N.
Определение. <a,b>~<c,d> тогда, и только тогда, когда a+Nd=
=b+^c.
ЗАДАНИЕ 13. Докажите следующие теоремы.
3.1.	Теорема. Отношение ~ - отношение эквивалентности на
множестве М х М.
Определение. Z (целые числа) - совокупность всех классов экви-
валентностей.
3.2.	Теорема. Z- множество.
Придумайте операцию +z в множестве Z.
ЗАДАНИЕ 14. Докажите следующую теорему.
3.3.	Теорема. Операция + z - коммутативная и ассоциативная.
Определите 0z eZи докажите следующую теорему.
3.4.	Теорема. Для любого элемента а выполняется соотношение
®т+%а = а.
Для каждого элемента a eZ определите элемент ~(а)г и докажите
следующую теорему.
3.5.	Теорема. Для любого элемента а ^^выполняется соотношение
Определите на множестве Z отношение <N и докажите следующую
теорему.
3.6.	Теорема. Отношение есть отношение линейного поряд-
ка на 7L.
ЗАДАНИЕ 15. Определите на множестве Z операцию -z и докажите
следующую теорему.
3.7.	Теорема. Операция  - коммутативная, ассоциативная и
дистрибутивная относительно операции +г.
Определите элемент lz е/и докажите следующую теорему.
3.8.	Теорема. Элемент 1 г есть единица операции -г.
20
Глава 4
РАЦИОНАЛЬНЫЕ ЧИСЛА
Числа — это интеллектуальные свидетельства, которые
принадлежат только человечеству и с помощью которых
возможно постичь смысл слов.
Оворе де Бальзак
Наша следующая цель состоит в построении рациональных чисел.
Метод построения очень похож на тот, который был использован в
предыдущей главе.
ЗАДАНИЕ 16. Определите множество ^(рациональные числа).
ЗАДАНИЕ 17. Определите операцию + q и докажите следующую
теорему.
4.1.	Теорема. Операция+Q- коммутативная и ассоциативная.
Определите элемент 0о. Для каждого элемента х е Qопределите
элемент ~(х)0 и докажите следующую теорему.
4.2.	Теорема. Элемент 0о - единица операции +Q, и для любого
элемента х элемент ~(х)0 есть аддитивный обратный элемент.
ЗАДАНИЕ 18. Определите операцию -0 и докажите следующую
теорему.
4.3.	Теорема. Операция -0 - коммутативная, ассоциативная и
дистрибутивная относительно Операции +Q.
Определите элемент Ц. Для любого элемента xeQ,x / (^опреде-
лите элемент (1/х)0 и докажите следующую теорему.
4.4.	Теорема. Элемент 1Q есть единица операции <j, и для каждого
элемента х е Q, х / 0о обратным мультипликативным элементом
будет (1/х)0.
ЗАДАНИЕ 19.
Определение. Множество Ь>]~ называется положительным
тогда и только тогда, когда 0z <г а Ь.
Множество [<а,Ь> ]и называется отрицательным тогда, и только
тогда, когда а г b <г 0z.
Докажите, что положительные и отрицательные множества опреде-
лены корректно.
Определение. Пусть г, s е ©.Неравенство?- <Q явыполняется тогда
и только тогда, когда s +ц (г)о— положительное множество.
4.5.	Теорема. Отношение <Qecn отношение линейного порядка.
21
Глава 5
ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА
Молодой человек, объекты математики ие понимают, к
ним просто привыкают.
Джон фон Нейман
Построение стандартных числовых систем завершим изучением
подхода к построению действительных чисел, предложенного Деде-
киндом. По разным причинам для такого построения требуется проде-
лать очень большую работу, поэтому ограничимся определениями
R,+r иОк. и обсудим трудности дальнейшего продвижения к цели.
Определение. Сечение1 - это подмножество reQ, такое, что:
1)	г и р<о Увлечет ре г;
2)	в г нет наибольшего элемента;
3)
4)
Определение. R - совокупность всех сечений.
ЗАДАНИЕ 20. Докажите следующую теорему.
5.1.	Теорема. R - множество.
Определите отношение <R и докажите следующую теорему.
5.2.	Теорема. Отношение <ц есть отношение линейного упоря-
дочения.
Определение. Элемент u®R называется верхней гранью множест-
ва № Rтогда и только тогда, когда для любого элемента ЬеХ выпол-
няется условиеb < Ru. Верхняя грань и называется точной верхней
гранью множества X в том и только в том случае, если всякий раз,
когда с - верхняя грань для X, имеет место неравенство и < R с.
Докажите следующую теорему.
53.	Теорема (непрерывность действительных чисел). Если мно-
жествах £ R,X¥=$ имеет верхнюю грань, то оно имеет и точную
верхнюю грань.
Определение. Пусть r,s®R. Тогда г +R s= zесть сумма эле-
мента из множества г с элементом из множества s}.
ЗАДАНИЕ 21. Докажите следующую теорему.
5.4.	Теорема. Если r,seR, то г + R s - сечение.	>
ЗАДАНИЕ 22. Докажите следующую теорему.
5.5.	Теорема. Операция +R - коммутативная и ассоциативная.
Определите 0R и докажите следующую теорему.
5.6.	Теорема. Элемент 0R есть единице операции +н-
1В тексте оригинала автор использует немецкое слово schnitt. - Прим, перев.
22
ЗАДАНИЕ 23 (без доказательств).
Определите для любого элемента гей элемент ~(r)R .
Определите операцию "r.
Для любого элемента r/0Rопределите элемент (l/r)R
Глава 6
ОРДИНАЛЫ
Математик - это слепец в темной комнате, ищущий
черную шляпу, которой в ней иет.
Чарльз Дарвин
Мы хотим расширить множество наших счетных1 чисел до более
широкого класса чисел, которые дали бы возможность пересчитывать
бесконечные множества. Это первый тип бесконечных чисел, предназ-
наченных для измерения ’’длин” больших множеств.
Определение. Линейное упорядочение на множестве X называется
полным упорядочением, если любое непустое подмножество иэ X
имеет наименьший элемент. Множество, на котором введено отноше-
ние полного упорядочения, называется полностью упорядоченным
множеством.
Определение. Множество X, такое, что:
1)	отношение е есть отношение полного упорядочения на множест-
ве X, и
2)	если о® Ь и 6®Х, то аеХ,
> называется ординалом.
Для обозначения ординалов обычно используются греческие
буквы а, Р, у..
ЗАДАНИЕ 24. Докажите следующие теоремы.
6.1.	Теорема. Пустое множество0- ординал.
6.2.	Теорема. Множество N - ординал.
63.	Теорема. Если а - ординал, то S(a) - ординал.
6.4.	Теорема. Если а - ординал иЬ^а,тоЬ- ординал.
Определение. В теории множеств вместо символа М принято
Писать о.
1 Здесь не вводится понятие "счетное число”, а говорится с мотивировке: натуральные
числа нужны для пересчета элементов конечных множеств. — Прим. рей.
23
ЗАДАНИЕ 25. Докажите следующие теоремы.
6.5.	Теорема. Для любых двух ординалов а и ₽ выполняется
а <= р ♦♦ а е р.
6.6.	Теорема. Отношение е есть отношение линейного порядка на
ординалах.
6.7.	Теорема. Отношение е есть отношение полного порядка на •
ординалах.
6.8.	Теорема. Пусть А - множество ординалов. Тогда UA - орди-
нал, определяющий наименьшую верхнюю грань множества А.
6.9.	Теорема. Не существует наибольшего ординала.
6.10.	Теорема. Совокупность всех ординалов не образует мно-
жества.
Определение. Пусть a=S(p) - ординал при некотором р. Тогда a
называется последующим ординалом. Если ординал а Ф 0 не последую-
щий, то это - предельный ординал.
ЗАДАНИЕ 26. Докажите следующие теоремы.
6.11.	Теорема. Ординал м - наименьший предельный ординал.
6.12.	Теорема (трансфинитная индукция). Пусть задана формула Ф
из языка С+, обладающая тем свойством, что если ф(а) - истинное
высказывание при любом ординалу Р, такому, что ф(Р) - истин-
ное высказывание, то ф(₽) - истинное высказывание при любом
ординале Р.
Для формулировки теоремы 6.13 потребуется ввести последнюю
аксиому теории Цермело-Френкеля.
Аксиома замещения. Любое определяемое отображение, область
определения которого - множество, есть функция.
Говоря точнее, если ф(х,у) - формула языка У'4, то ф ’’определя-
ет” отображение, когда для любого элемента х найдется единственный
элемент у, при котором высказывание ф(х,у) оказывается истинным.
Аксиома замещения утверждает, что если D - множество, то сужение
этого отображения на множество D будет Функцией, т. е. {<x,y>\x^D
и 4>(х,у)} - множество.
Одно из преимуществ от включения этой аксиомы в теорию состо-
ит в том, что в этом случае нет необходимости делать различие между
отображениями, заданными с помощью формул (которые не должны
быть множествами) и функциями (которые должны быть множества-
ми). Если формула <р(х,у) определяет отображение (т. е. для каждого
элемента х найдется единственный элемент у, такой, что высказыва-
ние Ф (х,у) будет истинным), то мы можем представлять себе это
отображение функцией, понимая, что такое представление будет
осмысленным только в случае сужения области определения / до
24
множества. Хороший пример дает рассмотрение последующего отобра-
жения S(x) = xU{x}. Это отображение - не функция потому, что его
область определения содержит все множества. Однако поскольку S -
Определяемое отображение, то будет функцией во всех случаях, когда
область определения отображения сужена до множества (например, до
цкожества М).
Этой аксиомой завершается построение теории ZF. Все теоремы,
^доказанные до сих пор, были доказаны только с помощью аксиом
ZF-теории. Позже введем еще несколько аксиом, которые многими
считаются важными, поэтому иногда ими стоит пополнять систему
аксиом ZF-теории. Они не включаются в теорию Цермело-Френкеля
из-за того, что не нашли всеобщего признания, но продолжают прико-
вывать внимание специалистов по теории множеств, алгебраистов,
топологов, философов и вообще всех математиков.
Определение. Совокупность высказываний называется совмест-
ной тогда и только тогда, когда из этих высказываний невозможно
вывести противоречие.
Совместна ли система аксиом ZF? Мы этого не знаем и, возможно,
никогда не узнаем! Известная теорема, доказанная Куртом Геделем в
1931 г. (вторая теорема о неполноте), утверждает, что любая совмест-
ная совокупность высказываний, имеющих некоторые общие характе-
ристики, не может быть доказательством своей собственной совмест-
ности. Конечно, если система аксиом ZF несовместна, то с ее
помощью можно доказать все, что угодно (по той же причине, что
ложное высказывание влечет все, что угодно - гл. 1), и, в частности,
ее собственную совместность!
До конца книги мы примем за постулат, что система аксиом
совместная.
Для большинства из нас это - вполне разумное предположение.
Большинство платоников признают, что система аксиом ZF состоит из
интуитивно истинных высказываний. Теория корректная. Для форма-
листов теория либо совместная, либо нет. Если ’’нет”, то из нее следу-
ет все, что угодно. Поэтому нужно только доказать ее совместность,
тогда ее можно будет признать. Наконец, для исследователей-практи-
ков теория кажется довольно надежной, так как в течение несколь-
ких десятилетий исследований несовместность теории не была
обнаружена.
Определение. Полностью упорядоченное множество <В, <в >
имеет порядковый тип а (где а — ординал) тогда и только тогда, когда
существует однозначная функция f из а в В, которая сохраня-
25
4-3504
ет порядок (т. е. при любых Р, у^а из того, что Реу, следует /($)<
<в№))-
6.13.	Теорема. Порядковый тип любого полностью упорядоченного
множества определен однозначно.
Доказательство приводится в конце главы.
Перейдем к построению арифметики ординалов.
Определение. Пусть « и ₽ ординалы. Тогда ординал а+ р есть
порядковый тип следующего упорядочения:
[Точнее, определим <+ упорядочение на множестве all(ixp);
a<+b тогда и только тогда, когда либо
1) а,Ьеа.цаеЬ,
2)aea, Ь®(1хр), либо
3)a,be(lxp),a = <0,c>, b = <0,d>nc^d.]
Определение. Пусть а и Р - ординалы. Тогда ординал a-0 Р есть
порядковый тип следующего упорядочения:
[, я	а	я
(-----------)(----------)(-----------)---------------
Р
[Точнее, определим упорядочение <о на множестве ахр как <а,Ь>
<0 <с, d> тогда, и только тогда, когда либо
1) bed, либо
2) Ь=</иаес.]
ЗАДАНИЕ 27 (без доказательства). Выясните: будет или нет опера-
ция +0 обладать свойствами коммутативности и ассоциативности;
существует ли единица операции; выполняется ли закон сокращения.
(Если а+ор = у+0Р, то будет ли а = у?) Спрашивается, будет ли верен
левосторонний закон сокращения, если операция +0 окажется неком-
мутативной?
Выясните: обладает ли операция -0 свойствами коммутативности и
ассоциативности; существует ли единица операции; выполняется ли
закон сокращения; будет ли операция •„ дистрибутивной относительно
операции +0.
Обозначение. Принято вместо аеР писать а<Р, поскольку отно-
шение 6 - полное упорядочение на ординалах.
ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 6.13. Сначала нам потребуется
доказать одну очень важную теорему.
26
6.14.	Теорема (о рекурсивных определениях). Для любой функции
/можно указать функцию g, такую, что при любом ординале а:
о тогда. и только тогда, когда а = f((g(fl)l₽ <а}).
Это теорема о построении функции по последовательным уровням.
Операции+N и дают пример таких функций. Другие примеры поя-
вятся при доказательстве теоремы 6.13 в гл. 8,9.
ДОКАЗАТЕЛЬСТВО. Можно определить функцию g формулой
языка^+:У(х,у)=”х-ординал, и существует функция/i, удовлетворя-
ющая условию
h (У ) = f({ h (Р ) I Р < У}) ПРИ любом у < х и h (х) = У’.
Это определение отображения: ибо допустим, что для некоторого
ординала а и множеств у и г оказались истинными обе формулы
ф(а, у) и Ф (а ,z), но при этом у Фг. Тогда существуют две функции hx и
ha , удовлетворяющие условию (*) при/1х (а ) = у и ha(a)=z. Пусть а
будет таким наименьшим ординалом. Тогда
x = ht (а )=/({/1х (р )₽<a} )=/({h2 (р )!₽<«} )=h2 (а )=у
- противоречие. По аксиоме замещения отображение ф определяет
функцию g, которая удовлетворяет условиям теоремы.
Перейдем к доказательству теоремы 6.13. Предположим, что
множество В полностью упорядоченно отношение <в. Применим
теорему о рекурсивных определениях к функции /, когда f(x) опредет
лен? как <в-наименыпий элемент вне х (если такой существует; в
противном случае значение f(x) не играет роли). Пусть g - отображе-
ние, определенное условиями теоремы 6.14 и такое, что g(a.) = а тогда,
и только тогда, когда a =/({g(Р )l Р < a}).
Отсюда следует, что отображение g - взаимно однозначное,
сохраняющее порядок, отображение. В силу взаимной однозначности
отображения g обратное отображение g~1 определено условием
g~1 (a) = а тогда и только тогда, когдаg (а.) = а,
и определение корректное. А так как область определения функ-
ции g~1 содержится в множестве В, то по аксиоме содержательности
она будет множеством. Из аксиомы замещения следует, что g"1 -
функция и отображение g - тоже функция. Область определения
функции g - множество ординалов и поэтому ординал, поскольку
если определено значениеg (а) и Р <а, то определено и значение g(P).
Пусть 6 - область определения функции g и пусть S^B - область
значений. Остается показать, что S = В. Однако если B\S - не пустое
множество, то/(S)&B и, таким образом,
27
4
а это означает, что 6 содержится в области определения g, т. е. 6 = 6,
что, конечно, невозможно.
Глава?
КАРДИНАЛЬНЫЕ ЧИСЛА
Моя, как море, безгранична нежность
И глубока любовь. Чем больше я
Тебе даю, тем больше остается;
Ведь обе — бесконечны .
Уильям Шекспир
В этой главе разовьем теорию еще одной совокупности бесконечных
чисел, предназначенных для измерения размеров (в отличие от длин)
бесконечных множеств.
Определение. Относительно множеств А и В будем говорить, что:
1)	НАН = ВВП тогда и только тогда, когда существует функция,
которая обеспечивает взаимно однозначное соответствие А на В;
2)	IIA II < IIВII тогда и только тогда, когда существует функция из А
в В, т. е. однозначное соответствие;
3)	IIАII<11ВII тогда и только тогда, когда ИА l|<IIВII, но не IIВII <
<11А II.
ЗАДАНИЕ 28. Докажите следующие теоремы.
7.1.	Теорема. R ы II < II S( а) II < II ы II.
7.2.	Теорема. II ы II < || 11| < II о К.
7.3.	Теорема. II ы II < || Q ||< R о R.
ЗАДАНИЕ 29. Докажите следующие теоремы.
7.4.	Теорема (теорема Шредера- Бернштейна). Бел и Н А И -< IIВ IK И А R,
то НА 11 = НВII.
7.5.	Теорема. || to || = ||Z|| = ||Q||.
ЗАДАНИЕ 30. Докажите следующие теоремы.
7.6.	Теорема (Георг Кантор, 1874). Для любого множества А выпол-
няется НА R < ПР(А) II.
7.7.	Теорема (Георг Кантор, 1874) || ы II < || R ||.
Определение. Если для любых р < а имеет место неравенство
У. Шекспир. Ромео и Джульетта, акт П, сц. 2 Пер. Т. Щепкииой-Куперник./Полн. собр.
соч. Т. 3. — М.: Искусство, 1958. — С. 46. — Прим, перев.
28
IРII< Hail,то ординала называется кардинальным числом. Обычно
для представления кардинальных чисел используется древнееврейс-
кая буква К.
7.8.	Теорема. Если А - множество кардинальных чисел, то U А есть
кардинальное число.
7.9.	Теорема. Множество $(<о) - не кардинальное число.
*	7.10. Теорема. Следующие утверждения эквивалентны между
собой.
1.	Аксиома выбора (АС): для любого множества А существует функ-
ция f (называемая функцией выбора) на множестве А, такая, что
f(x)&xnpu всех х^ А, таких, чтохфф.
2.	Лемма Цорна: если Р=£0 - частично упорядоченное отношением
<р множество, такое, что любая его цепь (т. е. подмножество CsP,
такое, что отношение <р есть отношение линейного порядка на С)
ограничена (т. е. найдется элемент х&Р, такой, что для всех у&С
выполняется неравенство у^рх), то в множестве Р имеется макси-
мальный элемент (т. е. элемент х^Р, такой, что ни для какого у из Р
неверно, что х <ру).
3.	Теорема Цермело или теорема полного упорядочения: любое
множество может быть полностью упорядочено.
Доказательство теоремы будет приведено в гл. 9.
Рядом математиков аксиома выбора рассматривается как сущест-
венная часть теории выбора и, вообще, всей математики. Другие же
относятся к ней иначе: либо считают ее вполне приемлемой, либо не
имеющей прямого отношения к теории или даже как к ложному посту-
лату. Если аксиома выбора включается в систему аксиом ZF, то
результирующая система называется ZFC-теорией.
На исторически ранней стадии развития теории множеств предпри-
нимались попытки доказать или опровергнуть аксиому выбора с
помощью аксиом ZF-теории, но они завершились полным провалом.
7.11.	Теорема (Курт Гедель, 1936). Невозможно опровергнуть
аксиому выбора.
7.12.	Теорема (Поль Коэн, 1963). Невозможно доказать аксиому
выбора.
Эти две теоремы по меньшей мере озадачивают. Но к чему-то
подобному математики были уже подготовлены первой теоремой
Геделя о неполноте (1931 г.), в которой тот доказал, что для любого
совместного множества высказываний, имеюпщх некоторые общие
характеристики, найдутся высказывания, которые будет невозможно
ни доказать, ни опровергнуть. Теперь же мы в действительности
получили первый конкретный пример.
29
Смысл этих теорем на самом деле очень глубок, и в следующей
главе мы обсудим идеи, позволяющие подойти к их доказательству.
ЗАДАНИЕ 31.
Определение. Множество X называется конечным тогда, и только
тогда, когда для некоторого п • N выполняется условие II n II = В А II. В
противном случае множество X называется бесконечным.
Множество X называется бесконечным по Дедекинду тогда и »
только тогда, когда существует однозначная функция из
множества X на собственное подмножество множества X. В противном
случае множество называется конечным по Дедекинду. Докажите
с. едующие теоремы.
7.13.	Теорема. Любое п в N - конечное по Дедекинду множество.
7.14.	Теорема. Если X - конечное множество, то оно конечное и по
Дедекинду.
Используя ZFC-теорию, докажите следующие теоремы.
7.15.	Теорема. Пусть X - конечное множество. Тогда существует
функция, однозначно отображающая о в множество X.
7.16.	Теорема. Из того, что X - бесконечное множество, следует,
что оно бесконечное по Дедекинду.
ЗАДАНИЕ 32. Используя ZFC-теорию, докажите следующие
теоремы.
7.17.	Теорема. Счетное объединение счетных множеств есть счет-
ное множество.
7.18.	Теорема. Если А - счетное множество, то АХА - счетное
множество.
7.19.	Теорема. Не существует наибольшего кардинального числа.
ЗАДАНИЕ 33. Используя только ZFC-теорию, докажите следующие
теоремы.
7.20.	Теорема. Если функция f однозначно отображает
множество X на ординал р, го существует полное упорядочение
множества X порядкового типа р.
7.21.	Теорема (теорема Гартога). Не существует наибольшего
кардинального числа.
Определение. Если для некоторого множества А существует
кардинальное число X , такое, что В А В= К ,то это число единственное.
Если К - кардинальное число, то ||Н|| = К.. Обозначим через ^наи-
большее кардинальное число, следующее после К.
Определение.
Ко =
«1=(^0)+ ,
Кя+1 = (Кя)+при любом значении пем,
30
I
= U{«n|neto},
и вообще Кю+1 =(КШ)+ ,
Кл - А.-е бесконечное кардинальное число. Наконец, с = || Р(со)|| =
» || R || (готическая буква с как аббревиатура слова Continium - конти-
нуум).
Континуум-гипотеза (СН). с =
Обобщенная континуум-гипотеза (GCH) ||Р(К)|| = К+ для любых
кардинальных чисел К, Ко < К.
Обе гипотезы были сформулированы Кантором. Он считал вполне
правдоподобным справедливость континуум-гипотезы и пытался
найти доказательство. Идея вполне естественная. Из теоремы 7.7
вытекает, что || R || больше, чем а = Ко,но насколько больше?
7.22.	Теорема (Курт Гедель, 1936). Невозможно опровергнуть
континуум-гипотезу (СН) или обобщенную континуум-гипотезу (GCH).
7.23.	Теорема (Поль Коэн, 1963). Невозможно доказать ни конти-
нуум-гипотезу, ни обобщенную континуум-гипотезу.
Глава 8
УНИВЕРСАЛЬНОЕ МНОЖЕСТВО
... Послушай, совсем рядом чертовски хорошенькая
вселенная, давай войдем.
В. В. Каммингс
Теперь, рассматривая структуру универсального множества, изучим
часть традиционной теории множеств. Принципиальным понятием
будет понятие множества, представляющего собой универсуум под-
множеств, причем все аксиомы ZF-теории оказываются истинными
для элементов этого множества.
Определение. а) У( 0) = 0; б) V(a +1) = Р( У( а)) для любых ордина-
лов а; в) V( А.) = U {У( а )| а < А.} для всех предельных ординалов А. •
8.1.	Теорема. Для любых ординалов а универсуум У(а) определен
и единствен.
Доказательство в точности следует доказательству теоремы 6.4 об
индуктивном определении, только формула <р теперь определяется
Следующим образом:
"х- ординал и существует функция h, такая, что:
h(0) = 0;
h(a+01) = P(h(a)) для всех a <х:
31
h(X,)“Ufh(B)ip<A.} для всех предельных ординалов А. <х, и
h(x)-y.”
Отметим, что как следствие мы получили не только то, что V - функ-
ция, но и что выражение ”ze У (а)” можно записать на языке-С.
Обычно вместо У( а) принято писать Va.
ЗАДАНИЕ 34. Используя только символы и запишите
v0>v^v2,v3.
Докажите следующие теоремы.
8.2.	Теорема. При любых а имеет место хе ye va ->• хе Va.
83.	Теорема. Для любых ординалов а и 6 имеет место
6<a-y4sV’ .
ЗАДАНИЕ 35. Докажите следующую теорему.
8.4.	Теорема. Каждое множество содержится в некотором множест-
ве Уа.
Определение. Кардинальное число к называется регулярным, если
всякий раз, когда Х=к и IIХИ <к, выполняется неравенство UX<k.
Если к - н.е регулярное кардинальное число, то оно называется син-
гулярным.
ЗАДАНИЕ 36. Докажите следующие теоремы.
8.5.	Теорема, о - регулярное кардинальное число.
8.6.	Теорема. - сингулярное кардинальное число.
8.7.	Теорема. Если мы принимаем аксиому выбора, то Kj - регу-
лярное кардинальное число.
Определение. Кардинальное число к>ы называется строго недо-
стижимым, если оно регулярное и всякий раз, когда HXIKk, имеет
место неравенство IIР(Х) II <к. Отметим, что обозначение II Р(Х) II будет
осмысленным лишь при условии, что можно полностью упорядочить
Р(Х).
ЗАДАНИЕ 37. Докажите следующие теоремы.
8.8.	Теорема. Не верно, что кардинальные числа о, К6 и
строго недостижимые.
8.9.	Теорема (аксиома выбора). Если к - строго недостижимое
кардинальное число и а<к, то II Va II < к.
ЗАДАНИЕ 38. В рамках ZFC-теории докажите следующие теоремы.
8.10.	Теорема. Если к - строго недостижимое кардинальное число,
roeVk истинны все аксиомы теории Цермело-Френкеля.
Определение. Пусть Т - совокупность аксиом (называемая тео-
рией) такова, что каждая аксиома из Т оказывается истинной на
множестве X; тогда множество X называется моделью теории Т. .
32
Теорема 8.10 утверждает, что если к - строго недостижимое
кардинальное число, то множество Vfe будет моделью ZFC-теории.
Определение. Пусть Т означает набор высказываний. Тогда
Con( Т) - высказывание о совместности совокупности высказыва-
ний Т.
Примеры
1.	Начиная с гл. 6 принято предположение о том, что высказывание Con(ZF) — истинное.
2.	Вторая теорема Геделя о неполноте (см. гл. 6) утверждает, что истинность Соп(Т)
не может быть доказана в теории Т (при определенных Т).
3.	Ранними теоремами Геделя устанавливается связь между понятием модели и
понятием совместности. Теорема о полноте (1930 г.) утверждает, что если высказывание
Соп(Г) — истинное, то теория Тимеет модель (обратное тривиально истинно).
Введем еще одну аксиому.
Аксиома SI1. Существует строго недостижимое кардинальное
число.
4.	Согласно примеру 3 в теореме 8.10 говорится о том, что из
аксиом ZFC и SI следует Con(ZF). В действительности, поработав еще,
мы сможем доказать и то, что из аксиом ZF, SI следует высказывание
Con(ZF).
5.	Теоремы 7.11 и 7.12 теперь можно записать в виде
Con(ZF) - Con(ZF + AC);
Con(ZF)- Con(ZF + l AC).
ДОКАЗАТЕЛЬСТВО. Предположим, что теория ZF совместная.
Тогда в ZF нельзя опровергнуть ни АС, ни ]АС; поэтому обе теории
ZF U {АС} и ZF U {1 АС} представляют собой совместные системы аксиом.
Такие доказательства совместности называются относительными.
Мы не можем доказать справедливость высказывания Con(ZFC), но
можем доказать, что это утверждение есть следствие Con(ZF). Еще
совсем недавно теоретики были обеспокоены тем, что пополнение
ZF-теории аксиомой выбора может привести к несовместной системе
аксиом. Согласно теореме Геделя беспокоиться нечего, поскольку
если сочетание ZF-теории с аксиомой выбора несовместно, то несов-
местной будет и сама ZF-теория. Это означает, что аксиома выбора -
относительно ’’безопасная” аксиома. То же самое можно сказать и о
] АС, но уже в силу теоремы Коэна.
Как доказывается относительная совместность? Доказательство
теоремы Геделя о том, что высказывание Con(ZF) влечет Con(ZF + СН),
проводится следующим образом: если ZF-теория совместная, то для
нее существует модель М. Затем Гедель обнаружил, что любая такая
1SI — аббревиатура от Strong Inaccessibility — строгая недостижимость. - Прим, перев.
33
5-3504
модель имеет (возможно, меньшую) подмодель L внутри себя, которая
уже удовлетворяет аксиомам как ZF-, так и сН-теорий. Ну а раз
существует модель, то теория ZF + СН должна быть совместной. При
доказательстве своей теоремы Коэн использовал Геделевскую модель,
которую аккуратно расширил до модели N, такой, что в ней одновре-
менно становились истинными аксиомы ZF- и]СН-теории и, значит,
ConfZF + ]СН).
А что можно сказать относительно аксиомы SI? Безопасная ли она?
8.11.	Теорема. Из высказывания Con (ZF) не следует высказывание
Con (ZF + SI). Иными словами, мы не можем доказать, что невозможно
опровергнуть аксиому SI!
ДОКАЗАТЕЛЬСТВО. Рассмотрим теорию Т = ZF + Con(ZF) и допус-
тим, что Con(ZF)-> Con(ZF + SI). Тогда
T-*ZF + Con(ZF + SI)~*ZF + Con(ZF + Con(ZF))-* (см. пример 4)
-* Con (ZF + Con (ZF)) - Con (T),
но по теореме о неполноте из теории Т не может вытекать ее собствен-
ная совместность.
Глава 9
ВЫБОР И БЕСКОНЕЧНО МАЛЫЕ ЧИСЛА
Я не заходил бы так далеко, чтобы утверждать, что
построение истории мысли без глубокого изучения
математических идей в последующие эпохи было бы
подобно исключению Гамлета из действующих лиц
пьесы, названной его именем. Это было бы преувеличе-
нием. Скорее, можно говорить об исключении роли
Офелии. Сравнение удивительно точное. Ибо для пьесы
Офелия очень существенна: она очаровательна и слегка
безумна.
А. Н. Уайтхед
Здесь мы собираемся доказать теорему 7.10, которая предлагает три
эквивалентные формы аксиомы выбора. Затем воспользуемся аксио-
мой выбора для построения системы чисел, которые получили назва-
ние гипердействителъных чисел (HR). Эта система расширит числовую
систему IR в той же мере, в какой R расширяет Q a Q расширяет Z.
Числовая система HR содержит как бесконечно малые, так и бесконеч-
но большие числа.
34
3504
ЗАДАНИЕ 39. Докажите следующие теоремы.
9.1.	Теорема. Теорема Цермело вытекает из аксиомы выбора.
9.2.	Теорема. Лемма Цорна вытекает из теоремы Цермело.
ЗАДАНИЕ 40. Докажите следующие теоремы.
9.3.	Теорема. Аксиома выбора вытекает из леммы Цорна.
Этим завершается доказательство теоремы 7.10.
Определение. ер(и) называется (не главным) ультрафильтром
на ы тогда и только тогда, когда:
а)	если Л, В е то А Г) В е
б)	если 11АII «о, то со\ЛбФ;
в)	каково бы ни было множество А^ы, либо А, либо ы\А содер-
жится в °U.
В рамках ZFC-теории докажите следующую теорему.
9.4.	Теорема. На ы существует ультрафильтр.
До конца главы будем считать, что ультрафильтр нам. Более
того, примем на веру все обычные свойства действительных чисел,
которые мы не потрудились доказать в гл. 5.
Определение. Пусть у = {Л/функция из ы в IR}.
Определим на X отношение S условием
/ %g тогда и только тогда, когда {п ea>\f(n) = g(и)} е ty.
ЗАДАНИЕ 41. Докажите следующую теорему.
9.5.	Теорема. Отношение s есть отношение эквивалентности.
Определение. Совокупность HR классов эквивалентностей называ-
ется множеством гипердействительных чисел.
Определение.	тогда и только тогда, когда
{neo)\f(ri) <в д(п)}е^.
Докажите следующую теорему.
9.6.	Теорема. Отношение <ю - корректно определенное линейное
упорядочение.
Определение. Для любого числа г е й через fr € X обозначим
функцию, такую, что при любом п
fr(n)-r (постоянная функция).
Определение.х е HR. называется бесконечным числом тогда
и только тогда, когда либо
l)x<w[/Js для всех г е 1R, либо
2)	х >ш [/г] g для всех гей.
Докажите следующую теорему.
9.7.	Теорема. Совокупность HR содержит бесконечные числа.
35
5
Определение. Число х е HR называется бесконечно малым числом
тогда и только тогда, когда:
1)	х
2)	х <hr [/rls	для всех г е R, г >н 0н ;
3)	х >ш [/r]g	для всех г е R, г <н 0н.
Докажите следующую теорему.
°;8. Теорема. Совокупность Ш содержит бесконечно малые числа.
Теория гипердействительных чисел была развита Абрахамом
Робинсоном в 1960 г. как альтернативный подход к классическому
математическому анализу. Ранние исследователи исчисления беско-
нечно малых (XVI1-XIX столетия) пользовались понятиями бесконеч-
но больших и бесконечно малых чисел, не заботясь о строгости. И хотя
эти идеи были чрезвычайно плодотворными, наблюдалась определен-
ная настороженность, поскольку они казались необоснованными ни
математически, ни как-нибудь по-другому. С помощью понятий
бесконечно малых чисел великие мыслители приходили к формули-
ровкам истинных теорем. Другие исследователи, прибегая к подоб-
ным рассуждениям, приходили к противоречиям. Один из первых
открывателей исчисления бесконечно малых Лейбниц, упорно настаи-
вал на том, чтобы с бесконечными количествами оперировали точно
так же, как с конечными числами. Однако чувствовалось, что здесь
где-то должны возникнуть ограничения, но не была понятна их сущ-
ность. В конце концов эти идеи были вытеснены теорией пределов.
Робинсон рискнул разработать метод исчисления бесконечно
малых чисел и в процессе создания теории обнаружил, что представля-
ют собой эти ’’ограничения”.
Определение. Обозначим через математический язык, который
построен точно так же, как и язык £ но со следующими изменениями;
1)	в язык £ н не включается символ “=;
2)	символы+R и -й сохраняются, и
3)	для любого действительно числа имеется постоянный символ и,
более того, имеется символ для любой действительной функции.
Робинсоном была доказана следующая теорема.
9.9.	Теорема. Если <р - высказывание, записанное на языке то
Ф - истинное высказывание в R тогда и только тогда, когда ф есть
истинное высказывание в Ш.
Другими словами, ограничение состоит в том. что следует придер-
живаться рамок языка £я-
ЗАДАНИЕ 42 (без доказательств). Определите операциии .то.
Пусть Н, Keffi - положительные бесконечно большие числа.
36
Пусть I, J e Ш- положительные бесконечно малые числа. Определите
истинность или ложность следующих высказываний:
1)	число Н +вд К должно быть бесконечным числом;
2)	число I J должно быть бесконечно малым числом;
3)	число I +вд J должно быть бесконечно малым числом;
4)	число Н-вд [ /0 01] должно быть бесконечным числом;
5)	число! -то L./ioo J должно быть бесконечно малым числом;
6)	существует наибольшее конечное гипердействительное число;
7)	существует наибольшее бесконечное гипердействительное
число;
8)	существует наименьшее бесконечное положительное гипер-
действительное число;
9)sin2(H) +ш cos2(H) = ЕЛ;
10)	каждое ограниченное множество в HR имеет наименьшую
верхнюю грань.
Гипердействительные числа E/rJ^ составляют точную копию [R
внутри Ш. В этом смысле числовую систему Ш можно рассматривать
как расширение числовой системы R. В системе Ш содержатся к тому
же и другие числа - бесконечно большие и бесконечно малые. Сле-
дующая теорема более ясно освещает картину порядковой структуры
системы Ш .
9.10.	Теорема. Кажоое конечное гипердействительное число
бесконечно близко к единственному действительному числу, т. е. для
каждого конечного числа хеЮсуществуетединственное число relR*
такое, что разность между х и [/г]ж будет либо [/0 ]s, либо бесконечно
малым числом.
Глава 10
ТЕОРЕМА ГУДСТАЙНА
Ничто стоящее не может быть доказанным, но и не
может быть опровергнутым.
Альфред Тенинсои
Эта часть книги посвящена замечательной теореме, доказанной в
1944 г. Р. J1. Гудстайном. Она замечательная в разных аспектах. Во-пер-
вых, это настолько необычное утверждение, что трудно поверить в его
истинность. Во-вторых, эта теорема утверждает факт о конечных
числах, но при ее доказательстве используется понятие бесконечных
ординалов. В-третьих, по прошествии 37 лет после появления дока-
37
зательства Гудстайна Л. Керби и Дж. Парис показали, что доказать
теорему Гудстайна без использования понятия бесконечных множеств
невозможно. Таким образом, теорема Гудстайна - это арифметическая
теорема, которую нельзя доказать арифметическими методами, а лишь
прибегая к сверхмощи теории множеств.
Чтобы сформулировать теорему, вначале надо обсудить, что
означает запись числа по ’’супероснованию 2”. Возьмем, например,
число 23. Запишем его в системе с основанием 2
2310 = 101112,
что, по существу, есть сокращенное обозначение суммы
24 + 22 +21 +2°.
В этой записи встречается цифра 4. При записи числа по супероснова-
нию 2 мы хотим исключить все числа больше 2, поэтому представим 4
степенью числа 2, т. е. 4 = 22, получим
23 = 22’ + 22 + 21 + 2° или 22’ + 22 + 2 + 1.
Для больших чисел, может быть, придется пойти еще дальше,
например записать
514 = 29+2 = 2РЭ + 1)+ 2 = 2<2(2+1)+1) + 2.
Тот же принциггприменяется и при записи числа по супероснованию 3,
супероснованию 4 и т. д.
А теперь сама теорема.
Возьмите любое натуральное число и запишите его по суперосно-
ванию 2.
Замените всюду цифру 2 на цифру 3. Отнимите единицу и перепи-
шите полученное число по супероснованию 3.
Замените всюду цифру 3 на цифру 4. Отнимите единицу и перепи-
шите полученное число по супероснованию 4.
Гудстайн утверждает, что в конечном счете вы получите О!
Проделаем предлагаемые шаги для небольшого числа, например
для числа 8:
начало	2<2*« = 8, 3(3+1)= 81 (заменена цифра 2 на цифру 3),
после шага 1	2 -З3+ 2-З2+ 2- 3 + 2 = 80 (отнята 1 и пере- писано),
38
	2 -44+ 2- 42+ 2- 4 + 2 = 554 (заменена цифра 3 на цифру 4),
» после шага 2	2 -44+ 2-42+ 2- 4 + 1 = 553 (отнята 1 и пере- писано), 2 • 55+2 • 52+2 • 5 + 1=6311,
после шага 3	2 -55+2-52+2- 5 = 6310, 2 • 66+2 • 62+2 • 6 = 93396,
после шага 4	2 • 66+2 • 62+6 + 5 = 93395
И т. д.
Выпишем несколько следующих чисел: 1647195,33554571,774841151,
20000000211, 570623341475. Каким же образом мы получим 0?
Определение. Для каждого п<ы, 2 <п, определим функцию Sn из
ивы следующим образом:
ЗД = о,
Sn(k’ п*) = к(п+ 1/^4 если к<п,
d . d
№Sn^okin,^LSn(kin^
где кд,kd<n.
Определение. Для каждого п <ы, 2 определим функцию £пиз ы
в ы следующим образом:
1,
gn+i(m)~Sn+1(g(m))- если2«п.
10.1.	Теорема (Гудстайн, Керби, Парис). Vm 3 п gn (т) = 0.
Это действительно обобщение оригинального результата Гудстай-
на, полученное Керби и Парисом.
ЗАДАНИЕ 43
1.	Рассчитайте gat11)» ЯзО1)» —, Set11)-
2.	Найдите наименьшее п, такое, что gn{3) = 0.
3.	Оцените значение наименьшего п, такого, что gn(4) = 0.
Определение. Для ординалов а, Р и к, где К - предельный орди-
нал, положим
а1 = а,
а₽+;= а3.
ях= U{asi 6<Х}.
Определение. Для каждого п<ы, 2 <п, определим функцию f из ы
в ординалы следующим образом:
4(0) = о,
fn(k • п() = afrits • к, если к <п,
39
d	d
гдек0,kd<n.
ЗАДАНИЕ 44. Докажите следующие леммы.
10.2.	Лемма. Для любых п,т<ы имеем fn(m)=fn+1(Sn(m)).
10.3.	Лемма. Для любых п,т<ы имеем fn(m + l)>fn(т).
10.4.	Лемма. Еслиgn(m)>0, для любыхп,т<ы, то
f„+2(S„+1(m))<fn+1(gn(m)r.
Докажите теорему Гудстайна.
Почему для доказательства теоремы Гудстайна понадобились
бесконечные множества? Теоретики теории множеств описывают
'арифметику как теорию, состоящую из четырех аксиом Пеано, приве-
денных в гл. 2. Но на самом деле аксиома индукции выполняется для
всех определяемых множеств. Полная система называется системой
РА. Доказательство Гудстайна основано на теории ZF. В течение
многих лет после появления доказательства Гудстайна специалисты
по теории чисел и теории множеств пытались найти доказательство в
рамках РА-теории. Наконец в 1981 г. Керби и Парис показали, что в
теореме Гудстайна используется предположение о совместности
РА-теории, и поэтому в силу второй теоремы Геделя о неполноте (см.
гл. 6.) теорема Гудстайна не может быть доказана в рамках РА-теории.
В этом коротком объяснении пропущена довольно большая часть
сложных математических рассуждений. Теорема Гудстайна утвержда-
ет очень глубокий факт, связывающий теорию чисел, логику и теорию
множеств - предмет исследований данной книги. Основная идея
доказательства состоит в использовании нестандартной модели
арифметики, построенной из N таким же образом, как в предыдущей
главе из числовой системы IR была построена система Ш.
।	ЧАСТЬ II
УКАЗАНИЯ
Глава 1
ЛОГИКА И ТЕОРИЯ МНОЖЕСТВ
ЗАДАНИЕ 1
1.	Приведем несколько ответов.
а) Т; в) F; д) Т. Это высказывание истинное, поскольку высказыва-
ние Ье с - ложное. Может показаться странным, что высказывание
ф-*ф, которое иногда читается как ”ф влечет ф” а иногда как ’’если
Ф, то ф” оказывается автоматически истинным, если высказывание
ф- ложное. Однако так бывает и в обычном разговорном языке.
Например, там, где я живу, действует закон, запрещающий парковать
автомобили на ночь в зимние месяцы. Этот запрет можно выразить
точнее: ’’Если сейчас позднее 12 ночи, но нет 7 часов утра и месяц
декабрь, январь, февраль или март, то Вы не имеете права оставить
машину на улице”. Этот запрет - муниципальная импликация, и я
обнаружил, что могу выполнить ее без всяких усилий в июне месяце.
Поскольку первая часть импликации ложна, то относительно закона
абсолютно безразлично, где я паркую свою машину.
з) Т; и) F (например, Ь).
2.	В примере н) t^s есть высказывание согласно свойству 1,
- высказывание согласно свойству 2е, поэтому Vs^t(t^s)-
высказывание согласно свойству 2ж.
ЗАДАНИЕ 2. По существу, Вас попросили выучить новый язык и
научиться переводить с него. Для достижения этой цели попробуйте
выразить русским языком, что означает каждая часть высказывания.
Например, рассмотрим высказывание ж). Высказывание 3z(zex)
говорит о том, что множество х имеет по крайней мере один элемент z.
Запись (н»е х - w = z) означает, что если w принадлежит х, то w равно z.
А поскольку перед этой частью высказывания стоит квантор V w, то это
Утверждение будет истинным при любом у>. Поэтому полное утвержде-
ние состоит в том, что z есть единственный элемент множества w.
Собрав все вместе, получим, что в высказывании ж) говорится о том,
6-3504	41
что множество х состоит в точности из одного элемента. Таким обра-
зом, множество х должно быть множеством е.
Будьте внимательными и удостоверьтесь, что Вы четко понимаете
различие между символами s и е. Например, Ь, но еФ b или d& b,
но 1 ds b.
ЗАДАНИЕ 3. Теперь мы заняты более трудной задачей: переводом
с обычного языка на язык £ . Возьмем в качестве примера аксиому
пары. Мы хотим сделать утверждение о произвольной паре множеств,
поэтому вначале следует записать V eV d. В аксиоме говорится о том,
что существует множество е; значит, следующей записью будет Зе.
Какова связь между множествами с, d и е? В действительности это
просто е= {с, d}, и задание выполнено:
VcVd3e(e= {c,d}).
Чтобы попрактиковаться, попробуем ответить на вопрос, как, не
зная сокращенной записи {с, d), выразить этот факт на языке £.
Чтобы показать, что end есть элементы множества е, запишем сееЛ
Л de е. А то, что это все элементы множества е, можно выразить выска-
зыванием: ’’каков бы ни был элемент / из множества е, этот элемент
должен совпасть с множеством либо с, либо d”:
Vf(f^e^(f = cVf = d).
Собрав все высказывания, получим
VcV d3e(ceeAd^e/\yf(f^e->-(f=c\/f=d))).
Запомните сформулированные ранее правила формирования
высказываний. Удостоверьтесь, что Вы сможете (так же, как это было
сделано в задании 1) проверить, правильно ли построены высказы-
вания.
ЗАДАНИЕ 4
4.1. Воспользуйтесь вначале аксиомой пары, а затем аксиомой
объединения.
1.2.	Покажите, что АП В- определяемое подмножество множества
А, и используйте аксиому содержательности. Не забудьте выписать на
языке £ (вместе с константами для множеств) явное утверждение ф.
1.3.	Используйте аксиому пары.
1.4.	Здесь впервые воспользуемся аксиомой регулярности. На
первый взгляд эта аксиома кажется несколько странной, но ею высве-
чивается фундаментальное свойство множеств: любое множество,
сколь угодно сложное, состоит из множеств, которые несколько проще
исходного. Представьте себе элемент b (в формулировке аксиомы
42
регулярности) как самый простой элемент множества d. Тогда все
элементы множества b проще, чем Ь, и поэтому не содержатся в d. Для
доказательства теоремы 1.4 аксиому регулярности применить к
множеству {А}.
Одно из следствий этой теоремы состоит в том, что парадокс
Рассела уже не преследует нас. На самом деле, парадокс исчезает,
даже если и не использовать аксиому регулярности. Мы просто можем
доказать, что R = {х|х£%} - не множество (поскольку, допустив
противное, мы бы имели Re R тогда и только тогда, когда R$ R, что
невозможно).
1.5.	Вновь искусно примените аксиому регулярности к {А, В).
1.6,	1.7. Примените аксиому экстенсиональности.
ЗАДАНИЕ 5. Например, пара {а,Ь} не подходит. Если c*d, то мы
хотим, чтобы < с, d> и < d, с> были различными множествами, но {с, d)
и {d,c) - это одно и то же множество. По той же причине не годятся
пары и {{а), {Ь}}, и {а,Ь^ а, Ь}}- Совсем по другой причине не подходит
пара {а,[ Ь)}• Допустим, что с*d. Мы хотим, чтобы множества < {с}> d>
и <{d), с> были различными, но если принято определение <а,Ь> =
= {а,{ Ь}}, то эти множества совпадают.
Убедиться, что к успеху ведет {{а), {а,Ь}}, вы можете, показывая,
что всякий раз, когда {{а}, {а,Ь}} = {{с),{с,d}} будет выполняться,
а = с и b = d.
1.8.	Покажите, что A><B - определяемое подмножество множества
P(P(A\iB)).
1.9.	Покажите, что область значений функции / есть определяемое
подмножество множества U (U /).
1.10.	Покажите, что /I D есть определяемое подмножество в мно-
жестве /.
ЗАДАНИЕ 6
1.12.	Используйте аксиому содержательности.
1.13.	Предположим, что [ а] (1 [ b] R + <Р.
Сначала покажите, что aRb. Помните, что для доказательства равенст-
ва двух множеств х и у вы должны показать, что: а) каждый элемент
множества х будет и элементом множества у, б) каждый элемент
множества убудет и элементом множества х.
1.14.	Воспользуйтесь аксиомой содержательности.
43
6*
Глава!
НАТУРАЛЬНЫЕ ЧИСЛА
ЗАДАНИЕ 7
2.2.	Предположим, что множества а и b удовлетворяют аксиоме
бесконечности. Попробуйте применить аксиому регулярности к
множеству (a\b) U(b\a).
2.З.В.	Используйте теорему 1.5.
2.3.	д. Примените аксиому регулярности к множеству М\4.
2.4.	Пусть А = {к е М|<р(к)}.
ЗАДАНИЕ 8
2.6.	Примените метод индукции по основанию с. Пусть ф (с) -
высказывание:
VaVb(a +n (b +N с) — (a +n b) +N c).
2.8.	Примените метод индукции по основанию п. Пусть q(n) -
высказывание:
О +N п = п.
ЗАДАНИЕ 9
2.9.	Свойство коммутативности оказывается не столь простое, как
свойство ассоциативности. Попробуйте вначале по индукции доказать,
что для любых а е N выполняется равенство a +м 1 = 1+гу а, а затем
вновь по индукции доказать, что a b = b +N а .
ЗАДАНИЕ 10
2.12.	Примените метод индукции по основанию р.
2.13.	Нет необходимости применять индукцию.
2.14.	Воспользуйтесь методом индукции и теоремой 2.11.
ЗАДАНИЕ И
2.15.	И вновь наибольшие трудности связаны с применением
закона коммутативности. Вначале докажите, что при любом а е N
имеет место О -N а = ОЗатем, используя индукцию по а, приступите к
доказательству a -Nb = b -N а. В середине доказательства придется
предположить, что для любых be N справедливой -N b = b -No. Попы-
тайтесь доказать, что5(а) b = b -N 5(а)при всех be N. Чтобы достичь
этого, вновь придется воспользоваться индукцией, но теперь по
основанию Ь. Такой тип доказательства иногда называют методом
двойной индукции.
ЗАДАНИЕ 12
2.18.	Воспользуйтесь индукцией по основанию у. Помните, что
44
если z =# 0, то z = S(k) при некотором к. Вспомните также, что S(y) =
2.19.	Для упрощения доказательства свойства антирефлективности
примените теорему 2.18. Для доказательства свойства трихотомии
примените метод индукции.
Глава 3
целые числа
ЗАДАНИЕ 13
3.1. Попытка доказать транзитивность приведет нас к пониманию
того, что не хватает одного очень важного факта относительно мно-
жества!^, а именно закона сокращения:	,
если а+^Ь = а+^с, тоЬ = с.
Назовите это утверждение леммой 2.20 и докажите его. Отметим,
что правило сокращения очень похоже на правило вычитания, а это
как раз то, что нужно для определения Z.
Почему мы, определяя операцию+2> вынуждены провести расши-
рение числовой системы от множества N до Z? В основном - чтобы
ввести операцию вычитания. Представьте себе каждую упорядоченную
пару как ответ на вопрос, чему равна разность a-b? Например, пара
<3,2> представляет в Z число 1, а пара <2,5> - число-3. С таким
пониманием задача расшифровки записи [<a,b>]~ +zlXc>^>]~
сводится к задаче поисков упорядоченной пары [<е,/>]~, такой, что
(a~b) + (c-d) = (e-f).
Что же такое ей/? Вспомним, что это должны быть элементы
множества N, подобные а, Ь, с и d. Есть много способов определения
этих элементов, самый простой из них - положить
е ~ а +м с, f = b d.
Однако задание еще не выполнено: нужно показать, что операция
+z определена корректно. Итак, мы решили, что
[<л,Ь)]~ +г [<c,d)]~ = [<a +м c,b +N
По сути это означает, что при заданных к и t из Z, мы рассчитываем
+z ^выбирая пары <а, Ъ>^к я<c,d>^t (вспомним, что все числа
отождествлены с парами натуральных чисел) и образуем пару [ <а
+MC,b + Nd>]~.
zHo что же произойдет, если выбрать другие пары:<а, d >&к и
<c,d>ej? в этом случае получим [<a'+n с',b'+N Если
введенная нами операция сложения имеет смысл, то эти два ответа
45
должны совпадать, т. е. если <a,b>~<a',b/> и <c,d>~<c',d' >, то
должно быть<а +N c,b	+м c',b’+N d'>.Докажите, что так
оно и есть. Именно это мы имеем в виду, когда говорим, что операция
+z определена корректно.
Леопольд Кронекер, судя по цитате, приведенной в начале гл.З,
ч.1, вряд ли одобрил бы наш метод построения Z. В частности, он
возражал бы против использования бесконечных множеств (каждый
класс эквивалентностей [<a,b>]^.eZ- это бесконечное множество).
К концу своей карьеры Кронекер сильно сомневался в существовании
бесконечных множеств. Но несколько напрягая воображение, чита-
тель, возможно, сумеет догадаться, как построить множество, эквива-
лентное множеству Z, каждый элемент которого будет конечным
множеством.
ЗАДАНИЕ 14. Для определения 0z выберем [<а, Ь>]~_ специаль-
ным образом, чтобы легко было доказать теорему 3.4.
Если при определении "(а)?; рассмотреть <с,d> как значение
разности c-d, то отрицательному числу будет соответствовать раз-
ность d-c, т. е. "(I<c,d>]~)z = [<d, с>]~. И вновь мы должны дока-
зать, что определение дано корректно, т. е. если <c,d>~<c',d' >, то
<d,c>~<d',c'>. Для отношения <z естественным определением было
бы [<а,Ь>]~<г	тогда и только тогда, когдаа +w d^b-i-^c.
Чтобы доказать корректность этого определения, следует воспользо-
ваться еще одной леммой о множестве N: а<^Ь тогда и только тогда,
когда a +м c<n b+N с для любых а, b исе N. Назовите это утверждение
леммой 2.21 и докажите ее.
3.6. Заметьте, что из леммы 2.21 следует, что если a<w Ьи с< w d то
a +n c<n biN «/(почему?)
ЗАДАНИЕ 15. При определении произведения [<a,b>]^-2 [<с, d>] ~,
имейте в виду, что (a-b)(c-d) = ас + bd-bc-ad. Это подсказывает
ответ [<(a -N c)+N (b-N d);(b-N c)4-N (a-N d)>]~. Доказать, что это опре-
деление корректно, будет трудоемко. Воспользуйтесь тем, что из
равенства х = у следует равенство х- м z = у z, и старайтесь не забы-
вать об этом!
С одной стороны, множества N и Z очень разные. С другой же,
множество Z содержит нечто, что делает его очень похожим на N, а
именно совокупность
{[<n,0>]~ eZ|ne N}.
Не стремясь к строгости, можно сказать, что это множество ведет себя
так же, как и множество!^. В этом смысле мы можем сказать, что N
вложено в
46
Глава 4
РАЦИОНАЛЬНЫЕ ЧИСЛА
ЗАДАНИЕ 16. При переходе от N к Z требуется операция вычита-
ния (мысленно отождествите а - b и a +2 (Ь)2). Мы делали что-то
подобное при построении Z как совокупности всех задач на вычита-
ние: каждая пара <а,Ь> представляла собой разность а - Ь. Каким
способом было определено отношение*- ?. Пары <а, Ь> и <с, d> должны
представлять одно и то же число тогда и только тогда, когда а - b =
яc-d. Поскольку мы не могли провести операцию вычитания в N,то
a-b = c-d представили как a +N d = b +N с.
Теперь при расширении Z до Q мы хотим потребовать выполни-
мости деления. Множество Q можно представить как совокуп-
ность упорядоченных пар <a,b\ a, beZ, каждая из которых пред-
ставляет задачу деления а/b. Конечно, число b должно быть отлично от
0. И вновь пары <а, Ь> и <c,d> должны представлять одно и то же
число тогда, и только тогда, когда a/b = c/d. Поскольку мы не можем
проводить операцию деления в Z, то потребуется другая запись.
Определение. Определим отношение на множестве Z х (Z\
\{ 0z })условием
< а, Ь> « < с, «/> тогда и только тогда, когда а у d = b у с.
Покажите, что данное отношение есть отношение эквивалентнос-
ти. Это будет нелегко. Вам потребуется лемма: для любых р, q, г е Z из
q тФ 02 и р '1 q = r ’z Ч> следует р = г. Этот закон сокращения для
операции-z- Существует много способов доказать его. Попробуйте
найти собственное доказательство, следуя схеме:
1) сначала докажите закон сокращения для операции -N;
2) предположите, что р = f<i,j>]~,q = [<k,s>]~, г =
Ч 02, и что р -1 q = г у q ; раскройте это выражение. Если вам
повезет, то вы придете к равенству
(О +м и) \ к) +м ((J +м t) s)= ((! и) s) ((j +n t) ‘n k).
Воспользуйтесь трихотомией по к и s для завершения доказатель-
ства. Заметьте, что кФ s (почему?)
Вновь используем бесконечные множества для построения Q, но,
как и раньше (возможно, не без затруднений), сможем достичь того же
с помощью только конечных множеств.
ЗАДАНИЕ 17. Как вы складываете дроби? Что означает запись
(a/b) + (c/d)“! Это (ad + bc)/bd. Докажите, что b yd не окажется нулем
и не забудьте показать корректность операции +q 
Определение. 0Q =[<02,12>]~, где 12 = [<1,0>]~-
Определение. -([<р,ч>]«)о = EC(p)z,4>K-
47
Чтобы показать корректность этих определений, может пртребо-
ваться вспомогательная лемма, но вполне возможно и прямое доказа-
тельство.
ЗАДАНИЕ 18. Как вы перемножаете дроби? Какая дробь равна 1?
Какая дробь, взятая а/Ъ раз, равняется 1?
В этом задании много работы, но она не очень сложная. Как и
прежде, видим, что множества Z и Q очень разные, и все же мно-
жество Z может быть вложено в Q. Сможет ли читатель найти в
множестве Q копию/?
ЗАДАНИЕ 19. Задание непросто главным образом потому, что мы
не удосужились доказать несколько свойств отношения <2. Наилуч-
шим советом общего характера будет: попробуйте доказать теорему
4.5, выписывая попутнр все факты, которые для этого требуются. Вы
можете прервать чтение и приступить к доказательству или последо-
вать за приведенными далее указаниями.
Определение. Элементх е Z называется pos-числом тогда и только
тогда, когда02 <2 хр neg-числом тогда и только тогда, когда х <? Oz-
Докажите следующие утверждения.
3.10.	Сумма двух pos-чисел есть pos-число.
3.11.	Сумма двух neg-чисел есть neg-число.
3.12.	х есть pos-число тогда и только тогда, когда -(х)2есть
neg-число.
3.13.	Произведение двух pos-чисел есть pos-число.
3.14.	Произведение pos-числа на neg-число есть neg-число.
3.15.	Произведением двух neg-чисел есть pos-число.
4.6.	Сумма двух положительных чисел - положительное число.
4.7.	Сумма двух отрицательных чисел - отрицательное число.
При доказательстве некоторых из этих утверждений, может быть,
придется еще раз вернуться к анализу структуры множества Ми
определению отношения <N.
Дополнительная подсказка: может потребоваться более внима-
тельное рассмотрение классов эквивалентностей. Например, если
[<а,Ь>]ъ - положительное число, то рассмотрите отдельно случай!:
<z Ь,и случай 2: a <z 0z, b <% 0z.
48
Глава 5
ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА
ЗАДАНИЕ 20. Судя по изученному нами материалу может пока-
заться, что математика пытается поднять сама себя за волосы. Мно-
жество N было построено из пустого множества ф. Не хватало опера-
ции вычитания - и мы построили множество Z из самих задач на
вычитание. Недоставало операции деления - и из задач на деление
было создано множество >0; Чего же нам не хватает теперь? Вроде бы
немногого. Мы, например, не можем извлечь квадратный корень,
поскольку в Q нет такого числа, не хватает и многих других очень
важных чисел.
В рациональной числовой прямой обнаруживаются ’’дырки”. Если
мы рассечем линию надвое, то получим два множества:
-----------------------------/-------------------------------
Может оказаться, что множество слева имеет наибольший элемент:
{xeQ|x$3}
{xeQ|x>3}
или же в правом множестве окажется наименьший элемент:
. {xeQ|x<5}
)[
----------------------,
{xeQ|5«x}
но может оказаться и так, что ни одно из этих утверждений не будет
истинным:
{xeQ|x’<2}
{xeQ|x3>2}
Появилась дырка (в приведенном примере она должна быть
заполнена значением 3-/2). Потребуем, чтобы каждый раз, когда мы
рассекаем линию, появлялось число либо справа, либо слева. Тем
самым мы создаем множество R как множество сечений. Каждое
сечение представляется левым множеством. Свойство (2) включено в
определение сечения для того, чтобы множества {xeQ |х<3} и
{xeQ|x 3}не могли быть использованы для представления различ-
чих чисел.
49
7-3504
Есть что-то привлекательное в таком подходе. Мы все время
создаем новые числовые системы из ’’нерешенных задач”. Так, число
- 5 есть обозначение для неразрешенной задачи: какое число, сложен-
ное с числом 7, даст 2. Число 2/3 обозначает неразрешенную задачу:
какое число, умноженное на 3, равняется 2? И наконец, число 3^2 есть
тоже неразрешенная задача, попадающая в дырку между числами
{хе<0|х3<2}и {xeQ|x3 > 2}?
Перейдем к определению отношения <и . Когда одно сечение г
меньше другого s?
-------------------—)----------------------------------------,
Г
--------------------------------------)-----------------------
3
Ясно, когда rSs. А так как мы не хотим, чтобы г = s, то должны настаи-
вать на том, что r<=s.
5.3.	Пусть г = UX. Покажите, что г - сечение. Покажите, что это
наименьшая верхняя грань для X.
Это не единственно возможный способ построения множества
действительных чисел. Другой, более знакомый метод состоит в
разложении числа в бесконечную десятичную дробь. Еще один путь -
использовать классы эквивалентностей последовательностей Коши.
Отметим, что при всех подходах требуется обратиться к понятию
бесконечных множеств. Кронекер это понял и, как следствие, не
доверял действительным числам. Часто цитируют его заявление,
что числа л не существует.
ЗАДАНИЕ 21.
5.4.	Большую часть из четырех характеристик легко проверить,
если Вы знаете несколько лемм об отношении <Q. Возможно, Вам
пригодятся следующие утверждения:
а)х, у е Qвлечет ~(х +Q y)Q = ~(x)Q +q ~(у)о и (~(x)q)q = х.
б)	Дляw,х, уe Q,если w<QxHy <Q z, то w +Qy <ox +oz;
чтобы доказать это, воспользуйтесь
в)	леммой 4.6 (см. задание 19).
Не исключено, что на другом пути в поисках доказательства
потребуются не эти, а другие леммы. Имейте в виду графическое
представление сечения
	)	
(нет наибольшего элемента)---------(может быть наибольший элемент)
Мой учитель всегда говорил мне: ’’делай то, что у тебя под носом”.
Прекрасный совет для носатых. И все же в нем есть определенный
50
смысл. Например, чтобы показать, что если a <Q b и ber +Rs ,то
аег+дЗ, мы так и поступаем. Что нам известно? Мы знаем, что
be г+rs, и поэтому при некоторых xer,yes верно, чтоЬ = х +Q у.А
что мы хотим показать? Мы хотим показать, что при некоторых эле-
ментах х'еГ и y'es выполняется равенство а = х' +q у' Поэтому нам
остается найти два числа хх и у1, которые в сумме дают число а. Они
должны быть меньше, чем х и у; и если х^хиу^у, то мы автомати-
чески получим x/er, y/Gs-
Если возникают сомнения, то вначале испробуйте самый простой
способ, а если он не срабатывает, то разберитесь, почему. В нашем
примере самый простой способ - положить х! = х и просто считать, что
у/ меньше у. Пусть у1 меньше у в той же мере, насколько а меньше Ь,
т. е. пусть у' = у +q a +Q ~(b)Q. И, действительно, все получается.
ЗАДАНИЕ 22
5.5.	Для г, s, t е IR. полезно рассмотреть множество {xeQ|x =
= a +Q b +о с, aer, bes, cet}.
Определение. 0R = {хе Q|x <Q 0Q}.
Почему это сечение? Чтобы показать, что ^eORHe будет наиболь-
шим элементом, рассмотрите р = q -Q (1/(1Q +Q 1Q))Q. Заметим, что
q <o 0Qтогда и только тогда, когда ~(q)Qположительное число. А для
того чтобы показать, что ~(р)ц положительное число, рассмотрите
q +q (p)q +q~(p)Qiи воспользуйтесь теоремой4.7 (задание 19).
5.6.	Обратите внимание на то, что у вас ’’прямо под носом”. Совсем
нетрудно показать, что г +R 0Rsr. Для другого направления, т. е. если
г +R 0R<Rr, то найдется у:
г+о0о	г
Используйте тот факт, что в множестве г есть элемент z, больший чем
у, и что у +Q ~(z)QeOR.
ЗАДАНИЕ 23. Предположим, что нам задано число т:
-------------------------------------)---------------------
Г
а мы хотим найти противоположное ему число. Первая жех мысль,
которая приходит в голову, - обратить диаграмму:
Q\r
51
7'
т. е. рассмотреть множество {х е Q| "(x)Q е Q\r}:
~Ма	)
~ (г)ц
Единственное затруднение состоит в том, что множество может
иметь наименьший элемент
-------------------------------------)Е-----------,----------,
а это значит, что в “(г)и должен быть наибольший элемент.
----------------------](-------------------------------------
И что тогда делать?
При определении г -в s вначале рассмотрите случай, когда 0R <R г, s.
Используйте результат для завершения определения.
И вновь: множество Q может быть вложено в множество	Сумеет
ли читатель найти копию Q в №
Глава 6
ОРДИНАЛЫ
ЗАДАНИЕ 24. Здесь мы сталкиваемся с еще одним аспектом
многоликой индукции. При обычных обстоятельствах следующие
принципы (на любом линейно упорядоченном множестве) равно-
сильны:
1)	отношение < - отношение полного упорядочения:
2)	в любом непустом множестве есть наименьший элемент (по
отношению <);
3)	не существует бесконечно убывающих цепей а1>а2>а3> ...;
4)	(индукция) если свойство Р - истинное для первого элемента и
если всякий раз, когда свойство Р имеет место для всех х, которые
следуют за данным элементом г, оно должно быть верным и для z, то
свойство Р выполняется для всех элементов.
6.	2. Прежде чем приступить к доказательствам утверждений о множест-
венных ординалах, заметим, что для доказательства утверждения 1 не
требуется проверять антирефлексивность (почему?). Далее, не надо показы-
вать и то, что каждое подмножество содержит наименьший элемент, посколь-
ку это свойство вытекает из аксиомы регулярности.
Докажите следующие утверждения.
52
6.	2.а. Лемма. Если А - множество, то А имеет наименьший по
отношению е элемент, что приводит к такому следствию.
6.	2.6. Следствие. Множество X - ординал тогда, и только тогда,
когда:
1') отношение е удовлетворяет условиям транзитивности;
2	0 отношение е удовлетворяет условиям трихотомии;
3') если а&Ь^Х, то а еХ.
Теперь, возвращаясь к множеству I4J, покажите, что отношения
< N и е - это одно и то же для проверки следствий 1^2^ и тем
самым Вы проделаете уже почти половину работы.
Между прочим, очень легко спутать утверждения РиЗ7. Еще
хуже, что обычно свойство З1 выражают, говоря, что X. (множество, а
не отношение) транзитивное. Это не одно и то же. Ради интереса
найдите множество, обладающее свойством 1z, но не обладающее
свойством 3\ и укажите множество со свойством З1, не обладающее
свойством 1z.
6.3,	6.4. Вы можете проделать стандартную работу по доказательст-
ву, но часто можно найти более короткие пути. Попробуйте найти
ясные и прямые аргументы.
ЗАДАНИЕ 25
6.5.	Провести доказательство в одну сторону нетрудно. Для дока-
зательства в обратную сторону покажите, что а равно наименьшему
элементу множества 0 \ а.
6.6.	Что это значит? Совокупность всех ординалов может и не
оказаться множеством (и на самом деле это не множество). Если Вы
еще раз взглянете на определение линейного упорядочения для
множеств, то увидите, что определение имеет смысл и в настоящем
контексте, но лучше выписать его отдельно.
Вам нужно будет воспользоваться теоремой 6.5. В трихотомии,
если а Ф ₽, то либо а\₽, либо р\а будет непусто. Если, например,
а\ р + ф, то докажите, что множество р содержит наименьший элемент.
6.8,	6.9. Если Вы добрались до этого места, то вряд ли возникнут
затруднения с доказательствами. Однако стоит потратить усилия на
поиски наилучшего из возможных доказательств. Математика - это
отчасти искусство, и каждый математик (и тот, кто ее изучает) -
художник .
6.10.	На раннем периоде развития теории множеств понятие
’’множество всех ординалов” приводило к парадоксу почти столь же
знаменитому, как и парадокс Рассела. Парадокс Бурали-Форти
состоял в том, что поскольку множество всех ординалов Q - пол-
ностью упорядоченное, то в силу теоремы 6.13 оно имеет порядковый
53
тип а. Тогда а=2, и поскольку а + 1 тоже ординал, то а + 1 еQ, но а
- это ’’длина” Q, и если а + 1ей,тоа+1<а~ противоречие.
Наш вывод иэ этого рассуждения: Q - не множество. И чтобы
показать это, нет необходимости использовать теорему 6.13: достаточ-
но воспользоваться теоремами 6.8 и 6.9.
ЗАДАНИЕ 26
6.12.	От слов ’’трансфинитная индукция” передергивает многих
профессиональных математиков. Для специалиста в теории множеств
принцип трансфинитной индукции, наоборот, кажется очень простым.
Как отмечалось при обсуждении задания 24, утверждается всего лишь
простой факт: отношение е полностью упорядочивает ординалы.
Позже мы не раз воспользуемся этим принципом так же, как мы
пользовались методом индукции на множестве N, но с одним исклю-
чением. На N было достаточно показать, что:
1)	ф(0),
2)	если для каждого п выполняется ц>(п), то tp (п +N1). Этого
достаточно потому, что каждый элемент п из N есть либо 0, либо
может быть представлен в виде п + м 1 (для некоторого п). Это утвер-
ждение ложно в контексте трансфинитной индукции из-за наличия
предельных ординалов. Надо доказать, что
3)	если высказывание ф( а) - истинное при всех аеХи X-
предельный ординал, то ф( X) - истинное высказывание.
На практике проверка условий 1 и 3 обычно не вызывает затрудне-
ний, они возникают только при проверке условия 2.
ЗАДАНИЕ 27. Сначала надо сказать несколько слов о доказательст-
ве теоремы 6.13. В действительности мы собираемся построить поряд-
ковый изоморфизм. Для каждого полностью упорядоченного множест-
ва X покажем, что можно построить функцию /, отображающую одно-
значно определенный ординал в множество X, такую, что / будет
однозначное отображение ”на”, сохраняющее порядок, т.е. такое, что
aG₽ тогда и только тогда, когда /(«)</(₽). В таком случае
ординал имеет в точности ту же длину, что и множество X. Оба мно-
жества могут быть линеаризованы согласованно друг с другом без пе-
реупорядочения каждого из них с сохранением соответствия между
элементами. Это - узловая идея для определения операций + 0 и • 0.
Для понимания операции +0 представьте себе сложение о +01
следующим образом. Возьмем последовательность символов (квадра-
тиков) длиной q:

и один символ длиной 1:
□
S4
и поместим его за последовательностью:
В результате получим
- ординал, следующий за ы или S(q). Теперь предположим, что мы
складываем 2 +оы. Возьмем последовательность квадратиков дли-
ной 2:
□ □
и одну последовательность длиной о:
и разместим вторую последовательность за первой:
(□□)(□□□•••).
В результате получим
□ □□□□•••
цепочку квадратиков длиной ы! Если это вам покажется странным, то
представьте себе гигантский измерительный инструмент для измере-
ния порядковых типов полностью упорядоченных совокупностей.
Инструмент состоит из бесконечной последовательности ячеек:
0	12	ш 8(а>)
Чтобы измерить последовательность квадратиков, помещаем их
последовательно в ячейки прибора до тех пор, пока все они не ока-
жутся размещенными по ячейкам. После этого считываем число,
указанное под первой пустой ячейкой. При измерении длины ы +0 1
(□□□•")(□)
сначала квадратики из ы заполнят первые ы ячеек, причем последний
квадратик займет ячейку ы. Первой свободной ячейкой оказывается
ячейка с номером S( w). При измерении длины 2 + оы
(□□)(□□□•••)
первые два квадратика заполнят ячейки 0 и 1. Первый квадратик из ы
попадет в ячейку 2, следующий за ним - в ячейку 3, и т. д. Немного
подумав, Вы поймете, что ни один из квадоатиков не попадет в ячей-
ку о, но каждая конечная ячейка будет заполнена, поэтому первой
пустой ячейкой окажется ячейка ы.
55
Результат операции -0 рассчитывается таким же образом. Пусть
требуется перемножить о -03. Мы берем три экземпляра о-цепей из
квадратиков и размещаем их одна за другой:
••• )"
<0	<0	СО
В результате црлучим последовательность
□ ••• □ □ □ •••
известную как ы +оы +оы.
Теперь Вы наверное поняли, что сложение +0 некоммутативное,
умножение -0 тоже, нечто необычное получается и с дистрибутив-
нрстыо.
Глава?
КАРДИНАЛЬНЫЕ ЧИСЛА
ЗАДАНИЕ 28
7.1.	Напомним, что для доказательства неравенства ПАН < И ВII
необходимо найти однозначное соответствие из множества А
в (нет необходимости в ”на”) множество В. Если нужно дальнейшее
наводящее соображение, то припомните рассказ Георга Гамова об
отеле с бесконечным числом комнат, пронумерованных 1, 2, 3, ... В
заполненный отель приехал путешественник и попросил комнату.
Управляющий сказал, что есть сколько угодно свободных мест и
попросил каждого жильца переместиться в следующую по номеру
комнату отеля (например, гость из комнаты 76 перемещается в комна-
ту 77 и т. д.). В результате комната 1 освобождается для прибывшего
путешественника.
7.2.	С целью дальнейшего использования этой теоремы полезно
думать о множестве Z как о совокупности чисел вида {..., -2, -1,0,
1, 2, ... }. Доказательство в одну сторону несложно. Приступая к
доказательству в обратную сторону, вспомните о гамовском ртеле.
Теперь в отель прибывает бесконечное число новых гостей. ’’Нет
проблем!” - говорит управляющий и просит каждого жильца пере-
ехать в комнату с удвоенным номером (например, жилец комнаты 76
переезжает в комнату 15*6 и т. д.). Все комнаты с нечетными номерами
оказываются свободными, и их достаточно, чтобы разместить вновь
прибывших.
7.3.	Для доказательства этой теоремы представим себе множество
Q как множество дробей вида а/b, где a,bG Z (так оно и есть).
56
Доказательство в одну сторону несложно. К доказательству в другую
сторону можно подойти разными путями. Проблема окажется решен-
ной, если мы сумеем расположить в линию все рациональные числа
Г1’ Г2> гз> •••
Начнем с того, что выпишем подряд все дроби, которые можно образо-
вать из чисел { -1, 0, 1 }, затем добавим числа, которые можно полу-
чить с помощью {-2,2},...
ЗАДАНИЕ 29
7.4.	На первый взгляд кажется, что доказать теорему нетрудно, но
это не так. Допустим, что заданы однозначные отображения /
из А в В и g из В в А. Дело в том, что ни одно из них не обязано быть
отображением ”на”:
f(X) для множества [f(x)\ х еХ},
g(Y) для множества {g(y)\y^Y}.
Мы используем метод, при котором множество А разбивается на
два подмножества Za A\Z, а множество В - на подмножества f(Z)n
*\f(Z):
Отображение f однозначно отображает множество Z на мно-
жество f(Z). Если множество Z будет выбрано правильно, то отображе-
8-3504
ние g однозначно переведет множество B\f(Z) на множество
A\z и мы построим однозначно определенную функцию h, положив
h(x)-y, еслихе/и f(x) = y,
h(x)=z, если x^A\Zn g(z) = х-.
Основная трудность состоит в нахождении подходящего множества Z.
Начнем с определения функции Н из множества Р(А) в множестве
Р(В),т. е.
Н(Х) = A\g(B\f(X)):
Пусть Z = {деД для некоторых XqA,аеХи Х^Н(Х)}. Докажите:
1.	Если Х<= Y, то H(X)<=H(Y).
2.	Z^H(Z).
3.	Функция g отображает множество B\f(Z) bA\Z. [Подсказка:
предположим, a<sB\f(Z)w. g(a) = b&Z. Тогда Ь^Х^Н(Х) пул некото-
58
ром множестве Х^А. Имеем b^H(Z) (почему?). Покажите, что это
невозможно.]
4.	g отображает B\f(Z) на A\Z. [Подсказка: предположим, что
b^A\Z. Поскольку b$Z, то ZU{b} не содержится в множестве
H(ZU{b}). Поскольку Z^H(Z)^H(Z0{b}), то должно быть b^H(ZU{b]).
Покажите, что при некотором a^B\f(Z) выполняется равенство
b=g(a).]
5.	Определенная выше функция h есть однозначное отображение А
на множество В.
7.5. Никаких затруднений тут не возникает. Заметим, что согласно
еще одному следствию теоремы7.4. Hull = IlSfujll. Как уже упомина-
лось, сейчас мы измеряем не длины множеств, а их размеры. Два
множества
ы	: 0	1	2	3	4	...,
S(u)	: 0	1	2	3	4	... ы
имеют различную длину. Они не порядково изоморфны. Однако это
множества одного и того же размера, поэтому если мы иначе ранжи-
руем S(a), то получаем
о	:0	1	2	3	4	...,
S(u)	: ы	0	1	2	3	...
Мы получили функцию f из „со в S(w), т.е. однозначное отобра-
жение ”на” (0 переходит в о, 1 переходит в 0, 2 переходит в 1 ...), но
это отображение не сохраняет порядок (см. пояснения к заданию 27),
поскольку Л1) еДО), но 1
ЗАДАНИЕ 30. 7.6. Приблизительно 100 лет назад Кантор открыл,
что размеры бесконечных множеств различны. Обе теоремы, 7.6 и 7.7,
получены им. Предположим, что ||Р(А_)||<||АЦ. Тогда по теореме
Шредера - Бернштейна ~Р(А)" = “А”'. Пусть / - однозначное
отображение А на множество Р(А). Пусть С = {xeAix^f(x)]. При
некотором элементе х&А имеет место равенство С = f(x) (почему?).
Верно ли, что x^f(x)2
7.7. Изложим три подхода к проблеме.
ДОКАЗАТЕЛЬСТВО 1 (’’диагональное” доказательство Кантора).
Это очень простое, приятное, тонкое и наиболее удивительное из
математических доказательств. Когда автор этой книги впервые
познакомился с ним, будучи еще совсем молодым студентом, он
Решил, что если это то, чем занимаются математики, то он хочет быть
математиком.
Примем десятичное представление множества R. Поскольку
59
8’
утверждение II ы II < II IR II явно истинное, то при || R II < II ы II по теоре-
ме Шредера-Бернштейна мы бы имели II ы 11= II R ||. А это означало
бы, что существует взаимно однозначное соответствие между действи-
тельными и целыми положительными числами. Пусть уже есть такое
соответствие	1 2-г2,
в котором появляются все действительные числа. Покажем, что такое
предположение невозможно. Проиллюстрируем процесс:
0«->.	23.718044382...
1«->	-.032196149...
2+-*	326.461988823...
3«-	7.102470065...
4+-*— 13.320795213...’
5«-> 206.423630912...
и допустим, что полный список содержит все действительные числа.
Рассмотрим выделенные цифры
0+-*	23.718044382...
1+->	-.032196149...
2+-*	326.461988823...
3	7.102470065...
4<—* — 13.320795213...
5«-> 206.423630912...
60
Построим новое число, добавляя единицу к каждой выделенной
цифре (если это не цифра 9, которая уменьшается на lh
г = .842581....
Покажите, что вопреки нашим предположениям это число не появится
в списке.
ДОКАЗАТЕЛЬСТВО 2. Поскольку R w II < I1P(g>) II. то покажем,что
НР(со)II < II R II; затем покажем, что если НАЦ < ЦВИ<IICII, то ||А||<||С||.
Пусть для первого условия f - отображение из множества P(q) в
множество R:
f(K)=Z 10-п для всех КеР(и).
пек
ДОКАЗАТЕЛЬСТВО 3. Поступим так же, как и при доказательстве
1, только вместо десятичного разложения используем сечения. Пред-
положим, что найдено взаимно однозначное соответствие:
0~го,
2 ** г2,
где каждое г - сечение. Найдем сечение, которое здесь пропущено.
Этого можно добиться с помощью двух последовательностей сечений:
4o 3l 32........ *2 *1 *0»
где все сечения s. меньше, чем все сечения t}. Обозначим через г
наименьшую верхнюю грань сечения s.. Заметим, что г всегда располо-
жено между 5{Я t..
Нулевой шаг. Выберем сечение s0 так, чтобы r0<s0. Поскольку
$0<г, то, значит, г0 #= г. В то же время выберем сечение так, чтобы
so<^o:
----------------+	+	+--------
Го--------------------------------------------------------*0-*0
Первый шаг. Рассмотрим . Если r\ <s0:
--------+	+	+--------
Г1--------------------------------------------------------»0-«о
ИЛИ f0<ri:
---------------------------+---------------------------+ +
«о-----------------------------------------------»о П
то мы знаем, что г будет отличаться от rt, поэтому положим st = s0,
t± = t0 и перейдем к следующему шагу:
61
I------------------1------------------
SO	to
s>	.‘1
В противном случае, когда s 0 г t f 0:
------------------------+	+	+---------------
«О-------------------------------------------------------------Г1-«о
либо выберем сечение s t, такое, что r1<s1<l0, и положим tt = t0:
-----7 —----------------+----------+ + +----------------------
So	rl	*0
31 '1
либо выберем tlt такое, что в0<^<г1( и положим Sj =s0:
-----------------------+ — + _ +	+---------------
so	Г1-*0
S,
В любом случае сечение rt не оказывается между st и ft. Второй шаг
аналогичен первому, только мы в этот раз имеем дело с г2. На каждом
шаге убеждаемся, что число г, которое в конце концов построим, не
равно гп:
s0<s<s2<...<r< ...^t3^t^t0.
Примечание. В этом доказательстве, как кажется, использована
аксиома выбора, поскольку мы выбираем из бесконечного числа
сечений. Однако доказательство можно видоизменить таким образом,
чтобы выбору подлежали элементы из множества Q. Например,
вместо прямого выбора s0 выберем q0 е Q и положим
s0 = {xeQ|x <Q 4о}-
Мы можем выбирать элементы из множества Q , поскольку оно
полностью упорядочено (теорема 7.5), а полностью упорядоченное
множество позволяет нам делать выбор (теорема 7.10).
7.8. Пусть а = UA. Если ₽ еи и II3 It = Ball, то покажите, что й у И
< II р II при некотором значении у, таком, что ₽ еА.
1.9. Смотрите обсуждение теоремы 7.5.
ЗАДАНИЕ 31
7.13.	Докажите, используя индукцию по основанию и. Для индук-
ционного шага предположите, что функция/ однозначно отображает п
1 на собственное подмножество п +.1. Определите h:
l-W
h(k)=f(k), если f(k) Ф n,
h(k) =f(n), если f(k) = n.
Покажите, что h - однозначное отображение n на собственное подмно-
жество п.
62
7.14.	Предположите, что f однозначно отображает на множество
X, и примените теорему 1.11.
7.15.	Введите полное упорядочение на множестве X и примените
теорему 6.13.
7.16.	Соберите функцию, определенную теоремой 7.15, с последую-
щей функцией.
ЗАДАНИЕ 32
7.17.	Сказать, что множество X- счетное, то же самое что сказать,
что оно ’’списочное”, т. е. утверждать, что можно выписать все его
элементы и список будет иметь длину < ы (либо множество X - конеч-
ное, и в этом случае можно выписать его элементы, сформировав
конечный список, либо это множество бесконечное, но существует
однозначное соответствие из ы в X, и тогда /60), / (l),f (2),...
составит список элементов длиной ы). Расположим в строку список
элементов множества X:
^1’ %2’ %3 "•
и выпишем в столбцы список элементов каждого элемента х{:
*0	*1	х2	*3
ао,о	а1,0	а2.0	аЗ,0
аО,1	«1.1	°2.1	а3,1
а0.2	а1.2	а2,2	а3,2
аО.З	а1,3	а2,3	а3,3
Некоторые из столбцов могут оказаться конечными. Теперь
составим список тех же элементов следующим образом:
О ** ao,oi
1 ~ «О,1>
2 ** °1^0>
4 ~ а1,1>
5~%0-
Если некоторый элемент а появляется в списках двух различных
элементов множества X, то он окажется в этом списке дважды. Если
такое произойдет, то мы просто исключим повторения, тем самым
добившись однозначного соответствия.
В каком месте доказательства использована аксиома выбора?
7.18.	Воспользуйтесь теоремой 7.17.
7.19.	Воспользуйтесь теоремой 7.6, теоремой о полном упорядоче-
63
нии и теоремой 6.13. Пусть при заданном К ординал у будет наимень-
шим, таким, что ||Р(К)|| — у.. Докажите, что у - кардинальное число и
что К < у-
Еще одним парадоксом ранней неформально излагаемой теории
множеств был парадокс Кантора: пусть К - множество всех карди-
нальных чисел. Тогда согласно теореме 7.8 объединение UK будет
кардинальным числом и наибольшим кардинальным числом. С другой
стороны, в силу теоремы 7.19 не существует наибольшего кардиналь-
ного числа. Каким образом можно разрешить это противоречие?
ЗАДАНИЕ 33
7.20.	Определим упорядочение <х на множестве X условием
а<хЬ тогда и только тогда, когда f(a)^f(b).
7.21.	Пусть задано кардинальное число К, пусть А = {01 и сущест-
вует полное упорядочение на X порядкового типа 0}. Используя
аксиому замещения, докажите, что А - множество. Докажите, что
у = U А - кардинальное число, большее К ; для этого предположите,
что для некоторого а<у выполняется равенство II ixII = II у II- Ответьте
почему:
1)	а® 0еА при некотором 0;
2)	НуН= 11011;
3)	существует однозначная функция из Хна у;
4)	уеА;
5)	у+01еА;
6)	противоречие!
Глава 8
УНИВЕРСАЛЬНОЕ МНОЖЕСТВО
ЗАДАНИЕ 34
8.2.	Это наше первое доказательство методом трансфинитной
индукции. Предположим, что задан ординал а и для всех 0 < а теорема
верна, т. е. хеуеУр влечет xeV$. Предположим хеуеу^. Вам
потребуется разбить задачу на несколько подзадач для случаев:
Случай 1. а = 0;
Случай 2. а = 0 +01 при некотором 0;
Случай 3. а - предельный ординал.
8.3.	Воспользуйтесь методом трансфинитной индукции по а. Предполо-
жите, что теорема спрвведлива для всех р < а. Докажите, что при всех
б < а выполняется включение У. с у
о а
64
ЗАДАНИЕ 35
8.4.	Доказательство этого очень простого утверждения потребует
определенной работы и использования нескольких стандартных
теоретико-множественных приемов. Ключ к решению, хотя это и не
очевидно, - регулярность. На самом деле это утверждение эквива-
лентно аксиоме регулярности.
1.	Схема доказательства: предположим, что теорема не верна.
Найдем множество х, не содержащееся ни в одном из Va, но каждый
элемент которого принадлежит какому-нибудь Va (хотя элементы и
могут попадать в разные Va). Затем найдем единственное значение р,
такое, что каждый элемент из х принадлежит Ур. Отсюда будет следо-
вать, что хе у₽ + х (почему?).
2,	Для нахождения х вначале предположим, что z - множество, не
содержащееся ни в одном из У . Если этого недостаточно (т. е. если
в множестве z есть элементы, которые не попадают в какое-нибудь
Уа), то мы построим так называемое транзитивное замыкание мно-
жества z: T(z) = zU(Uz)U(UUz)U (UUUz)U ...; почему оно будет множест-
вом? Это пример типичного применения аксиомы замещения. Мы
определяем функцию f с областью определения о таким образом,
чтобы/(0) = z;/(1) = Uz;/(2) = UUz ...; тогда область значений R функ-
ции /будет множеством, a U7? будет множеством T(z). Аксиома заме-
щения требует, чтобы эта функция была определяемой. Мы должны
найти формулу Ф, такую, чтобы Ф (а, Ь) была истинной тогда
и только тогда, когда [(а) = Ь. Утверждением, соответствующим
формуле, будет
”3/(/- функция и f(0) =z, и при всех	выполняется равенство
f(n + 1) = U/ (п), inf (а) = Ь). ”
Выпишите это высказывание на символическом языке, используя
принятые сокращения.
3.	Теперь у нас есть T(z), причем выполняется следующее свойст-
во: если cede T(z), то се T(z)(почему?).
4.	Пусть У = {s<= T(z)\ s не принадлежит Уа). Посредством аксиомы
содержательности удостоверимся, что У - множество. (Как можно
выразить утверждение ”s не попадает ни в одно из Va ” на языке Я ?)
5.	Поскольку имеются элементы из множества z, не попадающие ни
в одно из множеств Va, то У 4= ф. В силу аксиомы регулярности
существует множество х^У, такое, что хП У = 0. Это и есть искомое
множество, т. е. каждый элемент q&x принадлежит какому-нибудь Va
(почему?).
6.	Наконец, нам нужно найти ₽ такое, чтобы каждый элемент q&x
принадлежал Уд. Определим на множестве х функцию g условием
65
9-3504
g(q)=”наименьший ординал а, такой, что qsVa”; это определяемая
функция. По аксиоме замещения область значений R функции g будет
множеством. Покажите, что ₽ = U R и есть искомый ординал.
Замечание 1. На самом деле имеется не так много математических
доводов в пользу аксиомы регулярности. Почти все классические
математические результаты могут быть получены без нее. Отказ от
аксиомы изменит содержание понятия универсального множества, но
оно все же может быть введено. С другой стороны, аксиома регуляр-
ности наводит довольно удовлетворительный порядок в иерархии
множеств, который при отказе от нее будет утрачен. По этой и другим
причинам аксиома регулярности стала частью стандартной теории
множеств.
Замечание 2. Очень важно, что из этого и других доказательств
становится ясным, что некоторые обычные высказывания могут быть
выражены на языке и, таким образом, множества функций, кото-
рые они описывают, - определяемые. Мы уже имеем некоторый опыт,
например, при использовании допущений типа функция”, “Л. -
ординал” и т. п. По мере дальнейшей работы с понятиями теории
множеств приходит понимание того, что может быть выражено на
символическом языке, а что - нет. И действительно, в некоторых
областях математики (таких, например, как дескриптивная теория
множеств) нужно научиться различать дополнительные тонкости
такого типа, как выбор допустимой ранжировки квантификаторов.
• ЗАДАНИЕ 36
8.5. В каком-то смысле утверждение очевидно. Но каким образом
конечное множество (11x11 <ы) может достигнуть ы? И все же способ
доказательства виден не сразу.
Пусть задано множество X, IIXII = п <ы. Поскольку множествоX -
полностью упорядоченное отношением <, то существует функция —
однозначное соответствие из ординала а наХ. Докажите:
1)	X— конечное по Дедекинду множество;
2)а<ы;
3) а = S(k) при некотором к;
4)/(k) = UX;
5) UX<G).
8.7.	Воспользуйтесь теоремой 7.12.
ЗАДАНИЕ 37
8.9.	Допустим, что утверждение неверно. Пусть ординал а -
наименьший, такой, что II Va II - не менее чем к. Возможны два случая:
а - последующий ординал и а - предельный ординал. Чтобы разо-
браться со случаем предельного ординала, рассмотрим
66
однозначное отображение f из множества к на Va. Пусть для каждого
£<а Хр = {6е кI/(бVp}. Докажите, что:
1)	11ХрН<кпривсех ₽<а;
2)	UXp<k при всех ₽ < а;
3)	U{UХр| ₽<а}<к;
4)	это - противоречие.
ЗАДАНИЕ 38
8.10.	С большинством аксиом станет довольно легко работать, как
только Вы поймете, что Вам требуется доказать. Рассмотрим, напри-
мер, аксиому пары. Нам надо показать, что если х,у^ Vk, то [x,y]sV,(.
Мы работаем в рамках ZF-теории, поэтому {х,у} есть множество. Надо
показать, что оно содержится в Vk. Воспользуйтесь тем, что
Vk = U[Vaia<k}.
Теорема 8.2 часто оказывается очень полезной.
При проверке аксиомы бесконечности методом трансфинитной
индукции докажите, что а<= V„ . . для любого ординала а.
о
Для проверки аксиомы замещения надо доказать только то, что
если /- функция с областью определения Xе Vk и определяемая в Vk,
то область значения этой функции есть множество из Vk. По аксиоме
замещения область значения R функции / есть множество. И нам
остается показать, что ^GF(c. Высказывание ’’определяемая в Vk”
влечет то, что при всех аех справедливо f(a)^Vk. Воспользуйтесь
приемом 6, примененным при доказательстве теоремы 8.4.
В действительности мы можем показать и большее: Vk - модель
теории ZFC.
Глава 9
ВЫБОР И БЕСКОНЕЧНО МАЛЫЕ ЧИСЛА
ЗАДАНИЕ 39
9.1.	Идея доказательства довольно проста, хотя само доказательст-
во и не очень просто. Допустим, что задано множество X, которое
требуется полностью упорядочить. Выберем какой-нибудь элемент из
этого множества. Обозначим его аг и назовем первым элементом
множества X. Затем выберем еще один элемент из X. Обозначим его а2
и назовем вторым элементом множества X. Продолжим в том же духе,
пока все элементы не окажутся упорядоченными.
Однако тут возникают два затруднения. Во-первых, мы выполня-
ем слишком много актов выбора, каким образом это можно сделать?
67
9
Во-вторых, даже когда мы можем провести все элементарные акты
выбора, описанный нами процесс может занять бесконечно много
времени (о шагов может оказаться недостаточно, но и о +оы,ы-оы и
даже К j шагов все еще будет мало). Что дает нам уверенность в
окончании процесса?
Пусть У = Р(Х)\[ф] (множество всех непустых подмножеств
множества X). Пусть h - функция выбора на множестве У, т. е. для
любого множества А«У, h(A)^A. С ее помощью разрешаем первую
трудность - проведение единичных актов выбора:
Oj = h(X), a2=h(X\{ о J), a3 =	o2}),...
Для разрешения второго затруднения воспользуемся теоремой об
индуктивном определении. Пусть f - функция, определенная из
условия
f(A) = h(X\A), если Х\А * ф.
Применим теорему 6.14 к функции f для того, чтобы получить новую
функцию g. Докажите, что:
1)	g - однозначное соответствие;
2)	область значений g есть множество;
3)	область определения g-1 есть множество;
4)	g~1 и g - функции;
5)	область определения функции gесть ординал б;
6)	область значений функции g, определенной на ординале б, есть
множество X;
7)	множество X -> полностью упорядоченное.
[Дополнительная подсказка: просмотрите доказательство теоре-
мы 6.13.]
9.2.	Задано множество X и частичное упорядочение <х на этом
множестве. И снова идея доказательства довольно примитивная:
попросту выбираем один за другим элементы из множества X. Выбе-
рем элемент а0. Если это не максимальный элемент, то выберем
элемент, больший чем а0. Если и он не максимален, то выберем еще
больший элемент, и т. д. После того, как число выбранных элементов
достигнет о, получим цепь а0<ха1 <ха2<х По предположению, эта
цепь ограничена, т. е. существует элемент ио, который превосходит
все элементы цепи
°о "''х0!	<"х°со-
Если элемент аи не максимален, то выберем следующий, больший чем
аи, и т. д. И снова те же вопросы: каким образом можно провести
68
такое количество элементарных актов выбора и как узнать, окончится
ли когда-нибудь процесс?
Воспользуемся теоремой Цермело и полностью упорядочим отно-
шением «х (которое почти наверное будет отличаться от отношения
<х) множество X. Воспользуемся отношением <<х, чтобы произвести
акты выбора (элемента оо, <<х-наименьшего элемента в множестве
X, элемента alt <<х-наименьшего элемента в X, который >ха0).
Теперь определим
f(A) = < <х-наименьший элемент множества X среди тех элемен-
тов, которые >х всех элементов из А (если есть хоть один).
Вновь применим теорему 6.14 к функции f, чтобы получить функ-
цию g. Докажите положения 1-5, приведенные при обсуждении
теоремы 9.1 и докажите, что
6х) область значений g есть цепь в множестве X.
Пусть а - область определения функции g. Докажите:
7х) ординал а - последующий за £ +01;
8') элемент g( £) - максимальный.
ЗАДАНИЕ 40
9.3.	Задано множество X, и от нас требуется найти функцию выбо-
ра, т. е. при у е%и у =# 0 такую функцию f, что f(y)ey- Для единствен-
ного множества у не представляет труда указать его элемент. Также
легко можно привести и любое конечное число актов выбора. Труд-
ности связаны с бесконечными числами.
Проблему решим, используя Лемму Цорна. Рассмотрим множество
Р = {///“ функция, определенная на DQX и такая, что для всех уеЦ
уф 0 выполняется условие f(y)^y}. Каждый элемент множества Р
есть ’’частная” функция выбора. С ее помощью можно провести неко-
торые акты выбора, но, как правило, не все, т. е. для большинства
функций f область D<=X. Определим упорядочение <р на множестве
Русловием
/< pg тогда и только тогда, когда f<=g. Докажите, что:
1)	<р - отношение частичного порядка;
2)	каждая цепь ограничена;
3)	максимальный элемент множества Р представляет собой полную
функцию выбора. [Подсказка: пусть f - максимальный элемент в
множестве Р, у&Х, у Ф ф. Покажите, что если у не принадлежит
области определения /j то существует функция g^P, такая, что f<pg.]
9.4.	Чтобы легче понять проблему, давайте представим себе, что
ll есть совокупность ’’больших” множеств. Тогда свойства ультра-
фильтров можно переформулировать следующим образом:
а)	если два множества - большие, то они настолько большие,
чтобы их пересечение было большим множеством;
69
б)	конечное множество - не большое;
в)	каково бы ни было множество А, либо оно большое множество,
либо его дополнение есть большое множество.
Построение ультрафильтра представляет собой бесконечный
процесс принятия решений. Для заданного множества А следует
решить, будет ли оно или же множество ы\А большим множеством?
Для некоторых множеств решение легкое, например множество 1, 3, 8
не может быть большим, поэтому множество {0, 2, 4, 5, 6, 7, 9, 10,...}
должно быть большим. Для других множеств, таких как {1, 3, 5, 7, 9,
И, 13,...}, ясного ответа не существует. В действительности не играет
никакой роли, какое из таких множеств мы примем за большое, лишь
бы результирующая совокупность множеств удовлетворяла условиям
а) - в). Большое ли множество {1, 3, 5, 7,...}? Для некоторых ультра-
фильтров - да, для других - нет.
Доказательство этой теоремы дает еще один пример применения
леммы Цорна. Пусть Q = {иеР(ы)/и удовлетворяет условиям а) и б)
определения ультрафильтров}. Определим упорядочение <qусловием
u<qv тогда, и только тогда, когда и<= v. Докажите, что:
1)	отношение < - отношение частичного порядка;
2)	множество Q - не пустое;
3)	каждая цепь - ограниченная и
4)	максимальный элемент - ультрафильтр. [Подсказка: если и не
максимальный элемент и не ультрафильтр, то существует множество
Аеы, такое, что ни А, ни ы\А не содержатся в элементе и. Покажите,
что по крайней мере одно из этих множеств бесконечное и имеет
непустое пересечение со всеми элементами в и. Обозначьте это мно-
жество буквой S. Покажите, что и < q v = и U {ВЛ SI Be и} «в Q. ]
ЗАДАНИЕ 41
9.5.	В выполнении задания поможет доказательство следующей
леммы.
9.5а	. Лемма. Если А е % и A QB, то В е %.
9.7.	Рассмотрите[Я] s ,где Н(п) = п при всех п е ш.
Когда примерно 100 лет назад понимание ’’бесконечно малых” как
очень маленьких чисел перестало пользоваться популярностью,
авторы учебников, не желая отказываться от этого понятия, стали
описывать их как переменные, сходящиеся к нулю. Ирония в том, что
 именно так мы их здесь и рассматриваем. По существу, это последова-
тельности, предел которых (как следует из определения в анализе)
равен 0.
70
ЗАДАНИЕ 42. Очевидный выбор операции +н? будет[/]s+hi =
=[k]s, где h(n) ~f(n) +R д(и)при всех пец. В качестве упражнения
вам надлежит показать, что операция+н? корректно определена.
При рассмотрении случаев 1 - 5 полезно представлять себе Н как
И g, К как [k] s, I как [ i ] s и J как [ j] s, г де h, k, i и j принадлежат X.
Вы обнаружите, что случаи 1 и 2 нетрудные. Рассмотрим случай 3.
Ясно, что I+ж •/удовлетворяет условиям 1 и 3 определения бесконеч-
но малой, а как насчет условия 2? Пусть г е [R есть положительное
действительное число. Верно ли, что{пбси||(и) +rJ'(h) <r г) принад-
лежит множеству ^Поскольку IhJ- бесконечно малые, то мы знаем,
что множество {neco|i(n) <R г} и множество {и e(o|j (и) <r г} принад-
лежат <%, но пользы от этого не очень много. [Подсказка: рассмотрите
множество {и е со|i(n) <R r/2}.]
Для доказательства случая 6 предположим, что существует наи-
большее конечное гипердействительное число[д]а.Поскольку[д]£ -
конечное, то существует число г е IR такое, что[д]$<ж [Л]$®°змож‘
но ли это?
Рассматривая случаи 9 и 10, имеете в виду теорему 9.9.
Приведем пример использования HR в анализе.
Определение. Функция / из IR в SR называется непрерывной в точке
г тогда и только тогда, когда для всех бесконечно малых I значение
f(r + 1) бесконечно близко значению f(r).
Хотя IR есть область определения функции /, но любая, определен-
ная на [R функция может быть также определена и на HR (можно вос-
пользоваться теоремой 9.9 или прямым вычислением).
Определите, например, будет ли функция у = х2 непрерывной в
точке 2. Если I - бесконечно малое число, то
f(2 +1) = (2 +1)2 =4 + 21 +12.
Числа 21 и I2 - бесконечно малые (как в вышеприведенном случае 2).
Число 21 + I2 - бесконечно малое (как в случае 3), поэтому /(2) = 4
бесконечно близко значению /(2 +1).
Заключительное замечание: использование бесконечно малых
чисел существенно облегчает математический анализ. В основном,
однако, ими лучше всего пользуются на интуитивном уровне. Напри-
мер, мы ежедневно пользуемся понятием действительного числа, не
задумываясь о сечениях. Мы часто складываем целые числа, не беспо-
коясь о классах эквивалентностей. Подобным же образом мы можем
обращаться и с бесконечно малыми и с бесконечно большими числами,
если просто будем полагаться на хорошее ментальное представление о
них, как это делали наши предки.
71
Глава 10
ТЕОРЕМА ГУДСТАЙНА
ЗАДАНИЕ 43. Эти функции кажутся хитро устроенными, но идея
их построения простая. Функция Sn - это функция, которая в каждом
целом числе, записанном по супероснованию п, меняет каждое число п
нал + 1. Функцияgn - функция, которая преобразует целое число за п
шагов алгоритма Гудстайна.
3. Для разминки попробуйте проделать следующие упражнения.
Предположим, что:
а)	на 91-м шаге процедуры мы получили 13-93° (по основанию 93);
не имеет никакого значения, каким образом мы пришли к такому
результату; как много еще потребуется шагов, чтобы получить зна-
чение 0?
б)	на 35-м шаге процедуры мы получили 1 • 37 (по основанию 37);
как много еще потребуется шагов, чтобы получить значение О?
в)	на 43-м шаге мы получили 2 • 45 (по основанию 45); как много
еще потребуется шагов, чтобы получить значение 0?
г)	после первого шага мы получили 2 • 3 2 + 2- 3 + 2 (по основанию 3);
как много потребуется шагов, чтобы свести к нулю крайний правый
член; средний член?
ЗАДАНИЕ 44. Идея, на которой основывается это сложно выглядя-
щее доказательство, совсем не сложна. Если на п-м шаге заменить
каждое число п на ы, то получим ординал. Если проделаем это на
каждом шаге, то получим последовательность убывающих ординалов,
т. е. ординал, который мы получаем на шаге 125, больше ординала,
который получим на шаге 126, и т. д. Поскольку не может существо-
вать бесконечно убывающей последовательности ординалов (ордина-
лы полностью упорядочены), то последовательность должна закон-
читься нулем.
Функции fn - это функции, замещающие п на ы.
10.2.	В дополнение к сказанному напомним, что при заданном
основании п любое целое число т>0 может быть записано в форме
где m>d и при каждом i выполняется неравенство 0^k,<n. Для
основания п такое представление единственно. Поэтому, желая
доказать по индукции некоторое утверждение о целых числах т, вы
можете доказать, что оно верно
1)длят = 0и,
72
2)	если оно верно для всех i<d, что оно верно и для
d
т = 1дк(П‘
при любых к0, кkd<n.
10.3.	Воспользуйтесь методом индукции. Сначала удостоверьтесь,
что лемма справедлива при 0. Затем предположите, что она верна при
всех целых числах, меньших чем т, и запишите т в виде
kdnd +kd_jnd-J+ ... +ktn + к0,
где 0 < kf < п для всех i < d. Рассмотрите
случай 1: к0<п -1, а затем
случай2: ks<n - 1, но к(= п -1 при всех i<s.
В случае 2
т = kdnd + ... + ksns + (n - 1 )ns~l +... +(п-1),
т + 1 = kdnd + ... + (ks + \)ns.
Затем
fn(m) =fn(kdnd +... + ks+1ns+1) + fn(ksns + (n-1)^-1 +... + (n -1)),
в то время как
fn(m +1) =fn (kdnd +... + ks+1ns+1) + fn ((ks +1 )ns).
И, таким образом, будет достаточно показать, что fn (ks ns + (п - 1)	+
+... + (п - 1)) меньше, чем f„ ((ks +1) ns).
10.4.	Вы почти у цели: соберите вместе предыдущие леммы.
10.5.	Рассмотрите последовательность f3(g2(m)), fA(g3(m)),
f5(gA(m)),...
10-3504
ЧАСТЬ III
РЕШЕНИЯ
Глава 1
ЛОГИКА И ТЕОРИЯ МНОЖЕСТВ
ЗАДАНИЕ 1.
1. а)Т; 6)F ; в)F; г) т; д) Т; е) F; ж) F; з)т; и) F (с не подмножество
множества е); к)Т (е - подмножество множества а); л) Т (d- непустое
множество); m)F (например, a); h)F; о)Т (е - собственное подмножест-
во множества); п) F (е - не имеете двух различных элементов).
2. о) i®e, *eh, h = е
(i^e-+i^h)
)h = e
(6'®e-,’ieh)A]h =e)
V i((iee-*ieh)A]h = e)
и, наконец,
= e)
n) g^e, w^e,g = w
(g^Vw^e)
1g = w
((geeVwee)A]g = w)
3w((gsev wee)A]g = w)
и, наконец,
3g3w((geeVw®e)Alg = w)
- высказывания по правилу 1,
- высказывания по правилу 2 г,
- высказывание по правилу 2а,
- высказывание по правилу 26,
- высказывание по правилу 2е
-	высказывание по правилу 2ж,
- высказывания по правилу 1,
- высказывание по правилу 2в,
- высказывание по правилу 2а,
- высказывание по правилу 25,
- высказывание по правилу 2ж
-	высказывание по правилу 2ж.
ЗАДАНИЕ 2. а) а; б) f; в) d; г) f; д) а; е) а; ж) е (е - множество,
содержащее в точности один элемент); з) d; и) е; к) [; л) d; м) е; н) а; о) а;
п) а (только а не имеет собственных подмножеств); р) а (единственное
множество, которое не содержит в качестве элемента пустого подмно-
жества); с) е (имеет в точности одно собственное подмножество); т) f;
у) а; ф) d (множество d имеет в точности три различных элемента:
а, с и е).
74
ЗАДАНИЕ 3
Аксиома продолжения: V xV у(х=у** V z(z® х** 2е у)).
Аксиома пустого множества: 3 z(z «{ }).
Аксиома пары: V х V у Bzz = {x,y}.
Аксиома объединения: V хЗ yV z(z® у*» 3 w(z® wA	х)).
Аксиома степенного множества: V хЗ yV zfz® у** z& х).
Аксиома регулярности: V х(х ={ }V3zfzexAxflz={ }))•
ЗАДАНИЕ 4
1.1.	В силу аксиомы пары {А, В} - множество. По акси-
оме объединения U {А, В} = AU В - множество.
1.2.	АП В = {хе А | ф (х)}, где высказывание ф (х) - это хеВ. Поэто-
му по аксиоме содержательности АЛ В - множество.
1.3.	По аксиоме пары {А, А} = {А} - множество.
1.4.	По аксиоме регулярности найдется элемент хе {А}, такой, что
хП {А) = Ф. Элемент х должен быть А, поэтому АП {А} = Ф. В частнос-
ти, А£ А.
1.5.	По аксиоме регулярности найдется элемент хе{А,В), такой,
что хП {А, В) = Ф. Поскольку Ае В, то х не может быть множеством В,
отсюда х = А и АП {А, В}= Ф. Отсюда следует, что В£ А.
1.6.	Если два множества - пустые, то они имеют одинаковые
элементы и по аксиоме экстенсиональности эти множества оказываются
равными.
1.7.	Решение аналогично решению 1.6.
ЗАДАНИЕ 5. Продолжая обсуждение с того места, на котором мы
остановились в предыдущей главе, допустим, что {{а}, {а,Ь}} = {{с},
{с, d}}. Теперь либо {а} ={с), либо {a} = {c,d}. Если {а} = {с}, то а = с и
должно быть {а, Ь) = {с, d}, что приводит к равенству b = d. Допустим,
однако, что {а} = {c,d}. Тогда а = с = d. Затем {а,Ь} должно быть
{с, d] = {с, с} = {с}, и поэтому а = b = с.
Обнаруживаем, что во всех случаях а = с и b = d.
1.8.	Для аеА, Ь^В, {а} верно {a,b}eP(AUB), поэтому<а,Ь> =
= {{а}, {а, Ь }}S Р(АU В) или < a, b> G Р(Р(А U В)). Тогда АXВ = {хеР(Р(АU
ив}}|ф(х}}, где ф(х) - это ЗаЗЬ(х = <а,Ь>ЛаеАЛьеВ) (мы можем
ввести <а,Ь> в язык ££ как еще одно сокращение). Однако тогда по
аксиоме содержательности АХ в - множество.
1.9.	Если <а,Ь> = {{а}, {а,Ь }}е/,то {a,b}eUf (поскольку {а,b)e
e<a,b>ef) и beU(Uf) (поскольку be{a,b}e^f). Поэтому область
75
10
значений / = {xeU(U/)| q(x)}, где <?(x) - это 3y3z(z = <y,x>^zef) и
поэтому по аксиоме содержательности - множество.
1.10.	fW = {xef\3y3z(<y,z> = xAyeD)} - множество в силу
аксиомы содержательности.
1.11.	f1 - множество (в силу аксиомы содержательности). Это
функция, поскольку если пара < a, b>, <a, Oef-1, то пара <Ь,а>, <с,а>
ef, то b = с, так как / - однозначное соответствие. Аналогично 1 -
однозначное соответствие, поскольку/- функция.
ЗАДАНИЕ 6
1.12.	[a]R= {х<=А| <Х, а >е /?}.
1.13.	Если [a]R (![&]#¥= 0, то пусть х - элемент из пересечения.
Тогда aRx и bRx, поэтому по симметрии xRb, но тогда в силу транзи-
тивности aRb. Отсюда следует, что любой элемент у е [а] д также при-
надлежит и [ b]R. Действительно, из условия у*=[a]R следует, что aRy
и поэтому yRa. Теперь, используя то, что aRb и yRb, а потому и bRy,
получаем y«=[b]R. Доказательство в другую сторону проводится
таким же образом, поэтому [a]R = [ b]R.
1.14.	Каждый класс [a]R содержится в множестве Р(А), поэтому
набор всех классов эквивалентностей есть подмножество множества
Р(А). В действительности это {хеР(А)\ За Vy(y^x**aRy)}-
Глава 2
ЦЕЛЫЕ ЧИСЛА
ЗАДАНИЕ 7
2.1.	Истинное по 1.3 и аксиоме объединения.
2.2.	Если х Ф у, то А = (x\y)U(y\x) =# 0.
Пусть по аксиоме регулярности а «А будет таким элементом, что
а (1А - ф. Предположим, что а ех\у. Тогда a Ф 0, и поскольку 0 <=у, то
а = S(z) при некотором zex. А так как z^a, то гФА. Поскольку гФА и
zsx, то zey. Поскольку zey, то а = Sfzjey, что противоречит тому,
что а ех\у. Такое же противоречие вытекает из условия а еу\х.
! = {{)) 2-{( ).{{ )))
3“{{ }.{( )},({ ).{( })}),
«-{( }.{( })>{( }.{{ }}},{{ }.{{ )}.{( ){{ »)))•
76
2.3.	а), б) по определению множества N; в) так как x^S(x), то
S(x)± 0 = 0; г) ясно, что из x = y-^S(x) - S(y). С другой стороны, если
S(x) = S(y), то xU{x) = yU{y). Если х =# у, то в нарушение теоремы
1.5 хе у и уех; д) если А ф М,то по аксиоме регулярности найдется
элемент хе N\A, такой, что xflN\A =0. Поскольку х / 0, то х = S(k)
при некотором ке М.Таккакке хи А£М\А,то к«А. По предположе-
нию, x = S(k)^A, что противоречит тому, что Xе М\А.
2.4.	Пусть А = {хеГМ|<р(х)}. Так как 0«А и при любом к^А,
S(k)^A, таким образом, по теореме 2.3г А =М, поэтому высказывание
Ф (х) истинное относительно всех х е N.
ЗАДАНИЕ 8
2.6.	Пусть q(c) будет следующим высказыванием:У«УЬ(« +N (b +
+N с) =(<1 +n Ь)+м с). Чтобы показать истинность высказывания ф(с)
относительно всех с (ассоциативность), воспользуемся методом индук-
ции (теоремой 2.4). Прежде всего ф(0) - истинное высказывание,
поскольку a +N (b+N 0) =а +Nb =(а +N'b)+N 0. Теперь предположим,
что высказывание ф (к) истинное при некотором к. Тогда
« +n (b +n S(k)) = a +N S(b +N k)=
= S(a +m (b +m fc))=
= 5((a +n b) +n к) = (поскольку (f(k))
(« +n b) +n S(k),
отсюда q(S(k)).
И мы приходим к заключению, что <р(к)- истинное высказывание
при всех к.
2.7.	и +м 1 = и +м S(0) = S(n +N 0) = S(n).
2.8.	Пусть (f(n) будет следующим высказыванием: 0+N и = и.
Высказывание ф(0)- истинное, поскольку 0+к 0= О.Если справедли-
во высказывание <р(п), то 0+n S(n)fc= S(OH-N и) = S(n) и, значит, спра-
ведливо высказывание q(S(n)). По индукции высказывание <р(п)
истинно при всех neN.
ЗАДАНИЕ 9
2.9.	Используя индукцию по а, начнем с доказательства того, что
a+Nl =1+n °- Во-первых, по теореме 2.8 имеем 0+N 1= 1+n0. Предпо-
ложим, что а+|м1 =1+n «-Тогда
S(a) +N 1= S (S(a)) = (по теореме 2.7)
= S(a +n 1) =
= 5(1 +м «)=
= 1 +N S(a).
Значит, по индукции доказано, что а+n 1 = 1+ м а при всех а е N.
Теперь индукцией по основанию b докажем, что a+Nb = b+Na.
77
Во-первых, по теореме 2.8 имеет место a +n0 = 0 +n а.Теперь, если
a+n b= Ы-н а,то
а +n S(b) = а +м(Ь +n 1)—
= (а +n Ь) +n 1=
= (Ь +n о) +n 1=
= b + м (а + м 1)—
= b +N (1 +n а)=
= (b +n 1) +n
= S(b) +N а.
И мы заключаем, что a +n b= b апри всех а и b е N.
2.10.	2 +N 2 = 2 +N 5(1) = S(2 +N 1) = S(S(2)) = S(3) = 4.
ЗАДАНИЕ 10
2.12.	Используя индукцию по основанию р, докажем, что при всех
п, m и р е N справедливо равенство п	(m+N р) = (и m)+ N (и _'n рХ
Во-первых,и -N (m +N 0)== п -N m =(п -N m) +N 0 = (n -N m) +N (n 0).
Теперь предположим, что при всех п и me N выполняется равенство
и -N (т+|ч_р) -(и -JM т)Н-|ч(п-|м р).Тогда
и (w +n S(p)) — п -N S(m +n pX=
= (n -N (m +N p)) +N n =
= ((n -N m) +N (n -N p)) +n n -=
= (и -N m) +N ((и -и p) +n n)—
= (n ’м m) +m (n -N S(p)),
и теорема доказана по индукции.
2.13.	Индукцией по основанию с докажем, что(а -N b)-N с =а
a n (b -N 0> a -N 0= 0 = (a -N b) -N О.Если(а -Nb) -N с = a -N(b-Nc)TO
(а и b) -N S(c) = (a -N b) -N c +N (a -N b) -
= a *N (b ’N c) + N (a ’N b)~
= a-N ((b -мс)+мЬ)=
= a -N (b -N S(c)).
ЗАДАНИЕ 11
2.15.	Во-первых, 0 -N a= 0 по индукции:
0 N 0=0,иесли0 м а=0,то 0 N S(a) = 0 N a +N 0 = 0.
Теперь индукцией по основанию а докажем, что a -N b = b а:
0 N b = 0 = b м 0.
Предположим, что при всех b е М выполнено равенствоа -N b = b -N а.
Мы хотим показать, что S(a)-N b =b -N S(a). Докажем это индукцией по
основанию b:S(a)-N 0=0 = 0-N S(a), к если S(a)-N b=b -N S(a),то
S(a) -N S(b) = (S(a) -N b) +N S(a)=
— (b -N S(a)) +n (a +N 1) =
78
= (b ’м a) +n b +n a +n 1—
= (a ’n b) +m a +n b +n 1=
= (а ч S(b)) +N S(b)=
= (S(b)-Na)+NS(b)=
= S(b) -N S(a).
Этим доказано, что при всех be N выполняетсяS(a) -N b = b -N S(a)-
А это и доказывает, что a -N b= b-N апри всех a, b e N.
2.16.	(n +N m) -n p =p -N (n +N m) = (p -N n)+N (p -N m) =(n -N p) +
+N(m nP)-
2.17.	2 -N 2 = 2 -N S(l) = 2 -N 1 +N 2 = 2 +N 2 = 4.
ЗАДАНИЕ 12
2.18.	Пусть <p(y) будет следующим высказыванием: Vx(x<N у-►хе
еу). Используем индукцию по основанию у. Прежде всего заметим,
что x<N0 быть не может, поскольку х<^0 влечет, что для некоторого
ке N будет выполняться равенствох +N S(k)= 0, и потому S(x+N к) =
= 0, что невозможно. Отсюда следует, что <р(0) - истинное выска-
зывание.
Допустим, <р(у). Если x<N то x+N S(k)= S(y) для некоторого
к из N, и поэтому S(x+N k)=S(y)nx +^к = у.
Случай 7. к = 0. Тогда х=у и усу U {у} = S(y).
Случай 2. к =# 0. Тогда к = S(t) при некотором t, и потому x<N у и
хеу (поскольку у (у)), и вновь хеу U {у} = S(y).
Это дает q(S(y)), и поэтому по индукции доказано, что q(y) -
истинное высказывание при всех у.
2.19
1.	Отношение <N- антирефлексивное, поскольку если a <N а, то
ас а, что невозможно.
2.	Отношение <N- транзитивное, поскольку если a<N Ьи b<N с,то
a+^S(k) = b и b +N S(t) = с при некоторых значениях к, t е М, Поэтому
(a+NS(k)) +N S(t)= с, а значит, a (S(k) +N S(t))= с, следовательно,
а+ы S(S(k)+u t)=c, поэтому a <N с.
3.	Отношение <n удовлетворяет свойству трихотомии: пусть (f(b)
будет следующим утверждением: Уа(а = bVa<N bVb<^ а).Высказы-
вание ф(0) - истинное, поскольку если а =# 0, то 0 +n а = а и, по опреде-
лению, 0<n а.Теперь допустим, что q>(b)~ истинное высказывание.
Случай 1. а = Ь. Тогда a +n 1 = S(b), и поэтому a <N S(b).
Случай 2.а b. Поскольку при этом b +N 1 = S(b),b <n S(b), то
a<NS(b).
Случай 3. b<N a.Тогда b +N S(k) = a.
Случай За. к = 0. Тогда S(b) = a.
79
Случай 36. к ¥= 0. Тогда при некотором значении t е N выполняется
равенство к =S(t), поэтому S(b) +N S(t) = S(b +м S(t)) = b +n S(S(t))=a
и, значит, S(b) < n n.
Все эти случаи влекут q(S(b)). Поэтому по индукции высказывание
<р(Ь)~ истинное при всех b е N.
Глава3
ЦЕЛЫЕ ЧИСЛА
ЗАДАНИЕ 13
3.1.	<a,b>~<a,b>, поскольку в +м b = b а.Если <a,b>~<c,d>,
то а +м d= b +м с,поэтому с +м b= d а,и <с, d>~<o, b>. Для доказа-
тельства транзитивности нам потребуется следующая лемма.
2.20. Лемма.Если а	Ь=а + м с для а, Ьис^М,то Ь = с.
ДОКАЗАТЕЛЬСТВО. Доказательство проведем индукцией по
основанию а:из0+мЬ = 0+ мС следует b = с. Теперь предположим, что
всякий раз, когда а +м b = а + м с, всегда b = с. Тогда если задано S(a) +
+ м b = S(a) +м с, то S(a +N b)= S(a) +м с, поэтому a +Nb = а + N с и,
следовательно, b = с. Этим завершается доказательство леммы.
Теперь о транзитивности: если <a,b>~<c,d> n<c,d>~<e,f>, то
а d~b cHC4-^y = d+i^e.
Сложим правые и левые части равенств:
а +м d +N с +м f= b с +n d +N е и сократим:
Таким образом, <a,b>~<e,f>.
3.2.	По теореме 1.14 Z-множество.
Определение операции 4-2: определим [<а,Ь>]~+2 [<c,d>]~=
= [<а +м с, b + м d)]^. Нужно показать (см. ч. II книги), что это опреде-
ление не зависит от выбора значений а, Ь, с и d. Итак, предположим,
что <а,Ь>~<а',Ь'> и <c,d>~<c/,d>. Следует показать, что <a+N с, Ь+
+	(,а' +n C',b"+N d'y.. Принятые предположения позволяют
записать равенствам b' = b а’пс d' = d +N с', складывая
которые, получаем
я +м Ь’ с d' = b +м а' d с',
откуда следует, что
<я +м с,Ь dy ~ <а' +м c',b' +м d')>.
80
ЗАДАНИЕ 14
Определение. Пусть 0z = [ <0,0>]~ •
3.4.	[<о, Ь>] -~+ 2 0/ =	+ 0, b + ftj О>] ~	Ь>] ~ •
Определение. Для [<c,d>]~ е/положим -([<c,d>]~)z = [<d, с>]~.
Надо проверить, выполняется ли соотношение <d,c>~(d',c'), если
<c,d>~<c' d'>. Проверка не вызывает затруднений.
3.5.	[<с, d>]~+z	= [<с +м d,d +N с>]~. Это равно 0z, '
поскольку с + м d +м 0 = d +м с +N 0.
Определение. [<а, b>]~<2 [<c,d>]~ тогда, и только тогда, когда
а +м d <N b+N с.Чтобы показать корректность этого определения, нам
потребуется следующая лемма.
2.21	. Лемма. При любых a,bnce Nнеравенство а< м bвыполняется
тогда-и только тогда, когда a с <N b +N с.
ДОКАЗАТЕЛЬСТВО
a b
тогда и только тогда, когда а + N S(k) = b при некотором keN, что
выполняется тогда и только тогда, когда а +ы с +w S(k) =b +w с при
некотором k е N, что выполняется тогда и только тогда, когда а +м с<
<м b +м с.Теперь предположим, что <а, b>~<af, b'> n <с, d>~<c',
d'>. Тогда а + N Ъ'=Ь +м а'и с +ы d' = d + N с'. Таким образом,
a +N d<N b +N с тогда и только тогда, когда
а +м d + м а’ + м Ь' +м с' +м d‘ <м ,
что выполняется тогда и только тогда, когда
(а +м Ь') +n (d +м с') +м а' +м d'<K ,
<N (HnH+^c+n^+^'+nc; что выполняется тогда.,
и только тогда, когда
а' + м d' <\ b' +м с'.
3.6.	Антирефлексивность: если[<а, b>]~<z [<а, Ь>]~, то a b <Nb+
а, что невозможно.
Транзитивность: если [<а, b>]~<z [<с, d>]~ и [<с, d>]~< z [<е,
то а d	ис f Cftj d в,
таким образом, a +N d с +N f <N b +N c +N c +N f < b +N c+
d +\ eja + \ f	b +n e,
и потому [<a, b>]i<i [<e, />]-.
Трихотомия: при заданных значениях е = [<а, Ь>]~ и / = [<с, d>]~
либо а + м d =b +N с(тогда е =f), либо а d <N b +N с(тогда e<N /),
либо b +м c<N а +м ^(тогда/<2 е).
ЗАДАНИЕ 15
Определение. [<а, Ь>]~ 2	= [<(« ‘м с) +м (b d),
(b с) +м (а ’м
11-3504
81
Чтобы показать корректность данного определения, предположим,
что <а. Ъ>~<а'. Ъ'> и ‘'с, d>~<cf, d'>. Тогда имеем:
(1)	a	b' = a' -4-fsj Ьи
(2)	с	d' = с' d. Это дает
(3)	(а -м с) +м (Ь' -м с) = (и' -N с) +N (b -N с)и
(4)	(Ь' ’м с) + м (Ь' • м d') = (b' ’м с')	(b' d) плюс
(5)	(а d) + м (Ь' ’м d) = (а’ d) +м (Ь d) и
(6)	(а' -м с) +м (а' и d') = (а'	с') +N (a' -N d).
Поменяем местами правую и левую части равенств 4) и 5) и сложив
все равенства, получим
(а \ с) (Ъ’ ’м с) (Ь' ‘м с') +n (b d) +N (а’ ’м d) +м (Ь ч, d) +
+ n (а ‘n с) 4 n (а ’м d ) = (а' \с) + N (b с) +м (b' ‘N с) +
+ м (b' \ d'y + N(a \ d) (b' d) +N (a' ’m c')	(a' \ d).
После сокращений получим
(a ’N c) +n (b ’n d) +n (b' c') 4-^ (а' \	= (a' c')	(b' d') +
+n (b ‘m cj +n (a ’n d),
таким образом,
<(a ‘м c) +m (b d),(b ‘m c) (a -m dy>~ <(a'	c')	(b'	d'),
(bz ‘n c ) +n (a> ’n
3.7.	Доказывается стандартным образом.
Определение. lz =[<1,0>]~.
3.8.	Доказывается стандартным образом.
Глава 4
РАЦИОНАЛЬНЫЕ ЧИСЛА
ЗАДАНИЕ 16
Определение. Определим отношение « на множестве Z х (Z\{0z})
условием
<a,b>«<c, d> тогда и только тогда, когда а d = b г с.
Это - отношение эквивалентности; очевидно, что оно рефлексивное и
симметричное. Для проверки транзитивности предположим, что
<a,b>^<c,d> и <c,d>«><e,f>, так что а г d = b -г с и с -г f = d -г е..
Домножив первое равенство на /, а второе на Ь, получим а-г d -г f =>
‘Ь-гСг/лЬ гсг f= b -2d-ze и, значит, а -г d -г f = b -г d г е. Для
завершения доказательства нам бы хотелось обе части равенства
сократить на d. Однако для этого вначале потребуется следующая
лемма.
82
2.22. Лемма. ( Сокращение при операции -N). Пусть к, гл, neN;
тогда при S(k)-N m =S(k) -N n выполняется равенство m = n.
ДОКАЗАТЕЛЬСТВО. Если лемма не верна, то либот <N п, либо
п <n пг. Допустим, чтоп <N m,тогда и 4-^ 5(1) = m при некотором teN.
Тогда S(k) -N п. = S(fc) \ п +-N S(k) откуда О = S(k) S(t),,
откуда0 = S(k)-N t 5(k),откуда 0 = S(S(k)-N t к), что невозмож-
но. Теперь нужна еще лемма.
3.9.	Лемма, (сокращение при операции -z). Пусть р, q, г el. Если
Pzq^ri q, тор = г.
ДОКАЗАТЕЛЬСТВО. Пусть р = [<i,j>] q = [<k,s>], г = [ <t, u>]
Поскольку q =£ 0z,to должно быть к ± s (в противном случае [<k,s>]~=
= [<0,0>]_). Теперь равенствор -г q = г г q означает, что
<(i -N к) +м (J -м s),(i -м s) +N (J -N k)> ~ <(t -N к) (u s),(t s) +
+m (« 4 &)>> откуда (j k) +N (J -N s) +n (t 4 s) +N (u -N k)=(i -N s) +
+ m (J ‘n ty +n (t 'n k) 4-ftj (u ’n s)_или[(1 -f-N и) к]+м [_(j +m t) \ s]“
=[(i +N u) -N s]+N [(J +N t) ^к.].Посколькук * s, то либо k<N s, либо
s <м к.Пусть для определенности k <n s(другой вариант ведет к почти
тождественным выкладкам). Тогда s =к +NS(v) при некотором элемен-
те V. Проведя соответствующие подстановки и сокращения, получим
(j +n t) ’n S(v) = (i +m u) -n S(v). По лемме 2.22 имеем j t= i +N u,
значит, p = [<i, j>]~ = [<t, u>]~ = г. Таким образом лемма 3.9 доказана
и завершено доказательство транзитивности.
Определение.Q = {xeZ х Z|x= [<«, Ь>]« при некотором b Oz}-
По теореме 1.13 - это определение множества.
ЗАДАНИЕ 17 г . г/ ,чп
Определение. [<а, b>J% + q[<с,«>]» = [<(«’гa)+z(b’zc)>
ь-Мх.
Надо показать:
а)	если Ь и Oz,rob г d 0z,H
б)	операция 4-о определена корректно.
а)	Если b-z</=0z,to b-zd = 0zz ^поэтому либо<( = Ог,либо в силу
леммы 3.9 Ь = 02.
б)	Пусть <а, Ь>~<а', Ь'> и <с, d>^<c', d'>. Надо показать, что
\(п ’z d) +z (b -г c),b -z яа <(a' ’z d') +z (b' -z c'), b’ -г d'y, t. e
(a -z d b' -г d') +z (b -z с -г b' -z J')= («' ’z d' -zb -zd) +z (b' -z c’,
•z b -z d). Из данного предположения вытекаетa-zb’= a’ bnc -zd'=
= c' -z d, отсюдаа -z b’ d-zd’ = a' -z b -zd -г d’ и b -z b' -z c -z d' =
~ b *z b *z c *z d.
Сложение этих двух равенств завершает доказательство.
4.1.	Доказательство очевидно.
Определение. 0Q = [<0z, lz)]~.
Определение. ~([<р, уЖЬ = [<”(?)/, 4Ж •
11
83
Это определение корректное, ибо если <р, q>я><р', q'>, то
р '1 Q ’ = Р' z и тогда
~(р')г 'г 4 +z (P)z 'г $ +z (? г (Р 'г +z (p')z ‘z Q +z (p)z 'г q\
откуда~(р')7 z <2+z (-(p)z +z?)’z a' =("(p')z +z P')’z q +z ~(р)г'г a',
откуда (pjz z q +z0z=0z +z (p)z ’z 4,откуда-(р')г z? = (p)z z q’,
и, следовательно, <-(p')z,4'> ® <~(p)z,4>-
4.2.	Проверяется непосредственно.
ЗАДАНИЕ 18
Определение.[<a, b>]« -Q [<c,d>]~ = [<a -z c,b -zd>]~.
Корректность определения проверяется непосредственно.
4.3.	Доказательство кропотливое, но нетрудное.
Определение. 1Q= [<lz, lz>](1/[<а,Ь>]«)ц=[<Ь, a>]«.
Надо показать, что:
а)	если [<a, b>]«^ 0Q, то a ¥=0z, и
б)	определение дано корректно.
а)	Если а = 0z, то <а, Ь>я> <0z, lz> , поэтому [<a, Ь>]и = 0Q.
б)	Доказывается стандартным способом (если <а, Ь>™<а', Ь'>, то
а -г Ь' = а' -г Ь,поэтому <b, a>’»<b', а'>).
4.4.	Проверяется непосредственно.
Приведем ответ на вопрос, поставленный в предыдущей части
книги. Множество {[<s, lz>]~ eQ|seZ} есть подмножество множест-
ва Q, которое ведет себя в точности так же, как множество Z.
ЗАДАНИЕ 19
Прежде чем привести доказательство, придется рассмотреть
несколько лемм о целых числах.
Определение. Элемент х е Z - pos-элемент (положительный) тогда,
и только тогда, когда 0z <z х. Элемент х - neg-элемент (отрицатель-
ный) тогда, и только тогда, когда х <z 0z.
3.10	. Лемма. Сумма двух pos-чисел есть pos-число.
3.11	. Лемма. Сумма двух neg-чисел есть neg-число.
3.12	. Лемма. Элемент х - pos-число тогда, и только тогда, когда
элемент~(х)гестъ neg-число.
3.13	. Лемиа-Произведение двух pos-чисел есть pos-число.
3.14	. Лемма. Произведение двух neg-чисел есть pos-число.
3.15.	Лемма. Произведение pos- и neg-чисел есть neg-число.
4.6.	Лемма. Сумма двух положительных целых чисел - положи-
тельное целое число.
4.7.	Лемма. Сумма двух отрицательных целых чисел - отрицатель-
ное целое число.
ДОКАЗАТЕЛЬСТВО. Пусть х = [<a,b>]~,y = [<с,d>]~, 0z =
= [<о,о>]~.
84
3.10. Неравенства Ог <z х, Uz <z у означают, что а<^Ь и c<Nd.
По лемме 2.21 (см. ответ к заданию 14) рправедливо неравенство а +
с <n b +м а, поэтому Uz <z х +2 у.
3.11. Доказательство аналогично предыдущему.
3.12.0z <z х тогда и только тогда, когда а<м Столько и только
тогда, когда “(x)z — [<b,a>]~ <z О/-
3.13. Если Ь<м яи d<N с,то а = Ь +м S(k) и с = d + 5(0 (при неко-
торых значениях к и t е М- Тогда (a -N с) (b d) =(b-N d)-|-
+ м (Ь ‘м 5(0	+ м (S(k) ’м d) +м 4-^ (S(k) ‘м 5(0))	+14 (b м d)
= Г(Ь +N S(k)) ч d] +N [b -N (d +N 5(0)] +N CS(fc) S(01= (« -N *)+
+ n (^ n c)+m 5(k) S(t) = (a’m <()+m (b \ c)+n 5(5(к)’м t+м к),
таким образом,
(а ’м d) (Ь •- с) <м (а \ с) +м (Ь \ d),
поэтому
О/	‘n с) +n (b ‘м d),(a ‘м d) +N (b \ c))>]~ = x ’Z y.
3.14	и 3.15. Доказательство проводится аналогично.
4.6.	Предположим, что [<а, Ь>]и и [<с, d>L положительные.
Убедиться в том, что сумма [<(я -z d) +z (b г c),b -г </>]« - положи-
тельное число, можно, проверив четыре неравенства:
a)	0z <z а, b, с, d ;
б)	a, b <z 0z <z c,d;
в)	с, d <^2. 0z <z я, b t
г)	a, b, c, d <z 0z.
С помощью приведенных выше лемм проверку провести нетрудно.
4.7.	Доказательство аналогично предыдущему.
Теперь докажем, что определение положительного числа (в мно-
жестве О>)дано корректно. Допустим, что <а, Ь>^<а', Ъ'>, т. е. а -г Ь'=
= b -z а'. Тогда если 0z <z а -2_b, то, рассмотрев различные случаи,
можно показать, что 0z <г а' -г Ь'.
Случай 1.0z <z а, b. Тогда, поскольку Ь' Ф 0z, либо а -г b' <z 0z,
откудаЬ' <z 02ия' -z b <z 02,поэтомуа' <z 02и02 <z а' -г Ь'.либо
6)0z <z а -г b', откуда 0z <z b' и02 <z а' -г Ь,поэтому02 <z а' и
0z <z а' -г b'.
Случай 2.a, b <z 0z> рассматривается аналогично случаю 1. Следо-
вательно, 0z <2 а -г Ьтогда итолько тогда, когда0z <2 а' -2Ь'.Так же
показывается, что определение отрицательного числа дано корректно.
4.5.	Антирефлексивность: если к <Q к, то к +q (к)0 = 0а . есть
положительное число, но Oq = [<0z, lz>] ~ - не положительное число.
Транзитивность: если i <Q j и j <Q к, то j +Q -(0ои к +Q -(j)o -
85
положительные числа. По лемме 4.6 сумма - тоже положительное
число, поэтому i <Qk.
Трихотомия: пусть i,j е О^при этом возникают три случая.
Случай 1. Число j +Q “(/^-положительное. Тогда i <Q j.
Случай 2. j +Q “(i)Q = 0о.Тогдаj+q (/)q +q i = i, поэтому; = i.
Случай 3. Число j +q“(/)q- неположительное и не Oq, поэтому оно
отрицательное. Тогда число / 4-о “(;)Q должно быть положительным,
поскольку если бы оно оказалось iQq или было бы отрицательным
числом, то в силу леммы 4.7 число[ j +Q“(i)Q] +Q [i +g “(j)Q] было
бы отрицательным, но оно есть 0Q. Таким образом, j <Q /.
Глава 5
ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА
ЗАДАНИЕ 20
5.1.	I?- определяемое подмножество множества P(Q), и в силу
аксиомы содержательности есть множество.
Определение. Пусть г, se R, при этом r<R х тогда, и только тогда,
когда гс j.
5.2.	Антирефлексивность: утверждение r<R г очевидно ложное.
Транзитивность: неравенства г <R хи х <R t означают, что г с х и
Xе t, поэтому гс tи г <R t.
Трихотомия: допустим, г ¥= х. Тогда существует элемент, принадле-
жащий одному из этих множеств, но не принадлежащий другому.
Пусть для определенности №г\х. Тогда для всех уе х выполняется
неравенство у <Q х (если это не так, то по условию 1 определения
сечения было бы хе х), но поскольку у <Q х,тоуе г и отсюда х^ г. А
так как х ¥= г, то мы имеем s<J г и поэтому х <R г.
5.3.	Пусть х - верхняя грань множества X ч г = U X, где г - сечение,
поскольку:
1)	если qG г ир <Q q, то для некоторого сечения t имеем qe teX,
поэтому ре t и ре г;
2)	qer влечет q&t^X, и поскольку t не содержит наибольшего
элемента и г, то элемент q не может быть наибольшим элементом г;
3)	поскольку множество X * 0, то существует элемент X.
Поскольку t + 0 и t- г, то г + 0;
4)	поскольку х ф Q, то существует элемент ре q\ $. Этот элемент
не принадлежит сечению г, поскольку из ре г следует, что p^teX и
t <r s,поэтому t^s, но рФ s.
86
Далее г - верхняя грань множества X, поскольку из того факта,
что X, следует, что г, и поэтому t <R /-.Наконец, допустим, что
и - еще одна из верхних граней множества X. Тогда для каждого
элемента teX будет справедливым выражение и, а отсюда г = UX^ и
и поэтому г5? R и.
ЗАДАНИЕ 21
5.4.	Чтобы доказать, что г + Rs - сечение, предстоит проверить
выполнение четырех свойств.
1. Если a <Q Ъ n ber +R s, тоЬ = х +Q у ,гдехе г и уе s. Пусть
z = y +q a +Q ~(Ь)0.Мы получили а = х +q'zh хе г; для завершения
доказательства остается только показать, что zG s. Тут поможет сле-
дующая лемма.
4.8. Лемма. Если х, у е Q, то
а) (х +q у)ц = (x)q +q (у)ц, и
6)T(x)Q)Q = x.
ДОКАЗАТЕЛЬСТВО
"(х +Q y)Q, ="(х+q у)о,+q,(х +q у +9"(х)9 +a-(y)Q)*= (“~(х +9 у)д +
+ q X у) +q (x)q +q (y)o= (x)q +q (y)^.
( (x)q)q = ( (x)q)q +q ( (x)q +q x)i= ( (x)q)q +<j (x)q) + q x= x.
Итак,г <q у, поскольку у +q^(z)q = у +Q~(y)Q +Q"(a)Q Ч-а^ивсилу
леммы 4.8)= b +q (a)<j,- положительное число, так как а <Q ь. По-
скольку ye s> то z® s.
2. Предположим, что a® r+R s,a = x+Q у, xGr, yes. Поскольку в
сечениях г и s нет наибольших элементов, то существуют элементы
х/е г и yze s, такие, что х <0 х'и у <9 у'. Тогда a<Q х' ч-q у' и х' +
+Qy'er+Rs. Доказательство последнего утверждения требует еще
одной леммы.
4.9. Лемма. Если w, х, y,ze Q и w<Q х,у <Q z,ww ч-q у <q х ч-q z.
ДОКАЗАТЕЛЬСТВО. Числа х + Q ~(w)qhz ч-q ~(y)<j- положитель-
ные, поэтому, как следует из леммы 4.6 (см. задание 19), их сумма - то-
же положительное число.
ЗАДАНИЕ 22
5.5. Свойство коммутативности очевидно выполнено. Доказа-
тельство ассоциативности тоже становится простым, если мы заметим,
что r + R(s +я t) = (r+R s) + R t= {x|x = a +Q b + Q c, aer,bes,cet},из-за
ассоциативности операции+9.
Определение. Пусть 0R = {x|xeQ> л х <Q 0Q}.
Очевидно, число 0R обладает свойствами 1, 3, 4. Для проверки
свойства 2 предположим, что q е 0R. Рассмотрим р =q -Q (1/(1Q +Q 1q)q.
Кроме того, q <q 0отогда, и только тогда, когда 0Q +q ~(q)o ~ поло-
жительное число. Число ~(р)ц тоже положительное, поскольку q +
87
+q “(p)u +q ~(p)q °> и поэтому в силу 4.7 “(p)Q не может быть отрица-
тельным числом или нулем. Таким образом, p<Q oQ и pG 0Q. Наконец,
q<Qp, поскольку р + q ~(q)a ~ положительное число (оно не может
быть ни отрицательным, ни нулем, так как р +Q -(q)q +q р +q (q)o =
= p + p +~(q)a +q (<?)q = ~(q)a - положительное число).
5.6. Если xe r +rOr, то x = a + z b, ae r, beOR, поэтому x = a +
fQ b <q0 и xe г. Таким образом, г +r 0r ^r г.Может ли г быть больше,
чем г + r 0R? Только в том случае, если существует элемент yG г\(г +
+r OrJ:
r+,OB	у г
А так как в г нет наибольшего элемента, то найдется элемент г,
такой, что y<q z-Однако тогда у = z +Q (у +q(z)q),zе r,(y +q~(z)q) е0Q
и поэтому у е г + R Or, чтб противоречит сделанным предположениям.
ЗАДАНИЕ 23
Примечание. Допустимы и ответы, отличающиеся от приводимых
ниже!
Определение. Пусть reR, тогда “(r)R = {х е Q> | “(х)0 е Q>\ г и для
некоторого у G Q\г, у<Q -(x)Q}.
Определение. Пусть г, seR, 0R <Q г, s.Ho определению, г -R s =
= {xeQ|x =й -Q b для некоторых ое ги bes, таких, что 0Q <Q а и
0о <Q Ь}. Также по определению 0R R г = 0R,r R Or = 0R, r -H ~(s)R =
“ ~(r R Or,"(Hr R S R Or и ~(r)R R ~(s)R = r R s.
Определение. 1R = {x|x <Q 1Q}.
Определение. Для reR„0R <Rr положим (l/r)R={xeQ|3y(y/rA
a x <a(l/y)Q)}. Для г <R Ояположим (l/r)R = -((1/-(f)r)r)r.
Примечание. Если бы мы продолжили изучение темы, то было бы
необходимо доказать, что все эти величины - сечения А в случае
операции r для доказательства полноты приведенного определения
потребовалось бы также доказать, что t <rOr тогда, и только тогда,
когдаОи<и -(t)R. Множество {{peQ|p <q q}eR|(jeQ} - подмно-
жество множестваR, которое ведет себя подобно множеству 0.
Глава 6
ОРДИНАЛЫ
ЗАДАНИЕ24
6.1.	Очевидно истинное.
6.2.	Доказательство леммы 6.2а: при заданном множестве А найдет-
ся элемент Ь^А, такой, что ЬПД = 0. Этот элемент будет е-наимень-
88
ший в множестве А, т. е. если с - какой-нибудь другой элемент А,
то с&Ь.
Далее, для a, ЬеМс помощью теоремы 2.18 и свойства трихотомии
для отношения < легко показать, что а < м b тогда и только тогда,
когда aGb. Тем самым доказываются свойства! и 2' леммы 6.25. Нако-
нец, если aGbG , то a<Nb, поэтому aGN.
Между прочим, {{&}} очевидно удовлетворяет свойству 1', но не
удовлетворяет свойству 3'. С другой стороны, {0,{0},{{0}}} удовле-
творяет свойству 3', но не удовлетворяет свойству 1'.
6.3.	Приступая к доказательству транзитивности, предположим,
что a,b,c&S(a) = aU{a) и a&b&c. Тогда: либо а) все три элемента
принадлежат «, при этом а^с, поскольку a - ординал, удовлетворя-
ющий свойству 1'; либо б) а,Ьеа, с = а и отсюда а*=Ь согласно свойст-
ву 3'.
Доказывая свойство трихотомии, предположим, что а, S(a) =
= a U {а}. Если a, b е а, то мы воспользуемся трихотомией отношения е
на множестве а. Если а® а, b = а, то очевидно, что ае Ь. Наконец, если
оба элемента а и b равны a, то а = Ь.
Доказывая свойство 3', предполагаем, что a^b^S(a) = aU{a).
Тогда: либо а) Ьеа и, значит, a^a и поэтому a е S(a), либо б) b = а и,
значит, а&а и сноваa^S(a).
6.4.	Во-первых, be а, поскольку а&Ь-*а^а согласно свойству 3'
для х. Поскольку отношение е есть отношение полного упорядочения
на множестве «, то это также отношение полного упорядочения на
каждом подмножестве и, в частности, на множестве Ь. Во-вторых,
пусть се de be а. Тогда се de а и се а согласно свойству 3' для а.
Тогда, поскольку c,d,bea, согласно свойству транзитивности отноше-
ния е на а получим ceb.
ЗАДАНИЕ 25
6.5.	Если аер,тоуе«ер-»уер и, таким образом, a £ р; посколь-
ку к тому же a #= р, то а с р.
Если a <= р, то пусть у будет наименьшим элементом в множестве
Р \ «. Мы утверждаем, что a = у и, таким образом, а ер. Предположим,
что б е у. Тогда б*Р\аивтоже время б е у е р; следовательно, б е р.
Это означает, что б е а и мы получили у £ а. Чтобы показать, что a £ у,
и тем самым завершить доказательство, предположим, что б е «. Тогда
б е р и по свойству трихотомии либо:
1)	у е б (откуда yea- ложное высказывание!),
2)	у = б (откуда вновь уеа, что невозможно!),
либо
3)беу.
Возможен только последний случай и, таким образом, доказатель-
ство завершено.
6.6.	Необходимо показать только, что выполняется свойство
89
12-3504
транзитивности. Пусть аир- ординалы. Если а ¥= р, то одно из двух
множеств а \ р или Р \ а - непустое. Пусть р \ а ¥= 0. Пусть у - наимень-
ший элемент в множестве р\а. Как и при доказательстве теоремы 6.5,
покажем, что у^а. А так как у Фа, то (по теореме 6.5) невозможно
включение у <= а и поэтому у = а. Таким образом, a g р.
6.7.	Пусть А ¥= ф есть множество ординалов. Пусть аед. Если
а П 4 = 0, то а - наименьший элемент в множестве 4. С другой сторо-
ны, поскольку аП4£а, то множество а (14 содержит наименьший
элемент р; он же есть наименьший элемент и в множестве 4 (посколь-
ку для у®4 либо аеу, и тогда Р6У, либо а = у, и тогда РеУ, либо
у е«, и тогда у еа (14 и р =у илиР^у).
6.8.	Свойства 1' и 2' леммы 6.2а вытекают из утверждения 6.7.
Докажем свойство 3': если аереиА, тоРеУ при некотором значении
у е4, а следовательно, a g у, и поэтому а g и 4.
Если а®4} то а£114 (так как а = U4 или аеи4), поэтому U4 есть
верхняя грань множества 4. Если у - какой-нибудь другой ординал,
такой, что aG4-»asy, то U4£y (поскольку U4 = у или и4еу), а
отсюда U 4 - наименьшая верхняя грань.
6.9.	a g s(a).
6.10.	Если бы совокупность всех ординалов была множеством, то
множество U 4 было бы наибольшим ординалом, что в силу теоремы 6.9
невозможно.
ЗАДАНИЕ26
6.11.	Ординал ы не нуль и о + S(n) для любого nsw, поэтому этот
ординал - предельный. По определению, если a go5 то либо a = 0, либо
a = S(n) при некотором new. Поэтому a - не предельный ординал, и
отсюда w - наименьший такой ординал.
6.12.	Допустим, что при заданном высказывании найдется такой
элемент у, что высказывание Ф(у) будет ложным. Должен существо-
вать наименьший ординал такого типа, поскольку множество
Х = {аеу|ф(а) - ложное высказывание}
либо пустое (и тогда у наименьший элемент), либо непустое (тогда по
теореме 6.7 в нем содержится наименьший элемент). Пусть Р - наи-
меньший элемент. Однако это противоречит сделанным предположе-
ниям, поскольку при всех аер высказывание Ф(а) - истинное.
ЗАДАНИЕ 27. Операция +0 - не коммутативная, 1 +0 о = ы
1	со	со
но о +01 =S(a):
□ □	+ □ = □ О □	•
со	1	S(co)
90
Операция +0 - ассоциативная. Элемент 0 - единица операции.
Выполняется закон сокращения слева, т. е. из равенства а +ор =
= а +оу следует р = у, однако правое сокращение не выполняется,
например 1 +оы = о = 2 +оы, но 1 ¥= 2.
Операция -0 - не коммутативная, 2-0 о = о:
( )( )( □ ) ••• =□□□•••,
(<»)	J	<0
но о • 02 = ы +0 ы:
( □ •••)( □ •••) =□□•••□□ •••
(2)	_	со +о со
Операция -0 - ассоциативная. Элемент 1 - единица операции. Выпол-
няется закон сокращения слева, однако правое сокращение неправо-
мочно, поскольку 1-оы=2-оы,а1 / 2.
Выполняется один из дистрибутивных законов, а -0 (р +оу) = а -0 Р +
+оа-у, но второй не выполняется, (ы +01)-02 = о +ow +01:
<»+о1	со+01
(□□•••□)(□□•••□)
(2)
ш + о ш +<, 1
ho(q-02)+0(1-o2) = w+o“+o2:
(□□•••)(□□•••) □ □
(2)	J L <2)
<о +в <а +о 2
Глава?
КАРДИНАЛЬНЫЕ ЧИСЛА
ЗАДАНИЕ 28
7.1.	Для доказательства неравенства IIto IIIIS(to)И укажем, что
тождественное отображение /, задаваемое условием / (х) = х,
однозначно отображает ординал о в 5fo). Для доказательства в
другую сторону II S(gj)II II (о II определим /условиями /(ы) = 0 и f(n) =
= п +n 1 при всех п«ы.
7.2.	Для доказательства неравенства llolKIIZH воспользуемся
тождественным отображением, для доказательства в другую сторону
112. II =£ Ио) II определим /условиями f(n) = 2п, если 0<п, и f(-n) = 2п-1,
если - п<0.
7.3.	Для доказательства неравенства II о II < IIQH рассмотрим отобра-
жение /, отображающее п в дробь п/1. Для обратного неравенства,
IIZII II о II, составим специальный список. Сначала выпишем все дроби,
которые можно записать, используя {- 1, 0,1}:
1/1, 0/1,-1/1,
затем те дроби, которые получаются, если добавить {- 2, 2}:
1/2, 2/1,-1/2,-2/1,
и затем все дроби, добавив {- 3,3}:
1/3, 2/3, 3/1, 3/2, -1/3, - 2/3, - 3/1, - 3/2,
и т.д. Этот громадный список будет содержать все рациональные
числа, и его длина будет равна в точности о. Тем самым определена
функция:
О- 1/1,
1	- 0/1,
2-	-1/1,
3-	1/2,
4-2/1,
ЗАДАНИЕ 29
7.4.	Следуя плану, указанному § 7, ч.П, докажем следующее:
1.	Хе Y^f(X)sf(Y)^B\f(Y)SB\f(X)^g(B\f(Y))5g(B\f(X)Н А\
g(B\f(X))<=A\g(B\f(Y)).
2.	aGZ-aeX-H/Xj при некотором множествеX. Последнее
должно полностью содержаться в множестве Z, поэтому а^Х^Н(Х)^
^H(Z) и, таким образом, Z^H(Z).
3.	По определению, b&X^H(X)^H(Z) при некотором Хед. Тогда
b*A\g(B\f(Z)).
Однако тогда a$B\f(Z) - противоречие.
4.	Поскольку b*H/ZU{b}), b^H(Z), то b<£A\g(B\f(Z)), beg(B\
f(Z)) и b = g(a) при некотором a &B\f(Z).
92
5.	Это следует из п.З и п.4 и того факта, что отображения / и g
взаимно однозначные.
7.5.	Истинное по теоремам 7.4,7.2 и 7.3.
ЗАДАНИЕ 30.
7.6.	Согласно указаниям из ч.п С^А, откуда С^Р(А), поэтому С =
=f (х) при некотором х из множества А, поскольку f - это отображение
”на”. Далее мы видим, что x^f(x) тогда и только тогда, когда х&С, и
тогда и только тогда, когда хФ[(х). Это - противоречие, и поэтому
наше предположение о том, что II PfAJ Ж Н А Н, ложно.
7.7
ДОКАЗАТЕЛЬСТВО 1, приведенное в ч.ш, почти полное. Добавим
только, что построенное число г не содержится в списке. Это число не
может быть первым в списке, поскольку отличается от него первой
цифрой в правом десятичном разряде. Оно не может быть и вторым
числом в списке, поскольку отличается от него вторым десятичным
разрядом, и т.д.
Поэтому это не отображение ”на” - противоречие.
ДОКАЗАТЕЛЬСТВО 2 также использует десятичное представление.
При отображении множество, например, К = {1, 3, 4, 7, 9, 10....}, пред-
ставляется в виде десятичной дроби
0123456789
f(K) = .0101 100101 1 ....
1	3 4	7 9
Понятно, что если Kt*K2, то	поскольку их десятичное
представление будет различным.
Заметим, что если ПА II < IIВЖ ПСИ при отображении /, отображаю-
щем А в В, и взаимно однозначном отображении g из множества В в
множество С, то НА II’S И СП, поскольку композиция отображений g of
есть взаимно однозначное отображение. С другой стороны, НА II < И СИ,
ибо если отображение h из множества С в множество А взаимно одно-
значное, то h отбудет взаимно однозначно отображать множество В в
множество А, что противоречит неравенству НАЖИВИ.
ДОКАЗАТЕЛЬСТВО 3 проведено полностью.
7.8.	Пусть а = UА. Если ₽еа и II₽ II = IIа II, то существует
однозначное отображение /из я на 8. Поскольку реуеА при некото-
ром уеА, то /17 и есть однозначная функция из у в ₽,что
противоречит тому факту, что у — кардинальное число.
93
7.9.	В указаниях к задаче 7.5 было показано, что II о II = BS((o) II,
поэтому S(o) - не кардинальное число.
ЗАДАНИЕ 31
7.13.	Докажем теорему индукцией по основанию п. Множество 0 -
конечное по Дедекинду множество, поскольку не имеет собственных
подмножеств. Допустим, что п - конечное по Дедекинду множество, и
предположим, что функция f отображает п + N1 в собственное подмно-
жество п + м 1. Пусть отображение h будет таким, как предложено в
указаниях. Ясно, что отображение h - однозначное и что
множество значений есть подмножество в п. Более того, область
значений будет и собственным подмножеством, поскольку имеется
некоторое число к &п, не принадлежащее к области значений /. Если
к <п, то к не может принадлежать области значений h, и если к = п, то
f(k)<n и не в области значений h.
7.14.	Пусть /-однозначное отображение на множество Хи
N .Предположим, что g отображает множество X на собственное
подмножество X. Тогда функция h, определенная условием
Ъ(к)=Г'Шк))),
взаимно однозначно отображает п на собственное подмножество в п
(если у не принадлежит области значений g, то /~ г(у) не принадлежит
области значений h). Но это противоречит утверждению теоремы 7.13.
7.15.	Воспользуйтесь утверждением теоремы 7.10 для полного
упорядочения множества X. Как следует из теоремы 6.13, существуют
ординал а и функция /, однозначно отображающая а на
множество X Ординал а не может быть меньше чем о, поскольку
множество X - бесконечное. Однако тогда и /I (о - требуемая
функция.
7.16.	Пусть / будет функцией, построенной при доказательстве
теоремы 7.15. Определим отображение g из X в X условием
g(x)-f(S(f~1(x))).
Тогда g - однозначное отображение на себя. Значение / (0) не
принадлежит области значений / поэтому множество X - бесконечное
по Дедекинду множество.
ЗАДАНИЕ 32
7.17.	Приведем доказательство, отличающееся от намеченного в
главе указаний. Пусть множество X - счетное и при каждом а^Х
множество Ха тоже счетное. Пусть Y - объединение всех множеств Ха,
94
у = {у\у^Ха при некотором аеХ}. Надо показать, что множество У -
счетное. Пусть / - однозначное отображение X в о. Для
каждого элемента а еХ пусть /а - отображение Х„ в ы. Следует опреде-
лить однозначное отображение h из У в (6.
Первая попытка. Пусть h(y) = (рп)Ыу>, где уеХа, f(a) = п и р„ -
- п = е простое число. Первая попытка оказывается неудачной, пос-
кольку у может одновременно принадлежать двум различным мно-
жествам Ха и Хь. Тогда отображение h(y) не будет корректно опреде-
ленным.
Вторая попытка. Пусть h(y) = (рп)Ыу), где п - наименьшее нату-
ральное число, такое, что при некотором аеХуеХа и f(а) = п. Вторая
попытка приводит к успеху.
Аксиома выбора использовалась здесь при выборе отображений fa.
Для каждого значения а существует бесконечно много отображений Ха
в (о, но для доказательства требуется одно конкретное отображение. В
доказательстве, намеченном в ч.1, аксиома выбора используется при
выборе списков.
7.18.	Пусть для каждого а&А вычисляется равенство 4а = ДХ{а}.
Поскольку НАН = ИАвИ, то каждое из множеств 4а - счетное. Тогда
АХ А = UB, где В = {4а|аеД} есть счетное множество в силу теоремы
7.17.
7.19.	Пусть К- кардинальное число. По теореме о полном упорядо-
чении множество Р(К) - полностью упорядочиваемое. По теореме 6.13
оно порядково изоморфно ординалу у, поэтому || Р(К) || = II у Ц. Пусть у
- наименьший такой ординал. По теореме 7.6ЦК || < ||Р(К)||доэтому
Ks у. Ординал у - кардинальное число, поскольку из а е у и II а II = И у II
следует || Р(К) || = И а II, что противоречит нашему выбору у.
Разрешение парадокса Кантора состоит в том, что К - не множест-
во.
ЗАДАНИЕ 33
7.20.	Определим упорядочение <х на множестве X условием а<хЬ
тогда и только тогда, когда f(a)^f(b). Нетрудно показать, что это
линейное упорядочение на множестве X. Это полное упорядочение,
поскольку из А^Х, А^еГ, следует, что f(A)^$ имеет наименьший
элемент а. При некотором а^А имеем a=f(a), при чем а - наименьший
элемент в А. Более того, /~1 удовлетворяет условиям, приведенным
при определении порядкового типа, поэтому порядковый тип X есть а.
7.21.	Пусть К - кардинальное число. Пусть А = { Р I существует
полное упорядочение ^порядкового типа Р}. По аксиоме замещения А
95
- множество,так как есть область значений определяемой функции
на множестве. Это есть множество полных упорядочений К (определя-
емое подмножество в множестве Р(К х К))?и определяемая функция
отображает каждое полное упорядочение в его порядковый тип. Пусть
у = U А. Число у больше, чем К, поскольку существует полное упорядо-
чение К порядкового типа К +01 (определим: а<₽ тогда, и только
тогда, когда либо Р = О, либо	а =#0). Следуя сделанным указа-
ниям, покажем, что у - кардинальное число, поскольку из а<у и
IIа И = Ну II следует:
1)	ае р е А при некотором р, по определению у;
2)11уН = НаН^НрН^11у11, поэтому НуН = НрНпо теореме Шредера -
Бернштейна и, таким образом,
3)	существует однозначная функция из X на у;
4)	по теореме 7.20 у - порядковый тип подного упорядочения на К,
поэтому у « А;
5)	если существует полное упорядочение Н длиной у, то существу-
ет и полное упорядочение длиной у + 01, что можно показать следую-
щим образом. Пусть Т = К\{0}. Поскольку ||Т|| = К, то существует
полное упорядочение Т длиной У. Введем полное упорядочение на К,
используя упорядочение на Т, и поместим 0 в начало;
6)	как показано выше, у + 0 Iе А, поэтому У + 0 KUA = у, что
является противоречием.
Глава 8
УНИВЕРСАЛЬНОЕ МНОЖЕСТВО
ЗАДАНИЕ 34
n-(}. V, -{{}}. И2 =({},{{}».
*з-!{ ).{{ )).{{{ })},{{},{{ )»}.
Для вашего удобства выпишем еще и
^ = {{ }»{{ }}>{{{ }}}•{{{{ }}}}»{{{ }-{{ }}}}•
{{ }.{{ }}}>{{ }»{{{ }}}},{{ },{{ М{ }}}}•
{{{ }}>{{{ }}}}.{{{ }}.{{ }>{{ }}».{{{{ }}}•
{{}.{{}}}}.{{}.{{}}.{{{}}}}.{{},{{}}.
{{}.{{}}}}>{{}.{{{}}}.{{}.{{}}}}.{{{}}.
{{{}}}.{{}.{{}}}}.{{}.{{}},{{{}}}.
{{}.{{}}}}.
8.2.	Приве дем решения для трех случаев, описанных в указаниях.
Случай 1. Утверждение тривиально, поскольку не существует
уеуо = 0.
Случай 2. а = Р + 01 при некотором р. Тогда Ур, поэтому х« Ур.
По индукции из z<=x следует zG Ур, отсюда Ур и поэтому хе Уа =
= Р(Ур).
Случай 3. а - предельный ординал. Тогда уеУр при некотором
значении «. По индукции Ур и поэтому хе уа.
8.3.	Следуя указаниям, получаем решения.
Случай 1. а = 0. Утверждение тривиально истинно.
Случай 2. « = р + 01 при некотором Р. Независимо от того, будет ли
6 = Р или же 6 е Р, по предположениям индукции в обоих случаях Ур =
= Ур. Тогда при х® Ур, хе Ур по теореме 8.2 xS Ур, поэтому х® Va =
= Р(Ур).
Случай 3. а - предельный ординал. По определению, Ур е Уа при
всех Уа = Р(Ур).
ЗАДАНИЕ 35
8.4.	Заполним пробелы в доказательстве теоремы, намеченном в
ч.П:
1.	х^УриУр+1 = Р (У р), поэтому х^Ур+i.
2.	3/ (VcVdVe((<c, d>e/A<c,	= е?Л<0, z>e/AVcV
Vd(<c, d>e/-*<Sfc?,Ud>GpA<a, b>*f).
3.	Если d^T (z), to d^f (n) при некотором n, поэтому c®U/ (n) =
=f (S(n)) и, следовательно, c^T(z).
4.	Мы можем записать 5е Va (см. доказательство теоремы 8.3), а
следовательно, и V азФ Уа.
5.	Согласно п.З q^x^T (z) и, следовательно, q^T (z). Кроме того,
q& Y и q принадлежит некоторому множеству Уа.
6.	Если qGx, то qeVg(4) ng(q)^R, поэтомуg(q)^$.
По теореме 8.3 имеем Уг<ч;е Ур> поэтому q® Ур.
ЗАДАНИЕ 36
8.5.	Следуя указаниям (см. ч.П), приведем решения:
1)	верно по теореме 7.14;
97
13-3504
2)	а<(0, поскольку в противном случае X - бесконечное по Деде-
кинду множество (см. доказательство теоремы 7.16);
3)	а ¥= О, поскольку Х+ 0, и отсюда а = S (к) при некотором кео;
4)	поскольку / - сохраняющее порядок отображение, то из нера-
венства Ь<к следует неравенство / (b)<f (к); таким образом, / -
наибольший элемент в множестве X. По теореме 6.8 получаем, что UX -
наименьшая верхняя грань множества X, и поэтому ^X=f(k);
5)UX=/(k>x<=(0.
8.6.	Пусть X = {KB|neto}. По определению, UX = и очевидно,
что ИXII = (о. Заметим, что с помощью аксиомы замещения можно
показать, что X - множество.
8.7.	Пусть Х£ Kj, IIXH sS о. Тогда UX - счетное объединение счетных
множеств и, следовательно, llUXH^o/^.
ЗАДАНИЕ 37
8.8.	По определению,не есть сильно недостижимое множество.
Множество К;- не регулярное. Что касается Nj, то X = Ко = ы < Kj, но
если ||Р(К0) К ^i,TO И* (К0Ж ^О'ЧТО противоречит теореме 7.6. По
той же причине для Кб получим, что || Р(К5) || не меньше К6.
8.9.	Пусть а будет наименьшим ординалом, таким, что П Vtt II не
меньше к. Понятно, что ординал а не 0.
Случай 1. а = ₽ + 0 1 при некотором ₽<к. Тогда И Уа11 = ИР (Ур)II, и
поскольку НУр11<к,тойУаИ<к из-за недостижимости к.
Случай 2. а - предельный ординал. Допустим, k И Vu И.
Пусть / однозначно отображает к в множество Vа. Пусть
при каждом р<а будетХр = {6к |/(б)е Ур}. Тогда:
1.	ИХрН^Н УрН<к,
2.	UXp<k, поскольку к - регулярное множество,
3.	X = U{UXp|₽<a}<k, поскольку к - регулярное множество.
4.	но К = к - противоречие.
ЗАДАНИЕ 38
8.10.	Аксиома экстенсиональности - доказательство теоремы очевидно.
Аксиома пустого множества:&е У t s yk.
Аксиома пары множеств: если х, уеУк> то хеУа, уеУр при
некоторых ординалах a, Р<к. Тогда если у - наибольший из двух
ординалов, то у<к, {х, у}е У7и, следовательно {х, у]е У7+1 а ук
Аксиома объединения: если хе Ук, то хеуа при некотором орди-
нале a<k. Если а&Ь&х, то по теореме 8.2 аеУа, откуда Ux^ya и,
следовательно, Uya + 1,e ук.
Аксиома степенного множества: если хе Ук, то хе Уа при некото-
ром ординале а<к. По теореме 8.2 x^Vu, поэтому Р (х)яр (Уа) =
= Уа + 1, а следовательно, P(x)eVa+2 - Vk.
98
Аксиома регулярности: теорема доказывается стандартным мето-
дом с помощью теоремы 8.2.
Аксиома содержательности: если x^Vk, то xeVa при некотором
ординале а<К. Если у - определяемое подмножество множества х, то
оно будет множеством и y^Vtt, поэтому уе Va + ie ^k-
Аксиома бесконечности: доказательство следует из леммы.
Лемма. Для любого ординала а верно, что а® Уа+о i.
Доказательство проводится методом трансфинитной индукции:
0®’^.
Если peVp+i, ₽ + l = ₽U{p}eVp+i, то ₽ + 1gV₽+2.
Если ординал X - предельный, а а<Х, и следовательно, Va+i,
то Хе Ух, и, таким образом, Хе у Jl+1.
Аксиома замещения: пусть / - функция из х в Уь х®Уь Тогда
хе Уa при некотором а< к. Так как х£ Уа, то по теореме 8.9 Их II <
sSllyall< к. Определим функцию g на множестве х условием g(a) =
наименьшему ординалу ₽ <к, такому, что / (а)^ Ур. Пусть R - область
значений функции g. Поскольку llxlKk, IIRII<k, то UR<k. Как и в п.6
доказательства теоремы 8.4, покажем, что область значений функции
содержится в У у д и, следовательно, есть элемент У и r+1е Vk •
Глава 9
ВЫБОР И БЕСКОНЕЧНО МАЛЫЕ ЧИСЛА
ЗАДАНИЕ 39
9.1.	Следуя указаниям, получим:
1.	EcnH6<a,Tog(a)=/({g(₽)l₽<a}) = hfX\{g('p)l₽<a})GX \
\tef₽)l ₽ <«} Hg(a) =g(b).
2.	Область значений g- определяемое подмножество X и, следова-
тельно, множество.
3.	Область определения g-1 есть область значений g.
4.	По аксиоме замещения g~1 - функция, а отсюда следует, что g -
тоже функция.
5.	Область определения функции g - совокупность ординалов D,
где О - ординал сам по себе, поскольку если и а<Р, то а®О по
построению функции g.
6.	Пусть R будет областью значения функции /, определенной на
множестве 6. Еслий¥=Х, то функцияg(6) =f(g($} | ₽ < a}) = h(x\R)
определена, поэтому б принадлежит области определения g и, таким
образом, б = б - противоречие.
7.	Функция g однозначно отображает множество X в
ординал, поэтому по теореме 7.20 множество X полностью упорядочен-
13
9.2.	Для теоремы 9.2 п.1-5 такие же, как в теореме 9.1.
6'. На самом деле g - отображение, сохраняющее порядок: если
а<0, то g(a)<g($), поэтому область значений g есть полностью
упорядоченное множество R.
7.	Если а - предельный ординал, то R не содержит наибольшего
элемента, поэтому его граница вне R. Тогда g(a) =	< aD =
-f(R) определено: таким образом, a - область определения и аеа -
противоречие.
8'. Если g(0) - не максимальный элемент, то отображение g(a) =
=gfp+о 1) определено и вновь приходим к противоречию.
ЗАДАНИЕ 40
9.3
1.	Проверяется стандартным способом.
2.	Если С - цепь в множестве R, то ОСеР - верхняя грань для С;
ОС - функция, поскольку если <у,а>, <у,Ь>^С, то <у, а> efeC и
<y,b>egec при некоторых fag. Поскольку цепь С - линейно упоря-
доченное отношением <₽ множество, то f<pg, или f = g, или g<pf.
В любом случае <у,а> и <у,Ь> одновременно принадлежат той же
самой функции и поэтому должны быть равны Ь.
3.	Если f - максимальный элемент и yeX,y±j&, то элемент у
должен быть областью определения функции /, поскольку в против-
ном случае мы могли бы выбрать а&у и продолжить функцию / до
функции g:
g = fU{<y,a>}->
тогда f<pg и, следовательно, [ - не максимальный элемент - противо-
речие.
9.4
1.	Проверяется стандартным образом.
2.	Множество {АI ы \ А - конечное} содержится в множестве Q.
3.	Если С - цепь в множестве Q, то U Се Q - верхняя грань для С.
Понятно, что U С удовлетворяет условию б). Предположим, что А,
BQUC. Тогда АеиеС, ВереС при некоторых функциях и и и По-
скольку цепь С - линейно упорядоченное отношением <q множество,
то либо u<qv, u = v, либо V<qu. Тогда либо A, Be u, либо A, Be v. В
обоих случаях А (1 Be и С.
4.	Допустим, что и есть максимальный элемент множества Q, Аеы
и ни множество А, ни ы \ А не содержатся в множестве и. Мы утвержда-
ем, что одно из этих двух множеств должно пересекаться (иметь
непустое пересечение) со всеми элементами и.
ДОКАЗАТЕЛЬСТВО. Если это не так, то для некоторого множества
Ве и пересечение А (1В = ф и для некоторого множества De ц пересе-
чение (йДА^ПО = ф. Тогда 2JHD = фи, таким образом, ue Q - противо-
речие.
Обозначим это множество как S. Множество S не может быть
конечным, поскольку тогда ы \Se и и S должны пересекаться со всеми
элементами и. Пусть теперь v = {ВП5|Веи}. Ясно, что множество v
отвечает условию б). Нетрудно показать, что оно также удовлетворяет
условию а), и, таким образом, ve Q. Однако u<4vh и - не максималь-
ный элемент, а это - противоречие.
ЗАДАНИЕ 41
9.5.	Понятно, что отношение % - рефлексивное и симметрич-
ное. Допустим, что fs g и gs h, откуда X = (ne a\f(n)~ g(n)} и У =
={ne aig(n) = h(n)} содержатся в ультрафильтреТогда ХПУе^и
ХПУе (ne = h(n)}. Остается только доказать следующую
лемму.
9.5а	. Лемма. Если А е “^и А е В, то В е 01.
ДОКАЗАТЕЛЬСТВО. Если ВФ% то ы\Де^, поэтому А Л (ы\Д)е^,
откуда 0е^, что противоречит услрвию б) в определении ультра-
фильтра.
9.6.	Отношение определено корректно: допустим,f ng%g'
и [^]s-Тогда A = {necofr(n)=f(n)}, В = {necolg(n) = g'(n)} и
С = {песо l/,('n)<Rg,fn)}содержатся в ультрафильтре ^-Отсюда
АЛВПСе {neco\f'(n) <R е<%. Легко показать, что отношение
<ш - отношение линейного порядка.
9.7.	Пусть Н(п) = п при всех п. Тогда для любого элемента г из
множества R, если к - целое число, большее чем т, то со\к £ {и co\fr(n)
Н(п)} е и, таким образом, L41s <ж [Я]®-
9.8.	Пусть 1(п) = 1/(л + 1) для всех песо. Имеем {пб<и|/(п9 =
= /о(п)}0^^ и число [/]й^[/0]й-[/]й - наверняка положительное.
Допустим, что задано число г е R г >н QR. Тогда для некоторого числа
к имеем l/(k+l)<r, поэтомусо\к 5>{песо\1(п) </г(п)}е<%. и,таким
образом, [7]й - бесконечно малое число.
ЗАДАНИЕ 42. [/]й	Ей'J(Ms, где h(n) =f(n) +R д(п) при всех
п е со. Определение дано корректно, ибо если fs [' и g s g', то
{п eco\f(n) = f(n)} П {n e co\g(n) = g’(n)} £ {n e co\f(n) +R g(n)=f' (n) +
+r
Аналогично [/]»•»« [0]s= [fcl«> где k(n) = f(n) R g(n) при всех песо -
корректное определение.
Доказательства п.1-5 сохраняются. Приведем несколько доказа-
тельств (используя обозначения, введенные в указаниях).
101
2.	Для заданного положительного числа г е R справедливо включе-
ние {песоЩп) <R г} П {neco\J(n) <R ip} с {heca|/(n)-R J(n) <R r],
и, таким образом, I J— бесконечно малое число.
3.	Для заданного положительного числа г е R справедливо включе-
ние{иесо|7(п) <Rr/2}fl{neco|J(n) <Rr/2}={neco|/(n) +R J(ri) <Rr},«.
таким образом,/ J- бесконечно малое число. Утверждения 6-8
ложные.
8.	Допустим, что [g]s - наименьшее бесконечное, положительное
гипердействительное число. Тогда если к(п) = g(n)-l при всех песо,
то [k]g^ из [^]~>но к - тоже бесконечное (nycTbreR,{n6co|kfn)>R г}=
={neco|g(n) >Rr +R lR}e^).
9.	Утверждение истинное по теореме 9.9.
Высказывание Vx(sin2(x)+cos2 (х)=1) может быть выражено на язы-
ке J5?R.
10.	Утверждение ложное. Не может быть выражено на языке Jg?R,
поэтому теорема 9.9 не применима (например, мы не можем описать
подмножество). В качестве примера рассмотрим множество всех
конечных чисел. Оно не имеет верхней грани (так как утверждения 6 и
8 - оба ложные). Заметим, что это множество тоже нельзя выразить на
языке J?R.
Глава 10
ТЕОРЕМА ГУДСТАЙНА
ЗАДАНИЕ 43
l	.g2(ll) = 84,g3(U) = 1027, затем 15627, 279937, 5764801, 134217727,
2749609302.
2	.g2(3) = 3, затем 3,2,1 Hg6(3) = 0.
3	. Сначала приведем ответы для некоторых тренировочных упраж-
нений: а) 13; б) 38; в) 46 + 92 = 138.
Теперь после первого шага 2- З2 + 2’3+2,
после 1 + 3 шагов	2 • 62 + i .g + 5,
после 1 + 3 + 6 шагов	2-12 + 11,
после 1+3 + 6 + 12 шагов	242 + 25 • 24 + 23,
после 1 + 3 + 6+ 12 +24шагов 482 +22-48 + 47.
Каждый раз мы удваиваем приращение числа шагов и тем самым
уменьшаем средний коэффициент на единицу. Чтобы избавиться от
члена в квадрате, нам потребуется в 23 раза больше шагов, поэтому
придется продолжить процесс на
102
п-1 + 3 + 6+12... + 3‘ 226 шагов,
и получим
#п(4) = (п+1) (п + 2) + (п+1) (по основанию п+2).
Чтобы уменьшить коэффициент при п+2 до нуля, мы должны
продолжить процесс удвоения еще п+1 раз, т.е. увеличить число шагов
до
т = 1 + 3 + 12 + ... + 3-216+(п + 1).
Тогда получим gm(4) = m + 1, т.е. ответом будет т + (т + 1) шагов или
g2m+i(4) “ 0- Мы можем рассчитать
п = 1 + 3 (1 + 2 + 4... + 226) = 1 + 3 (227 - 1) = 3 • 227 - 2.
Затем
m = 1 + 3 (1 + 2+ 4 +... + 225 + 3 227 ) = 1 + 3(227 + 3 • 227 - 1).
Таким образом,
2m + 1 = 2 + 3 (227+з 2” - 2) + 1 = Зв2402653211 - 3
- очень большое число.
ЗАДАНИЕ 44
10.2
Un+i(Sn(0))-fn+1(0)-0-f„(0).
d
2. Еслит = Е к.п(,
где 0< kj<п, и если лемма верна для всех чисел, меньших чем т, то
d	d	d
fn+i(Sn(m)) = fn+1 (S„ (Sfl kjti1)) = fn+i(i=g Sn(kjn1)) = /П+;(Ё^ kfX
x(n+l/n(4) = Zfl/n+I (k{ (n + l)sn(i)) = Д w fn+i (Sn (i)).k.
’fcf = i-o fn (ki‘ni) Sfn X A kr ni) (m)-
10.3. Рассмотреть случай 1, следуя указаниям, нетрудно:
fn(m)^adkd + ad-i.kd_t+_ +ык1 + кв,
то
fn(m+l) = ^ikd + y>i-i‘kd^1 +... d-^kj+kg+l.
Для случая 2
fn(ks-ns + (n-l)n5~i +... + (п-1)) = wsks + GP-J-(п-1) +... +(n-l)^
юз
<а’к, + o’-ifn-l) + ... +	+ ... + (n-
-l))<a3k, + a3-I(n-l)s<a3k, + Qs’°us(k,+ l)-fn((kt + l)'nl).
10.4
fn+2(gn+i(m))-fn+rfS'+ifafm))- l)<fn^(Sn+1(gn(m))) -fa+I(g„(m)).
10.1. Если для некоторого числа т последовательность g3(m),
gj(m)... могла бы быть продолжена неограничено, то мы бы получили
бесконечно убывающую последовательность ординалов:
f3(g2(m))>f4(g3(m))>fs(g4(m))>...,
что невозможно.
5W'
ОГЛАВЛЕНИЕ
Предисловие .	5
Введение...........................	6
ЧАСТЬ I. ЗАДАНИЯ...................10
Глава 1. Логика и теория множеств...............................
Глава 2. Натуральные числа......................................
Глава 3. Целые числа.............................................. ^9
Глава 4. Рациональные числа........................................“*
Глава 5. Действительные числа...................................
Глава 6. Ординалы...............................................
Глава 7. Кардинальные числа.....................................
Глава 8. Универсальное множество ...............................
Глава 9. Выбор и бесконечно малые числа.........................
Глава 10. Теорема Гудстайна........................................3'
ЧАСТЬ II. УКАЗАНИЯ...............................................41
Глава 1.	Логика и теория множеств................................41
Глава 2.	Натуральные числа.......................................44
Глава 3.	Целые числа.............................................45
Глава 4.	Рациональные числа......................................47
Глава 5.	Действительные числа....................................49
Глава 6.	Ординалы................................................52
Глава 7.	Кардинальные числа......................................56
Глава 8.	Универсальное множество.................................64
Глава 9.	Выбор н бесконечно малые числа..........................64
Глава 10. Теорема Гудстайна......................................72
ЧАСТЬ III. РЕШЕНИЯ...........................74
Глава 1. Логика и теория множеств
Глава 2. Натуральные числа
Глава 3. Целые числа..................
Глава 4. Рациональные числа
Глава 5. Действительные числа .
Глава 6. Ординалы.....................
Глава 7. Кардинальные числа
Глава 8. Универсальное множество .
Глава 9. Выбор и бесконечно малые числа
Глава 10. Теорема Гудстайна .	.	.	.
74
76
80
82
86
88
91
96
99
102